041 - First Missing Positive

41. First Missing Positive

Problem Statement

Given an unsorted integer array nums, return the smallest missing positive integer.

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

 

Example 1:

Input: nums = [1,2,0]
Output: 3
Explanation: The numbers in the range [1,2] are all in the array.

Example 2:

Input: nums = [3,4,-1,1]
Output: 2
Explanation: 1 is in the array but 2 is missing.

Example 3:

Input: nums = [7,8,9,11,12]
Output: 1
Explanation: The smallest positive integer 1 is missing.

 

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1

Click to open Hints

• Think about how you would solve the problem in non-constant space. Can you apply that logic to the existing space?
• We don't care about duplicates or non-positive integers
• Remember that O(2n) = O(n)

Solutions

Go

package main

func firstMissingPositive(nums []int) int {
	i := 0

	for i < len(nums) {
		if nums[i] > 0 && nums[i] <= len(nums) && nums[nums[i]-1] != nums[i] {
			nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
		} else {
			i++
		}
	}

	for i, num := range nums {
		if num != i+1 {
			return i + 1
		}
	}

	return len(nums) + 1
}

Rust

impl Solution {
    pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
        let (mut nums, mut i) = (nums, 0);

        while i < nums.len() {
            let num = nums[i];

            // if the number is in the range [1, nums.len()] and not in the right position
            // swap it with the number at the right position
            if num > 0 && num <= nums.len() as i32 && num != nums[num as usize - 1] {
                nums.swap(i, num as usize - 1);
            } else {
                i += 1;
            }
        }

        // find the first missing positive number
        for (i, num) in nums.iter().enumerate() {
            if num != &(i as i32 + 1) {
                return i as i32 + 1;
            }
        }

        nums.len() as i32 + 1
    }
}

...