702696. Non-Repeating Element
Non-Repeating Element
Slug: non-repeating-element3958 Difficulty: Easy Id: 702696 Topic Tags: Arrays, Hash, Data Structures Company Tags: Snapdeal, Goldman Sachs, Adobe
Summary
Given an array of integers, find the first non-repeating element. If all elements are repeating, return -1.
This problem involves using arrays and data structures to solve a simple yet effective algorithmic challenge.
Detailed Explanation
To solve this problem, we can use a simple hash table approach. We iterate through the array, and for each element, increment its count in the hash table. Then, we iterate through the array again and return the first element that has a count of 1.
Here's the step-by-step breakdown:
- Initialize an empty hash table (e.g., HashMap in Java or Python).
- Iterate through the input array, and for each element:
- If the element is not present in the hash table, add it with a count of 1.
- If the element is already present, increment its count by 1.
- Initialize a variable to store the first non-repeating element (or -1 if all elements are repeating).
- Iterate through the input array again:
- For each element, check if its count in the hash table is equal to 1.
- If it is, return that element as the first non-repeating element.
Time complexity: O(n), where n is the length of the input array (since we iterate through the array twice). Space complexity: O(n), since we store the counts for each element in the hash table.
Optimized Solutions
Java
public int findFirstNonRepeatingElement(int[] arr) {
HashMap<Integer, Integer> countMap = new HashMap<>();
for (int num : arr) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
for (int num : arr) {
if (countMap.get(num) == 1) {
return num;
}
}
return -1;
}