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.

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 <= 105
• 1 <= nums[i] <= n

Approach 1:

Iterate through the array for a range of numbers from 1 to n and return all those numbers that are not present in the array ,each of checking will need a complete traversal of the list.

class Solution:
    def findDisappearedNumbers(self, nums):
        result=[]
        n=len(nums)
        for i in range(1,n+1):
               found=False
               for j in nums:
                  if i==j:
                    found=True
                    break
               if(not found):
                  result.append(i)
                
        return li

Time O(n²)

Space :O(1)

Approach 2:

Using hash set

You can enhance the runtime at the expenditure of some space.

Here we create a hash set of the nums list, this because the runtime of lookup operation can be reduced to O(1) in case of a set.

The same algorithm above applies to this , but this time ‘j’ is something that is looked from the hash set.

Time:O(n)

Space:O(n)

Approach 3:

Third approach is some what trickier and the most optimized in terms of both space and time.

Here we are given an array of length n and the range of numbers can be from 1 to n. So if you carefully visualize and understand the problem, what if we allocate each index position for a number , such that index position ‘i’ will contain the number ‘i+1’. That is every number is placed intact with their corresponding index position. So what we do here is, we iterate through the entire array and on finding a number say ‘j’ then its actual index position which is j-1 is made to 0 and let the number that was present at the index position j-1 be some k, then the index position k-1 is also made to zero , this is continued until we encounter a zero. This operation is repeated for each non zero element we find in the array. So essentially , on marking the index position ‘i’ to zero , we mean that , the number i+1 was present in the array.

Finally we iterate again through the array and all those index position having not marked as zeros correspond to the position of missing numbers in the array.

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        li=[]
        for i in range(len(nums)):
            temp=nums[i]-1
            if(temp>=0):
                while(nums[temp]>0):
                    val=nums[temp]-1
                    nums[temp]=0
                    temp=val
        for i in range(len(nums)):
            if(nums[i]!=0):
                li.append(i+1)
                
        return li

Time: O(n)

Space: O(1)

Approach 4:

The same approach3 can be implemented in another way. We iterate through the array and all those index position of a number present in the array is marked as negative of the number present in that index position. Finally, the nums array is traversed again and all those index position not marked as negative correspond to the missing numbers.

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

Time :O(n)

Space:O(1)