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]) // 1Optimised 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
}