Problem Statement
This problem is from Leetcode – Single Number. The problem statement is as below:
Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Solution
This problem is asking us to figure out that one integer that isn’t repeating. Lets take the Hashmap approach to solve this:
- Iterate through the given nums array and push it into a Hashmap.
- While pushing into the Hashmap check if the integer already exists. If it doesn’t exist then push with value true, else push with value false.
See the code example below:
public int singleNumber(int[] nums) {
public int singleNumber(int[] nums) {
int singleNum = nums[0];
// initialize Hashmap
Map<Integer, Boolean> numsCountMap = new HashMap<>();
// Push given integers in it
for(int i=0; i<nums.length; i++) {
// if integer is pushed first time then keep value as true
if(!numsCountMap.containsKey(nums[i])) {
numsCountMap.put(nums[i], true);
}
// if integer already present then re-push with value false
else if(numsCountMap.containsKey(nums[i])) {
numsCountMap.put(nums[i], false);
}
}
// iterate the array again and check against the Hashmap which integer has value as true
for(int i=0; i<nums.length; i++) {
if(numsCountMap.get(nums[i])) {
return nums[i];
}
}
return singleNum;
}
You can checkout the code from Github here: Single Number
See the performance of this approach in terms of space complexity below:
