268.missing-number.md

268. Missing Number

Hash Table

fun missingNumber(nums: IntArray): Int {
    val hashSet = hashSetOf<Int>()
    for (n in nums) {
        hashSet.add(n)
    }
    for (i in 0..nums.size) {
        if (!hashSet.contains(i)) return i
    }
    return -1
}

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

Sum

Since the input values range 0..n, we can calculate the sum of 0..n and subtract the sum of input array to get the missing number.

fun missingNumber(nums: IntArray): Int {
    val n = nums.size

    var sum = 0
    for (num in nums) sum += num
    return (n + 1) * n / 2 - sum
}

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

Cycle sort

The following note is deprecated, please refer to My Notes

We can use array itself as hash table and index as key since the value range in 0..n, we can place the value at the index it should be, that is nums[i] = i.

For input [3, 0, 1], value 3 should be placed at index 3 (but it's out of bound, we just ignore), value 0 should be placed at index 0 so on, the idea is to place the number at the position correctly by swapping. So we iterate the array and swap the value to the index it should be.

It might not be the value we want after swapping, so we don't move forward the iteration, and keep swapping the value until nums[i] == i or nums[i] is out of bound.

Some solution will write in nums[i] and nums[nums[i]], that is equivalent to nums[i] and nums[value] in our solution.

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

index =  0  1  2  3
value = [2, 0, 4, 1]
         i
         4, 0, 2, 1 // Swapped 2 and 4
            i
         0, 4, 2, 1 // Swapped 0 and 4
               i  
         0, 4, 2, 1 // Just move forward
                  i
         0, 1, 2, 4 // Swapped 1 and 4
                     i

fun missingNumber(nums: IntArray): Int {
    val n = nums.size
    var i = 0
    while (i < nums.size) {
        if (nums[i] in 0 until n && i != nums[i]) {
            nums.swap(i, nums[i])
        } else {
            i++
        }
    }
    // Or equivalent to for loop (skip)

    for (i in 0 until nums.size) {
        val value = nums[i]
        if (i != value) return i
    }
    return nums.size
}

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

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