Find All Numbers Disappeared in an Array (via Leetcode)¶

Date published: 2020-03-28

Category: Python

Subcategory: Beginner Algorithms

Tags: functions, loops, sets

Problem setup

This problem is on Leetcode.

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Test Cases¶

In [28]:

# assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == [2]

# assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == [2]

In this test case, the size of the array is 4, assigned to n. All elements of [1, n] would be [1, 2, 3, 4]. However, the input list does not contain 2. Therefore, this test case should return 2.

In [29]:

# assert find_disappeared_numbers_in_array([5, 6, 1, 5, 6, 1]) == [2, 3, 4]

# assert find_disappeared_numbers_in_array([5, 6, 1, 5, 6, 1]) == [2, 3, 4]

In this test case, the the size of the array is 6. All elements of [1, n] would be [1, 2, 3, 4, 5, 6]. However, the array doesn't contain [2, 3, 4] and so our function should return that.

Pseudocode¶

In [30]:

# build a python set of all numbers from i to n with n being the size of the array. 

# iterate over input list
    # if item in set:
        # pop item out of set

# return: convert set to a list

# build a python set of all numbers from i to n with n being the size of the array. # iterate over input list # if item in set: # pop item out of set # return: convert set to a list

Explanation of space and time complexity:

Let n be the number of elements in the input list assigned to the variable nums.

I iterate over n and therefore it's an O(n) time complexity. There a is another O(1) check for membership in the set that is done O(n) times. Total time complexity is O(2n). The 2 is negligent so most people say this is just O(n) time complexity.

I initially create a Python set of values from 1 to the value of n. Therefore, this is an O(n) space complexity.

Here is a great resource on time complexity operations in Python.

Code¶

In [31]:

def find_disappeared_numbers_in_array(nums):
    length_nums = len(nums)
    all_numbers_set = set(range(1, length_nums + 1))

    for num in nums:
        if num in all_numbers_set:
            all_numbers_set.remove(num)

    return list(all_numbers_set)

def find_disappeared_numbers_in_array(nums): length_nums = len(nums) all_numbers_set = set(range(1, length_nums + 1)) for num in nums: if num in all_numbers_set: all_numbers_set.remove(num) return list(all_numbers_set)

Verify Test Cases¶

In [32]:

assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == [2]

assert find_disappeared_numbers_in_array([1, 3, 4, 3]) == [2]

In [33]:

assert find_disappeared_numbers_in_array([5, 6, 1, 5, 6, 1]) == [2, 3, 4]

assert find_disappeared_numbers_in_array([5, 6, 1, 5, 6, 1]) == [2, 3, 4]