First Missing Positive


Problem

Given an unsorted integer array numsnums of length nn, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n)O(n) time and uses O(1)O(1) auxiliary space.

Example

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.
Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.
Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

Constraints

  • 1n1051 \leq n \leq 10^5
  • 231numsi23112^{31} \leq nums_i \leq 2^{31} - 1

Submit your solution at here

Solution

Intuition

Sort and find missing element resulting in O(n×logn)O(n \times logn) time, n=105n = 10^5 so that solution would AC if you insist on doing so 🙄. We can do better than that. We will traverse once and fill all number slots. Then do a 2nd pass and check for the first unfilled slot.

Approach

We define “useless” number as a number that is not contribute to our final sequence. Those number are

  • Out of range [1,n][1,n]
  • Or already exist before

For example:

[3,4,-1,1,0,99] // -1, 0, 99 are useless number
[7,8,9,11,12] // all numbers in the array are out of range [1~5] and are useless

In the first pass, we will have a running pivot ii, and put all useful number in its position, all useless number behind ii For example, this is an array before/after first pass

// input array
[0,6,2,2,4,0,1,4,1,3]
// loop iteration
check 10
swap 10/3, nums = [0, 6, (3), 2, 4, 0, 1, 4, 1, (2)]
check 10
swap 10/2, nums = [0, (2), 3, 2, 4, 0, 1, 4, 1, (6)]
check 10
swap 10/6, nums = [0, 2, 3, 2, 4, (6), 1, 4, 1, (0)]
check 10 nothing happened
check 9
swap 9/1, nums = [(1), 2, 3, 2, 4, 6, 1, 4, (0), 0]
check 9 nothing happened
check 8
swap 8/4, nums = [1, 2, 3, (4), 4, 6, 1, (2), 0, 0]
check 8~1 nothing happened

In the final array, notice that first position has an odd item is 55, so we return 55

Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

Code

impl Solution {
    pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
        let mut nums = nums;
        let mut i = nums.len();
        while i > 0 {
            let useless = nums[i-1] > i as i32 || nums[i-1] < 1;
            if useless {
                i -= 1;
                continue;
            }
            let j = nums[i-1] as usize;
            let useless = nums[i-1] == nums[j-1];
            if useless {
                i -= 1;
                continue;
            }
            nums.swap(i-1,j-1);
        }
        //println!("{:?}", nums);
        return nums.iter()
            .enumerate()
            .take_while(|&(i, &x)| i as i32 == x-1)
            .count() as i32 + 1;
    }
}