Interview Bootcamp
Vote

0% completed

​

Find all Missing Numbers (easy)

Problem Statement

We are given an unsorted array containing numbers taken from the range 1 to ‘n’. The array can have duplicates, which means some numbers will be missing. Find all those missing numbers.

Example 1:

Input: [2, 3, 1, 8, 2, 3, 5, 1]
Output: 4, 6, 7
Explanation: The array should have all numbers from 1 to 8, due to duplicates 4, 6, and 7 are missing.

Example 2:

Input: [2, 4, 1, 2]
Output: 3

Example 3:

Input: [2, 3, 2, 1]
Output: 4

Constraints:

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

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Azimul Haque

· 4 years ago

I need help in understanding "Find all Missing Numbers (easy)" problem. Unlike the previous problem, in which j = nums[i] was used, what is the reason for using j = nums[i] - 1 instead of j = nums[i] ? Please explain the reason why it is used as it has not been explained in the solution. Thanks!

Show 2 replies
Y

Yogi Paturu

· 5 years ago

In the explanation for the space complexity, why would you ignore the space required for the output array?

The length of the missingNumbers output array would, at worst, be the length of nums array - 1. This would be if nums is all duplicates of one number.

Any thoughts?

Show 1 reply
CPK N.A

CPK N.A

· 4 years ago

I need help understanding the first if statement in this problem if(nums[i] != nums[nums[i]-1]). Why is it not sufficient to do a check such as if(nums[i] != i+1) ?

Show 2 replies
D

davemednikov

· 3 years ago

This solution has several variables that could use better naming and explanation in the solution.

The purpose of i can be understood to be the current index when iterating through the list of numbers.

However what about the variable j? What does the assignment in j = nums[i] - 1 represent? Is this supposed to be the expected index for the current number?

What are we checking for in if nums[i] != nums[j]:? That the number at the current index is not equal to the number we expect to see at the current index? What are we achieving with this swap?

Other explanations have been much more in depth but this one was a bit lacking. Please advise. Thank you!

L

Luke Samuel

· 4 years ago

So why couldn't we just use a built in sort for a question like this? Is it because that's restricted in this problem?

Show 1 reply
T

tedgo001

· 2 years ago

For the conditions to tell if a swapping is needed:

if(nums[start] != nums[nums[start] - 1]) will not give a TLE but if(nums[start] != start+1) will. Wondering why this happens?

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

class Solution:
  def findNumbers(self, nums):
    missing = []

    def swap(i, j):
      nums[i], nums[j] = nums[j], nums[i]
    
    for i in range(len(nums)):
      # nums[i] != nums[nums[i] - 1] = an item that is in the correctly positioned
      # while the item is miss positioned and not referring to an item that in the correctly positioned. keep swapping
      while nums[i] != i + 1 and nums[i] != nums[nums[i] - 1]:
        swap(i, nums[i] - 1)

    # like in 1, 2, 3, 1, 5, 3, 2, 8
    for i in range(len(nums)):
      if nums[i] != i + 1:
        missing.append(i + 1)
    
    return missing