701716. First Repeating Element
Here is the detailed Markdown blog post for the "First Repeating Element" problem:
First Repeating Element
Summary
Given an array of integers, find the first repeating element. This problem involves arrays and hash data structures, making it a great exercise in understanding how to efficiently solve problems using these fundamental concepts.
Detailed Explanation
To solve this problem, we can use a HashSet to store unique elements from the array and then iterate through the array again to check for duplicates. Here's the step-by-step breakdown:
- Create an empty HashSet.
- Iterate through the array and add each element to the HashSet if it's not already present (this will automatically remove duplicates).
- Initialize a variable
firstRepeatto null. - Iterate through the array again, this time checking each element against the HashSet.
- If an element is found in the HashSet, update
firstRepeatwith that element and break out of the loop.
The time complexity for this solution is O(n), where n is the size of the input array, since we're doing a single pass through the array to create the HashSet and another pass to find the first repeating element. The space complexity is also O(n) because in the worst-case scenario (all elements are unique), we'll store all elements in the HashSet.
Here's an ASCII art diagram illustrating the algorithm:
+---------------+
| Array |
+---------------+
|
v
+---------------+
| Create HashSet |
+---------------+
|
v
+---------------+
| Iterate through |
| array to add |
| unique elements |
+---------------+
|
v
+---------------+
| Initialize firstRepeat|
| to null |
+---------------+
|
v
+---------------+
| Iterate through |
| array again |
| to find first |
| repeating element|
+---------------+
Optimized Solutions
Java
import java.util.HashSet;
public class FirstRepeatingElement {
public static int findFirstRepeating(int[] arr) {
HashSet<Integer> set = new HashSet<>();
for (int num : arr) {
if (!set.add(num)) {
return num;
}
}
return -1; // no repeating elements found
}
}