First Missing Positive

hard array cyclic sort

Problem

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

Inputnums = [3, 4, -1, 1]

Output2

Place each value v in slot v−1, then scan for the first index where nums[i] ≠ i+1.

nums (comma-separated)

def first_missing_positive(nums):
    n = len(nums)
    for i in range(n):
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            j = nums[i] - 1
            nums[i], nums[j] = nums[j], nums[i]
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

function firstMissingPositive(nums) {
  const n = nums.length;
  for (let i = 0; i < n; i++) {
    while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const j = nums[i] - 1;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return n + 1;
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int j = nums[i] - 1;
                int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) return i + 1;
        }
        return n + 1;
    }
}

int firstMissingPositive(vector<int>& nums) {
    int n = nums.size();
    for (int i = 0; i < n; i++) {
        while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
            swap(nums[i], nums[nums[i] - 1]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (nums[i] != i + 1) return i + 1;
    }
    return n + 1;
}

Explanation

The answer must be one of 1, 2, …, n, n+1 (with n the array length), because n numbers can cover at most that many positives. The trick is to use the array itself as a hash table by putting each value v into slot v - 1, so we need no extra space. This is called cyclic sort.

In phase 1, for each position we keep swapping the current value into its correct home as long as it is in range 1..n and not already there. The condition nums[nums[i] - 1] != nums[i] stops us from swapping when the home already holds the right value, which avoids infinite loops with duplicates.

After all the swapping, every value that can be in its home v - 1 is there. In phase 2 we scan for the first index i where nums[i] != i + 1. That gap is the smallest missing positive, i + 1. If every slot matches, the answer is n + 1.

Example: nums = [3, 4, -1, 1]. Sorting in place gives roughly [1, -1, 3, 4]. Scanning, index 0 holds 1 (good), but index 1 should hold 2 and does not, so the answer is 2.

Although there is a nested loop, each value is moved into place at most once, so the total work stays linear with no extra memory.

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