Find All Numbers Disappeared In An Array

TARGET DECK: Leetcode FILE TAGS: Easy

---

Intuition

• Mark each element that is in the range from 1 to n
  • Be careful to 0 index this, since you are creating n elements from 1 to n + 1, but the element that corresponds to 1 is at index 0.
• Then, return the elements which were not encountered.
• To improve upon space, clobber the original array:
  • Notice that each element is from 1 to n, meaning the corresponding indices are from 0 to n - 1.
  • This means that you can mark those indices which contain the num (so the num - 1) as negative, such that in the next sweep of the array, you keep only those indices that are positive + 1.
  • But make sure to keep the original value of the array and only set it to negative or positive, since duplicates are possible.

Complexity

Runtime

• $O(N)$ for two sweeps across the range of valid numbers.

Space

• $O(1)$ if clobbering original array
• $O(N)$ to check if values are in the resultant array or not.

Code

Clobbering Original Array

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        for num in nums:
            i = abs(num) - 1 # Get the position to clobber
            nums[i] = abs(nums[i]) * -1 # Clobber that position with negative of itself
        
        res = []
        # Keep the elements that remain (non-negative)
        for i, num in enumerate(nums):
            if num > 0:
                res.append(i + 1)
        return res

O(N) Extra Space

class Solution:
    def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
        n = len(nums)
        is_in = [False for i in range(1, n + 1)]
        for i in range(n):
            is_in[nums[i] - 1] = True
        
        res = []
        for x in range(len(is_in)):
            if is_in[x] == False:
                res.append(x + 1)
        return res

Cards

START Basic Front: Find All Numbers Disappeared In An Array Back: Mark the indices corresponding to num - 1 as negative, and positive num of indices in the final sweep.

END

---

References

• Find All Numbers Disappeared In An Array