First missing positive

Array Hash Table

42.5% acceptance

Jan 12, 2026

18285

1979

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn first_missing_positive(nums: Vec<i32>) -> i32 {
    let mut nums = nums;
    let n = nums.len();
    
    // Place each number in its right place (index-based hashing)
    for i in 0..n {
      while nums[i] > 0 && nums[i] <= n as i32 && nums[nums[i] as usize - 1] != nums[i] {
        let pos = nums[i] as usize - 1;
        nums.swap(i, pos);
      }
    }
    
    // Find the first missing positive
    for i in 0..n {
      if nums[i] != (i + 1) as i32 {
        return (i + 1) as i32;
      }
    }
    
    // If all positions are correct, return n + 1
    (n + 1) as i32
  }
}