[Google Interview] Find All Numbers That Disappeared in an Array

by

[toc]

?️ Company Tags: Google

Problem Formulation

Given an array nums of n integers. Return an array containing all the integers in the range[1, n]that do not appear in nums.
✒️ Here, nums[i] is in the range [1, n].

⚠️Constraints:

  • n == nums.length
  • 1 <= n <= 105
  • 1 <= nums[i] <= n

?Examples

Let’s have a look at some examples to improve our understanding of this problem.

✏️ Example 1

Input:  nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Explanation: The length of the array is 8 and the only numbers missing from it within the range 1 to 8 are '5' and '6'.

✏️ Example 2

Input:  nums = [1,1]
Output: [2]
Explanation: The length of the array is 2 and the only number missing from it within the range 1 to 2 is '2'.


✏️ Example 3

Input:  nums = [1,2,3,4,5]
Output: []
Explanation: All numbers within the range 1 to 5 are present in the array.


✏️ Example 4

Input:  [4,4,4,4]
Output: [1,2,3]
Explanation: The length of the array is 4 and the numbers missing from it within the range 1 to 4 are '1', '2' and '3'.

?️Python One-Liner Using list + set + range

❖ Approach: The idea here is to use a set within the range(1, len(nums) + 1) that allows you to get the unique elements in nums from 1 to n and then subtract set(nums) from it. This will yield you the numbers that were not in the given range.

Note:

Let’s have a look at the following illustration to understand the proposed concept:

Now, let’s have a look at the code.

def missing_numbers(nums):
    return list(set(range(1, len(nums)+1))-set(nums))

Easy! Isn’t it? ? 

Let’s run this code on our examples:

#Example 1

nums = [4,3,2,7,8,2,3,1]
print(missing_numbers(nums))
#[5,6]


#Example 2

nums = [1,1]
print(missing_numbers(nums))
#[2]

#Example 3

nums = [1,2,3,4,5]
print(missing_numbers(nums))
#[]


#Example 4

nums = [4,4,4,4]
print(missing_numbers(nums))
#[1,2,3]

Hurrah! ? The code passed all the test cases.

❖ Complexity Analysis

  • Time Complexity: Frankly speaking, we are simply finding the difference between two sets in this solution. Hence the runtime complexity of this solution is O(n).
  • Space Complexity: O(n)

But, can we avoid using the set and somehow mark the input array, which tells us what numbers are seen and what are not? This will allow us to avoid using extra space.

TIDBIT: The Python range() function creates an iterable of subsequent integers within a given range of values. You can pass either only a stop argument in which case the range object will include all integers from 0 to stop (excluded). Or you can pass start, stop, and step arguments in which case the range object will go from start to step using the given step size. For example, range(3) results in 0, 1, 2 and range(2, 7, 2) results in 2, 4, 6.

Recommended Article: Python range() Function — A Helpful Illustrated Guide

?️Optimal Solution: Without Using EXTRA Space

❖ Approach

The idea is to use the given list/array and keep track of the numbers visited. Since all the numbers are positive integers, you can mark the presence of every number that is visited by negating the number at the index that is equal to the current number. This basically means that you are marking the index that is equal to (number-1). If the number at that index is already negated, you do nothing. Finally, just return the indices (index + 1 for the number) where the numbers are still positive and represent the missing numbers within the range.

Confused? The following illustration will make things clear.

❖ Explanation:

nums = [4, 3, 2, 7, 8, 2, 3, 1]. Now let’s iterate through the array nums.

  • At iter = 0,
    • current number: |4| (|.| here refers to taking the absolute value)
    • number at index = 3 (current number - 1): 7
    • After negation: nums = [4, 3, 2, -7, 8, 2, 3, 1]
  • At iter = 1
    • current number: |3|
    • number at index = 2 (current number - 1): 2
    • After negation: nums = [4, 3, -2, -7, 8, 2, 3, 1]
  • At iter = 2
    • current number: |-2|
    • number at index = 1 (current number - 1): 3
    • After negation: nums = [4, -3, -2, -7, 8, 2, 3, 1]
  • At iter = 3
    • current number: |-7|
    • number at index = 6(current number - 1): 3
    • After negation: nums = [4, -3, -2, -7, 8, 2, -3, 1]
  • At iter = 4
    • current number: |8|
    • number at index = 7 (current number - 1): 1
    • After negation: nums = [4, -3, -2, -7, 8, 2, -3, -1]
  • At iter = 5
    • current number: |2|
    • number at index = 1 (current number - 1): -3
    • Array stays unchanged: nums = [4, -3, -2, -7, 8, 2, -3, -1]
  • At iter = 6
    • current number: |-3|
    • number at index = 2 (current number - 1): -2
    • Array stays unchanged: nums = [4, -3, -2, -7, 8, 2, -3, -1]
  • At iter = 7
    • current number: |-1|
    • number at index = 0 (current number - 1): 4
    • After negation: nums = [-4, -3, -2, -7, 8, 2, -3, -1]

Now the indices at which there are still positive numbers are the numbers (index+1) that weren’t present in the array.

❖ Let’s have a look at the code.

def missing_numbers(nums):
    for n in nums:
        i = abs(n) - 1
        nums[i] = -abs(nums[i])
    res = []
    for i, num in enumerate(nums):
        if num > 0:
            res.append(i+1)
    return res

❖ Test Cases

Let’s go ahead and execute the test cases on our code to verify the authenticity of this approach:

# Example 1
nums = [4, 3, 2, 7, 8, 2, 3, 1]
print(missing_numbers(nums))
# [5,6]


# Example 2
nums = [1, 1]
print(missing_numbers(nums))
# [2]

# Example 3
nums = [1, 2, 3, 4, 5]
print(missing_numbers(nums))
# []


# Example 4
nums = [4, 4, 4, 4]
print(missing_numbers(nums))
# [1,2,3]

❖ Complexity Analysis

  • Time Complexity: It takes n iterations to compute the solution. Hence the runtime complexity of this code is O(n).
  • Space Complexity: This solution has a space complexity of O(1).
    • You might be wondering that this isn’t O(1) space because you’re using res = []. Strictly speaking, yes, you are correct! But, “You may assume the returned list does not count as extra space in the given question.” So, that grants you some leeway.

?️Solution 3

There’s another approach to solve the given problem.

❖ Approach

  • You can iterate over the given array and add N to the existing number at the position implied by every element. Thus, the positions implied by the numbers present in the array will be definitely more than N (i.e. the smallest number is 1 and 1+N > N).
  • Therefore, in the second iteration, you simply need to report the numbers less than or equal to N to return the numbers that are missing from the given list/array.

Let’s have a look at the code:

def missing_numbers(nums):
    N = len(nums)
    for i in range(len(nums)):
        x = nums[i] % N
        print(nums[x-1])
        nums[x - 1] += N
    print(nums)
    x=[]
    for i in range(len(nums)):
        if nums[i] <= N:
            print(i)
            x.append(i+1)
            print(x)
    return x

Now let’s have a look at the following example to visualize the above solution. Consider that the given list is nums = [1, 3, 3]. The following tables demonstrate the step-by-step dry-run of this list when executed upon the above code.

❖ Test cases

numsOutput
[4, 3, 2, 7, 8, 2, 3, 1][5, 6]
[1, 1][2]
[1, 2, 3, 4, 5][]
[4, 4, 4, 4][1, 2, 3]

❖ Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Conclusion

I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.

Recommended:  Finxter Computer Science Academy

  • Do you want to master the most popular Python IDE fast?
  • This course will take you from beginner to expert in PyCharm in ~90 minutes.
  • For any software developer, it is crucial to master the IDE well, to write, test and debug high-quality code with little effort.
The Complete Guide to PyCharm

Join the PyCharm Masterclass now, and master PyCharm by tomorrow!