First Missing Positive

1. Problem Description

Given an unsorted integer array nums, find the smallest positive integer that does not appear in the array.

Implement a solution with O(n) time complexity and only constant extra space.

2. Approach

3. Implementation

3.1. HashMap

func firstMissingPositive(nums []int) int {
    m := make(map[int]bool, 0)
    for _, num := range nums {
        m[num] = true
    }

    for i := 1; i <= len(nums);i++ {
        if !m[i] {return i}
    }

    return len(nums)+1
}

3.2. Sort + Binary Search

func firstMissingPositive(nums []int) int {
    sort.Ints(nums)
    for i := 1; i <= len(nums);i++ {
        if binarySearch(nums, i) == -1 {return i}
    }

    return len(nums)+1
}

func binarySearch(nums []int, target int) int {
    left := 0
    right := len(nums)-1
    for left <= right {
        mid := left + (right-left)>>1
        if nums[mid] == target {
            return mid
        } else if nums[mid] < target {
            left = mid+1
        } else {
            right = mid-1
        }
    }
    return -1
}

3.3. In-place Hash

func firstMissingPositive(nums []int) int {
    for i := range nums {
        // Maintain the in-place hash property that nums[i] belongs at position nums[i]-1
        // A for loop is needed for a case such as [3,4,-1,1]; after swapping, 1 could otherwise be skipped and never moved to the correct position
        for {
            val := nums[i]
            index := indexFor(val)
            if index < 0 || index > len(nums)-1 {
                break
            }
            if nums[index] == val{
                break
            }
            nums[i], nums[index] = nums[index], nums[i]
        }

    }
    
    for val := 1; val <= len(nums);val++ {
        index := indexFor(val)
        if nums[index] != val {
            return val
        }
    }
    return len(nums)+1
}

// Similar to the index of a custom hash mapping
func indexFor(val int) int {
    // Indices are in [0,n-1], while values are in [1,n], so map a value to val-1
    return val-1
}

4. References

• In-place hash solution for First Missing Positive