Find All Numbers Disappeared in an Array

1. Problem Description

Given an integer array where 1 ≤ a[i] ≤ n (n = array size), some elements appear twice and others appear once.

Find all numbers in the range [1, n] that do not appear in the array.

Can you complete this task without using extra space and in O(n) time? You may assume the returned array does not count as extra space.

2. Approach

1. Approach 1
   • Traverse once and put values into a set
   • Then check whether each value in [1, n] is in the set
2. Approach 2
   • Since every number is in [1,n], an array of length n can also be used instead of a hash table

3. Implementation

3.1. HashMap

// Space complexity: O(N)
// Time complexity: O(N)
func findDisappearedNumbers(nums []int) []int {
	res := make([]int, 0)
	count := make(map[int]bool, 0)
	for _, num := range nums {
		count[num] = true
	}
	for i := 1; i <= len(nums); i++ {
		if !count[i] {
			res = append(res, i)
		}
	}
	return res
}

• Or use an array directly

func findDisappearedNumbers(nums []int) []int {
    count := make([]byte, len(nums))
    for _, val := range nums {
        count[val-1] = 1
    }

    res := make([]int, 0)

    for index, val := range count {
        if val != 1 {
            res = append(res, index+1)
        }
    }

    return res
}

3.2. In-place Hash

// Space complexity: O(1)
// Time complexity: O(N)
func findDisappearedNumbers2(nums []int) []int {
	n := len(nums)
	// For each val, use it as an index (val-1) and add len to the number at that index
	for _, v := range nums {
		v = (v - 1) % n
		nums[v] += n
	}

	// If a number is <= len, the value at this index was never increased by len, meaning val (index+1) is missing
	res := make([]int, 0)
	for i, v := range nums {
		if v <= n {
			res = append(res, i+1)
		}
	}
	return res
}

func findDisappearedNumbers(nums []int) []int {
    for i := range nums {
        for {
            index := indexFor(nums[i])
            if index < 0 || index > len(nums)-1 {
                break
            }
            if nums[i] == nums[index] {
                break
            }
            nums[index], nums[i] = nums[i], nums[index]
        }
    }
    
    var res []int
    for i := range nums {
        index := indexFor(nums[i])
        if index != i {
            res = append(res, i+1)
        } 
    }
    return res
}

func indexFor(val int) int {
    return val-1
}

4. References

• Find All Numbers Disappeared in an Array - LeetCode