645.set-mismatch.md

645. Set Mismatch

Hash Table

Since the value of input array ranges from 1..n, and we're going to find the duplicate and missing, we can use input array itself as hash table and index as key (value - 1), then iterate every number and mark the number as negative (seen).

When seeing value = 3 (A[i]), we mark A[2] as negative.

• The number is already negative, we've seen this before, it's duplicate.
• Then iterate again to see which number has not been seen (positive).

fun findErrorNums(nums: IntArray): IntArray {
    var duplicate = 0
    for (i in 0 until nums.size) {
        val value = nums[i]

        // We see value, we mark `A[value - 1]` as negative.
        // When seeing 3, we mark `A[2]` as negative.
        if (nums[value - 1] < 0) {
            duplicate = value
        }
        nums[value - 1] = -abs(nums[value - 1])
        
    }
    var missing = 0
    for (i in 0 until nums.size) {
        // When A[2] is positive, then we didn't see 3.
        // When A[i] is positive, then we didn't see i + 1.
        // When seeing i + 1, we mark `A[i]` as negative.
        if (nums[i] > 0) {
            missing = i + 1
            break
        }
    }
    return intArrayOf(duplicate, missing)
}

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

Cycle sort

See My Notes

We see A[i] = 4, then we should place it to A[3] (A[A[i] - 1] should be 4). Then iterate again to find the duplicate number A[i] that satisfies A[i] != i + 1.

fun findErrorNums(nums: IntArray): IntArray {
        // duplicate, missing
        val ans = IntArray(2)
        val n = nums.size

        for (i in 0 until n) {
            while (nums[i] - 1 in 0 until n && nums[i] != nums[nums[i] - 1]) nums.swap(i, nums[i] - 1)
        }
        // Or equivalent to:
        // var i = 0
        // while (i < n) {
        //     if (nums[i] - 1 in 0 until n && nums[i] != nums[nums[i] - 1]) {
        //         nums.swap(i, nums[i] - 1)
        //     } else {
        //         i++
        //     }
        // }

        // 0, 1, 2, 3
        // 1, 2, 2, 4
        // index 2 should be 3 (missing), but it's 2 (duplicate)
        // duplicate is 2, missing is 3
        for (i in 0 until n) {
            if (i + 1 != nums[i]) {
                ans[0] = nums[i]
                ans[1] = i + 1
            }
        }
        return ans
    }