Find All Numbers Disappeared in an Array - Go solutions

Hi everyone! Today, we will look at rather easy question from topic arrays. The most interesting in here - solution without using additional memory.

The question

Link: 448. Find All Numbers Disappeared in an Array.
Difficulty: easy

💡 Take 10-15 mins to find solution by yourself. If can't solve in-space time, let's keep reading.

Approach #1 - Extra space

func findDisappearedNumbers(nums []int) []int {
   hp := make(map[int]int)
   n := len(nums)
   res := make([]int, 0)

   for i := 0; i < n; i++ {
      hp[nums[i]]++
   }

   for i := 0; i < n; i++ {
      _, ok := hp[i+1]
      if ok == false {
         res = append(res, i+1)
      }
   }

   return res
}

Algorithm for input [4,3,2,7,8,2,3,1]:

1. We add all numbers to hash-map, it gives us like this:
   

   {
       4: 1,
       3: 2,
       2: 2,
       7: 1,
       8: 1,
       1: 1
   }
   

   It's not necessary to count amount of each number in nums.

2. We know, highest value in array equals length of this array. Therefore we just need to find numbers from 1 to length which doesn't exists in create hash-map (don't exists in array) and save their to result array.

3. The biggest waste of memory happening because we use hash-map to store duplicate numbers. It clear that in worst case hash-map would use memory same as input array. So, it takes O(n) space complexity. Also, we have 2 passes through nums array, it takes O(2n) → O(n).

Approach #2 - in-space

func findDisappearedNumbers(nums []int) []int {
    for i := 0; i < len(nums); i++ {
        ind := abs(nums[i]) - 1
        if nums[ind] > 0 {
            nums[ind] = -nums[ind]
        }
    }

    j := 0

    for i := 0; i < len(nums); i++ {
        if nums[i] > 0 {
            nums[j] = i+1
            j++
        }
    }

    return nums[:j]
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

Algorithm for input [4,3,2,7,8,2,3,1]:

1. We take every number and mark corresponding position as negative, like this:
   

   i=0 -> nums[0] -> 4-1=3 -> nums[3] = -nums[3] -> [4,3,2,-7,8,2,3,1]
   i=1 -> nums[1] -> 3-1=2 -> nums[2] = -nums[2] -> [4,3,-2,-7,8,2,3,1]
   i=2 -> nums[2] -> 2-1=1 -> nums[1] = -nums[1] -> [4,-3,-2,-7,8,2,3,1]
   ...
   i=6 -> nums[6] -> 3-1=2 -> nums[2] < 0 -> [4 -3 -2 -7 8 2 -3 -1]
   i=7 -> nums[7] -> 1-1=0 -> nums[0] = -nums[0] -> [-4 -3 -2 -7 8 2 -3 -1]
   
   [-4 -3 -2 -7 8 2 -3 -1]
   [ 0  1  2  3 4 5  6  7]
   

2. As you can see above, there are two positive numbers, their indexes + 1 will be the disappeared digits we were looking for. We put their to the beginning of array and return calculated range of slice ( [5 6 -2 -7 8 2 -3 -1] and j=2).

3. It takes O(1) space complexity because we don't use any additional structures. We have two consecutive passes through array. It takes O(2n) → O(n) (discard constants) time complexity.