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 1015 mins to find solution by yourself. If can't solve inspace 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]
:

We add all numbers to hashmap, 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
. 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 hashmap (don't exists in array) and save their to result array.
The biggest waste of memory happening because we use hashmap to store duplicate numbers. It clear that in worst case hashmap 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  inspace
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]
:

We take every number and mark corresponding position as negative, like this:
i=0 > nums[0] > 41=3 > nums[3] = nums[3] > [4,3,2,7,8,2,3,1] i=1 > nums[1] > 31=2 > nums[2] = nums[2] > [4,3,2,7,8,2,3,1] i=2 > nums[2] > 21=1 > nums[1] = nums[1] > [4,3,2,7,8,2,3,1] ... i=6 > nums[6] > 31=2 > nums[2] < 0 > [4 3 2 7 8 2 3 1] i=7 > nums[7] > 11=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]
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]
andj=2
).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)