41.first-missing-positive.md

41. First Missing Positive

Hash Table

Idea!! For array of size = n, the first missing positive numbe will be in the range of 1 to n + 1 (inclusive).

We have the time and space complexity constraints, so we are going to use array itself as hash table , we use array index as key, and mark the element of that index as seen. For example, if we mark A[1] as negative number when we see 2 (not missing) (and 0-based index, we have to -1 for index).

See 3, mark A[2] as negative! Index = value - 1

But before mark the number to negative, we might contain zero or negative in the beginning, and they are not the answer, so we will change the them number to n + 1 (or some number out of normal range [1..n + 1])

Then we start to mark the number we've seen and iterate the whole array to check if any number was not marked as negative. If all numbers were marked, then return n + 1. ([1, 2, 3] the answer will be 4)

def firstMissingPositive(self, nums: List[int]) -> int:
    n = len(nums)
    for i in range(0, n):
        if nums[i] <= 0: nums[i] = n + 1
    for i in range(0, n):
        value = abs(nums[i])
        if 0 < value and value <= n:
            nums[value - 1] = -abs(nums[value - 1])
    for i in range(0, n):
        if nums[i] > 0: return i + 1
    return n + 1

fun firstMissingPositive(nums: IntArray): Int {
    val n = nums.size
    for (i in 0 until n) {
        if (nums[i] <= 0) nums[i] = n + 1
    }
    for (i in 0 until n) {
        // The number might be marked negative before, we have to operate using absolute numbers.
        val value = abs(nums[i])
        if (value in 1..n) {
            // -1 for 0-based index.
            // Using abs() for the same reason above
            nums[value - 1] = -abs(nums[value - 1])
        }
    }
    for (i in 0 until n) {
        if (nums[i] > 0) return i + 1
    }
    
    return n + 1
}

• Time Complexity: O(n).
• Space Complexity: O(1), we use array itself as hash table.

Cycle sort

See My Notes

Since the value range is 1..n, this approach is to position the element to the index it should be by swapping. That is nums[i] should place at index nums[i] - 1 (0-based index).

For example, 2 should be placed at A[1] (-1 for 0-based index), [3, 4, -1, 1] shoule be placed like [1, -1, 3, 4]

See 3, place to A[2]. Index = value - 1

index = 0, 1, 2, 3
value = 3, 4,-1, 1  // original 
value = 1, 2 ,3, 4 // It should be after swapping

def firstMissingPositive(self, nums: List[int]) -> int:
    # Recommended to use swap function
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]

    n = len(nums)
    for i in range(0, n):
        # See 3, it should place A[2]
        while 0 < nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            # nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i] 
            # will lead to infinite loop, because nums[i] is updated.
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
            # Or swap(nums, i, nums[i] - 1)
    
    # A[2] should be 3
    for i in range(0, n):
        if nums[i] != i + 1: return i + 1
    return n + 1

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

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

    for (i in 0 until n) {
        if (nums[i] != i + 1) return i + 1
    }
    return n + 1
}

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), we use array itself as hash table.