Single Number – Leetcode #136

Problem Statement

This problem is from Leetcode – Single Number. The problem statement is as below:

Given an integer array where every element appears twice except one, find the single element that appears only once.

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:

PERFORMANCE ANALYSIS

RUNTIME	12 ms | Beats 22.31 %
MEMORY	44.92 MB | Beats 94.52 %
TIME COMPLEXITY	O ( N )
SPACE COMPLEXITY	O ( N )