703697. Find unique element
Find Unique Element
Summary
This problem involves finding a unique element in an array where each element appears exactly twice, except for one element that appears only once. The task is to identify this unique element using various algorithmic approaches.
Detailed Explanation
To solve this problem, we can use a simple hash map (or dictionary) approach. We iterate through the array and count the frequency of each element. Then, we return the element with a count of 1, as it's the unique one.
Here's a step-by-step breakdown:
- Initialize an empty hash map
freqMapto store the frequency of each element. - Iterate through the given array:
- For each element, increment its count in
freqMap. If the element is not present in the map, add it with a count of 1.
- For each element, increment its count in
- Iterate through
freqMapand return the key (element) that has a count of 1.
Time complexity: O(n), where n is the length of the array. We need to iterate through the array twice (once for counting frequencies and once for finding the unique element).
Space complexity: O(min(n, m)), where m is the size of the hash map. In the worst-case scenario, we might store all unique elements in the hash map.
Optimized Solutions
Java
import java.util.HashMap;
import java.util.Map;
public int findUniqueElement(int[] arr) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
return -1; // or throw an exception
}