Skip to content

First Missing Positive

Topic: 01. Basics (Cyclic Sort)

Link: LeetCode 41 - First Missing Positive

1. Logical Breakdown

  • [x] Core Logic: Map value x to index x-1.
  • [x] Pattern: Cyclic Sort.

2. Visualization

graph TD A["Start i = 0"] --> B["i < N?"] B -- Yes --> C["Is nums[i] in Range & Misplaced?"] C -- Yes --> D["Swap nums[i] with correct spot"] D --> B C -- No --> E["Increment i"] E --> B B -- No --> End["Scan for Missing"]

3. Complexity

  • Time: O(N)
  • Space: O(1)

4. Code

package com.dsa.basics;

public class FirstMissingPositive {
    public int solve(int[] nums) {
        int n = nums.length;
        int i = 0;
        // Cyclic Sort: Place nums[i] at index nums[i]-1
        while (i < n) {
            int correct = nums[i] - 1;
            if (nums[i] > 0 && nums[i] <= n && nums[correct] != nums[i]) {
                int temp = nums[i];
                nums[i] = nums[correct];
                nums[correct] = temp;
            } else {
                i++;
            }
        }
        // Find the first index missing its number
        for (int j = 0; j < n; j++) {
            if (nums[j] != j + 1) return j + 1;
        }
        return n + 1;
    }
}