## DEV Community is a community of 751,566 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 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 -> 4-1=3 -> nums = -nums -> [4,3,2,-7,8,2,3,1]
i=1 -> nums -> 3-1=2 -> nums = -nums -> [4,3,-2,-7,8,2,3,1]
i=2 -> nums -> 2-1=1 -> nums = -nums -> [4,-3,-2,-7,8,2,3,1]
...
i=6 -> nums -> 3-1=2 -> nums < 0 -> [4 -3 -2 -7 8 2 -3 -1]
i=7 -> nums -> 1-1=0 -> nums = -nums -> [-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.