Arrays - Find All Numbers Disappeared in An Array

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums.

Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Explanation: Missing numbers from array are 5, 6 as array should have numbers from 1-8.

Input: nums = [1,1]
Output: [2]
Explanation: Missing numbers from array 2 as array should have numbers from 1-2.

Follow up: Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Solution 1 - Store numbers in a HashSet, then loop through from 1-n to find missing
Solution 2 - Mark visited indexed numbers first, then find missing numbers (Answer to follow-up question)

In this approach, we are going going to store input array nums elements into a HashSet first, so that if there are any duplicates removed. Then, loop through from 1...n and check if the number exists in the HashSet or not, if it is not then that is a missing number.

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.stream.IntStream; public class FindAllMissingNumbersFromArray { static List<Integer> usingHashSetApproach(int[] nums) { HashSet<Integer> unique = new HashSet<>(); IntStream.of(nums).forEach(unique::add); List<Integer> missing = new ArrayList<>(); for(int i=1; i<=nums.length; i++) { if(!unique.contains(i)) { missing.add(i); } } return missing; } }

Complexity Analysis:

Time complexity: O(n) where n is the input array nums length.
Space complexity: O(n) since we are using HashSet to store elements.

As per the problem statement, the numbers will be in range [1,n], so that mean they all have to be positive integers

We first go through elements of the input array nums, these numbers may range from 1....n and and indexing of array is 0....n-1, so we can essentially map each number in the input array to an index of the array, say if the number in array is M then there the index for the number will be M-1.

Now, we know that each number will have an associated index in the array, so will be markig those indexes as visited by making number at that index negative. But some numbers may be repeated, for example say if the input array is [2, 2, 2, 4]

When we are at index 0, number in the array is 2 so the corresponding index will be 2-1= 1, so mark the number at index 1 to negative, so it becomes [2, -2, 2, 4].
When we are at index 1, number in the array is already negative -2 so in this case we have to take absolute value to get the corresponding index abs(-2) -1 = 1, so mark the number at index 1 to negative, but the number is already negative, so when marking a number as negative, either ignore marking it again (or) take -1 * abs(nums[i]) so it becomes [2, -2, 2, 4].

By the time we loop through all elements and mark the numbers, it is gonna look like this [2, -2, 2, -4].

Now, we will loop through array after marking, and if the number is still positive, that means it is a missing number which is equal to index +1.

import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.stream.IntStream; public class FindAllMissingNumbersFromArray { /* loop through array, and mark indexed numbers 1....n will turn into indexes 0... n-1, then find missing ones*/ static List<Integer> markIndexedNumbers(int[] nums) { for(int i=0; i<nums.length; i++) { int index = Math.abs(nums[i]) -1; nums[index] = -1 * Math.abs(nums[index]); } List<Integer> missing = new ArrayList<>(); //after marking is done, loop through array and if value is +ve then that is a missing number. for(int i=0; i< nums.length; i++) { if(nums[i]>0) { missing.add(i+1); } } return missing; } }

Complexity Analysis:

Time complexity: O(n) where n is the input array nums length. Everytime sumRange is called, it returns in constant time.
Space complexity: O(1), since we are modifying input array itself and not using any intermediate data structure to store data.

Above implementations source code can be found at GitHub link for Java code

Contents

Complexity Analysis:

Complexity Analysis: