Single Number – Leetcode #136

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:

1. Iterate through the given nums array and push it into a Hashmap.
2. 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: