Teaching Kids Programming – Two Algorithms to Find All Numbers Disappeared in an Array (Hash Set)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]

Example 2:
Input: nums = [1,1]
Output: [2]

Constraints:
n == nums.length
1 <= n <= 10^5
1 <= nums[i] <= n

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.

Find All Numbers Disappeared in an Array (Hash Set)

The straightforward solution is to use a hash set to remember all the numbers (we can convert the array easily to set), and then checking the numbers that disapper from 1 to N inclusive using the hash set. The time/space complexity is O(N).

1
2
3
4
5
6
7
8
9

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        ans = []
        seen = set(nums)
        n = len(nums)
        for i in range(1, n + 1):
            if i not in seen:
                ans.append(i)
        return ans

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        ans = []
        seen = set(nums)
        n = len(nums)
        for i in range(1, n + 1):
            if i not in seen:
                ans.append(i)
        return ans

Find All Numbers Disappeared in an Array (In-place)

As all the numbers are within the range from 1 to N, and they are positive, we can use the absolute value of the value (e.g. a) minus 1 as the index, and we turn that number into negative to mark value a visited. Then a second pass going through the array to check if the number is visited (negative).

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        ans = []
        for i in nums:
            idx = abs(i) - 1
            if nums[idx] > 0:
                nums[idx] *= -1
        
        for i in range(1, len(nums) + 1):
            if nums[i - 1] > 0:
                ans.append(i)
 
        return ans

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        ans = []
        for i in nums:
            idx = abs(i) - 1
            if nums[idx] > 0:
                nums[idx] *= -1
        
        for i in range(1, len(nums) + 1):
            if nums[i - 1] > 0:
                ans.append(i)

        return ans

The time complexity is O(N) but the space complexity is O(1) constant as we are checking/modifying inplace. This however excludes counting the returned array as additional space usage.

–EOF (The Ultimate Computing & Technology Blog) —