Find All Numbers Disappeared in an Array – Leetcode #448

Problem Statement

This problem is from Leetcode – Find All Numbers Disappeared in an Array.

Given an array nums of n integers, where each nums[i] is in the range [1, n], find and return all integers in the range [1, n] that are missing from nums.

Solution

The solution to this problem is simple enough. In first pass we’ll add all numbers from zero till the length of the array in a HashSet. In second pass we’ll check if any numbers are missing in this HashSet in comparison to the given array. See the code sample below:

public List<Integer> findDisappearedNumbers(int[] nums) {

		List<Integer> intList = new ArrayList<Integer>();

		Set<Integer> numSet = new HashSet<Integer>();

		
		// add numbers in a Hashset
		for(int i=0; i<nums.length; i++) {

			numSet.add(nums[i]);

		}
		
		// now find the missing numbers
		for(int i=1; i<=nums.length; i++) {

			if(!numSet.contains(i)) {

				System.out.println(i);
				intList.add(i);
			}
		}



		return intList;
	} 

You can checkout the code from Github here: Find All Numbers Disappeared in an Array. See the performance of this approach below:

PERFORMANCE ANALYSIS

RUNTIME	17 ms | Beats 36.18 %
MEMORY	55.36 MB | Beats 21.90 %
TIME COMPLEXITY	O(N)