Missing Number – Leetcode #268

Problem Statement

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

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Solution

Approach-1

Lets try a simple for loop approach first.

1. Sort the given array.
2. Set a counter variable count = 0
3. Iterate in a for loop and compare array integers to count. Increment count with every iteration of the loop.
4. Return the missing number.

See the code sample below:

public int missingNumber(int[] nums) {

		int missingNum = nums[0];
		
		// sort the given array
		Arrays.sort(nums);
		
		// initialize a counter to zero
		int count =0;
		
		// iterate in for loop and compare array integers with count
		for(int i=0; i<=nums.length; i++) {
			
			if(i < nums.length) {
				
				// if integer doesn't match with count then return it
				if(nums[i] != count) {
					
					missingNum = count;
					return missingNum;
				}
				
				// increment count
				count = count+1;
			}
			// if array integers are exhausted then return count
			else if(i == nums.length) {
				
				missingNum = count;
				return missingNum;
			}
			
		}
		
		return missingNum;
	}

Time complexity of this approach is O(N). You can checkout the code from Github here: Missing Number – First Approach.

See the performance of this approach below:

Approach – 2

Lets expand on the above approach and use a HashSet.

1. Iterate the given array and push the integers in a HashSet.
2. Now in a for loop, iterate between 0 and N, and check which integer is missing.
3. Return the missing integer in HashSet as answer.

See the code sample below:

public int missingNumber(int[] nums) {
		
		int missingNum = nums[0];
		
		// initialize a Hashset
		Set<Integer> numSet = new HashSet<>();
		
		// iterate in a loop and push array integers into the Hashset
		for(int i=0; i<nums.length; i++) {
			
			numSet.add(nums[i]);
		}
		
		// now between 0 and N, check which integer is missing
		for(int i=0; i<=nums.length; i++) {
			
			if(!numSet.contains(i)) {
				
				// return the integer not present in Hashset
				return i;
			}
		}
		
		return missingNum;
	}

Time complexity of this approach is O(N). You can checkout the code from Github here – Missing Number – Second Approach.

See the performance of this approach below:

Approach – 3

Lets take an out of the box approach. Lets add up all the integers in given array and store in variable numsSum. Also lets add up all the integers between 0 and N and store in expectedSum. The difference between expectedSum and numsSum is our answer. See the code sample below:

public int missingNumber(int[] nums) {
		
		int missingNum = nums[0];
		
		// initialize sum variable to zero
		int numsSum = 0;
		
		// iterate in for loop and add all integers in given array and store in numsSum
		for(int i=0; i<nums.length; i++) {
			
			numsSum = numsSum + nums[i];
		}
		
		// initialize sum variable and a counter to zero
		int expectedSum = 0;
		int num = 0;
		
		// add all integers between 0 to N and store in expectedSum
		for(int i=0; i<=nums.length; i++) {
			
			expectedSum = expectedSum + num;
			num = num+1;
		}
		
		// find the difference and return it
		missingNum = expectedSum - numsSum;
		
		return missingNum;
	}

The time complexity of this approach is O(N). You can checkout the code from Github here: Missing Number – Third Approach.

See the performance of this approach below: