448.find-all-numbers-disappeared-in-an-array.md

448. Find All Numbers Disappeared in an Array

The two below solutions are similiar to 41. First Missing Positive with some modification.

Hash Set

Since the values range 1...n, we can add all elements to set, and iterate 1...n to find the missing number.

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    n = len(nums)
    nums_set = set(nums)
    missing = []
    for i in range(1, n + 1):
        if i not in nums_set:
            missing.append(i)
    return missing

• Time Complexity: O(n).
• Space Complexity: O(n).

Hash Table

Since the values range 1...n, we can use index to represent the number we saw before. For example, nums[i] is 4, then we mark index 3 as seen (negative).

We iterate all elements, we mark abs(nums[nums[i] - 1]) as negative (we use 0 indexed, so we have to minus one, get absolute value because it might has been marked before) to indicate that we have seen nums[i].

Then iterate again to find the index of positive number (not be marked, not seen before)

Index:  0  1  2  3
Input: [4, 3, 3, 4]
        i
        4, 3, 3,-4  // Marked index 4 - 1 = 3 as negative
           i   
        4, 3,-3,-4  // Marked index 3 - 1 = 2 as negative
              i

The input array becomes [4, 3, -3, -4], and we find out nums[0] and nums[1] are positive (not marked, not seen before), so return [0, 1].

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    # See 3, mark A[2] as negative
    for i in range(len(nums)):
        value = abs(nums[i]) - 1
        nums[value] = -abs(nums[value])
    missing = []
    for i in range(len(nums)):
        if nums[i] > 0:
            missing.append(i + 1)
    return missing

fun findDisappearedNumbers(nums: IntArray): List<Int> {
    val disappearedNumbers = mutableListOf<Int>()
    for (i in 0 until nums.size) {
        val index = nums[i].abs() - 1
        nums[index] = -nums[index].abs()
    }
    for (i in 0 until nums.size) {
        if (nums[i] > 0) {
            disappearedNumbers.add(i + 1)
        }
    }
    return disappearedNumbers
}

• Time Complexity: O(n) for only two for-loops.
• Space Complexity: O(1) no extra space.

Cycle sort

See My Notes

We can use array itself as hash table and index as key since the value range in 1..n, we can place the value at the index it should be, that is nums[i] - 1 = i. For example, A[0] = 4, then we should move to A[3] by swapping.

Then iterate again to find the value that is not at the right index (the value != index), then it would be the missing number.

def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]

    # See 3, place to A[2] by swapping
    n = len(nums)
    for i in range(n):
        while 0 < nums[i] <= n and nums[i] != nums[nums[i] - 1]:
            swap(nums, i, nums[i] - 1)

    missing = []
    for i in range(n):
        if nums[i] != i + 1:
            missing.append(i + 1)
    return missing

fun findDisappearedNumbers(nums: IntArray): List<Int> {
    val n = nums.size
    var i = 0
    while (i < nums.size) {
        val value = nums[i]
        if (nums[value - 1] != value) nums.swap(i, value - 1)
        else i++
    }

    val results = mutableListOf<Int>()
    for (i in 0 until n) {
        if (nums[i] != i + 1) results.add(i + 1)
    }
    return results
}

private fun IntArray.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}