702915. Single Number
Single Number
Slug: single-number1014 Difficulty: Easy Id: 702915 Topic Tags: Arrays, Data Structures Company Tags: Amazon
Summary
Given an array of integers where every element appears twice except for one, which appears once. Find that single number.
This problem is about finding a unique element in an array where all other elements appear twice. The key concepts involved are arrays and data structures.
Detailed Explanation
The solution to this problem involves using a hash table (in Python, we can use the built-in dict type) to keep track of the frequency of each number. Then, iterate through the hash table to find the unique element that appears only once.
Here is a step-by-step breakdown of the solution:
- Initialize an empty dictionary (
freq_dict) to store the frequency of each number. - Iterate through the given array and for each element:
- Check if the element is already in
freq_dict. If it is, increment its value by 1. If not, add it tofreq_dictwith a value of 1.
- Check if the element is already in
- After iterating through the entire array, find the key in
freq_dictthat has a value of 1. This will be the unique element.
Time complexity: O(n) where n is the length of the input array. Space complexity: O(min(n, m)) where m is the maximum possible frequency of an element in the array.
Optimized Solutions
Java
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
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
}