DEV Community

Cover image for Find All Numbers Disappeared in an Array - Go solutions
Valeriy
Valeriy

Posted on

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
}
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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.

Discussion (0)