This page did not load. You can still read it on the original site — the toolbar below keeps your place in the directory.

Leetcode: 41. First Missing Positive Naive Solution Primary idea: Use Set to keep the positive numbers from the array and find the first…

Leetcode: 41. First Missing Positive

Naive Solution

Primary idea: Use Set to keep the positive numbers from the array and find the first positive number not included in the set.
Time Complexity: O(n)
Space Complexity: O(n)

func firstMissingPositive(_ nums: [Int]) -> Int {
    let numSet = Set(nums.filter({$0 > 0}))
    for i in 0..<nums.count {
        if !numSet.contains(i + 1) {
            return i + 1
        }
    }
    return nums.count + 1
}
firstMissingPositive([1,2,0]) // 3
firstMissingPositive([3,4,-1,1]) // 2
firstMissingPositive([7,8,9,11,12]) // 1

Optimised Solution

Primary idea: The idea is to use array elements as an index. To mark the presence of an element x, change the value at the index x to negative. But this approach doesn’t work if there are non-positive (-ve and 0) numbers.

So segregate positive from negative numbers as the first step and then apply the approach.

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

// Linear time routine for partitioning step
func partition(_ arr: inout [Int]) -> Int {
    var firstPositiveIndex = 0
    // Each time we find a positive number we move it to the
    // left side before the pivot
    for i in 0..<arr.count {
        if arr[i] > 0 { // found positive number
            // Move the number to left of pivot
            arr.swapAt(i, firstPositiveIndex)
            // Move pivot to the right
            firstPositiveIndex += 1
        }
    }
    // Return index of the first non-positive number
    return firstPositiveIndex
}
// Function for finding the first missing positive number
func firstMissingPositive(_ nums: [Int]) -> Int {
    var arr = nums
    let firstPositiveIndex = partition(&arr)
    // Traverse the positive part of the array
    for i in 0..<firstPositiveIndex {
        // Get the absolute value of the current element
        let val = abs(arr[i])
        // If the absolute value is within range and the
        // element at index `val-1` is positive, mark its
        // presence by changing its sign to negative
        if val - 1 < firstPositiveIndex && arr[val - 1] > 0 {
            arr[val - 1] = -arr[val - 1]
        }
    }
    // Traverse the positive part of the array again to find
    // the smallest missing positive number
    for i in 0..<firstPositiveIndex {
        if arr[i] > 0 {
            return i + 1
        }
    }
    // If all numbers from 1 to firstPositiveIndex are present, then the
    // missing number is `firstPositiveIndex + 1`
    return firstPositiveIndex + 1
}

iOS Interview - Leetcode 41. First Missing Positive

Naive Solution

Optimised Solution

Further Reading

Comments