---

1. Problem Summary

You are given an integer array nums.
Your task is to find the smallest positive integer (greater than 0) that does not appear in the array.

Important characteristics:

• The number must be positive (1, 2, 3, …)
• The array may contain:
  • negative numbers
  • zeros
  • duplicates
  • large numbers beyond range of interest
• The required answer must be computed in:
  • O(N) time
  • O(1) extra space

Example interpretation:
For input [3, 4, -1, 1], the smallest missing positive is 2.

---

2. Key Insights

The answer is always in the range [1 … N+1]

Given array length = N:

• If array contains all numbers from 1 to N, then answer is N+1
• Otherwise, the missing number is within [1, N]

Ignoring irrelevant values

Numbers that are:

• ≤ 0
• greater than N
  cannot contribute to the missing result.

Use array indices as hash markers

We map value v to index v - 1.
If value exists, we mark its presence inside the array itself.

In-place marking method

To mark presence, we flip numbers to negative (or maintain sign).

Final scan identifies missing positive

The first index with a positive value indicates the missing number.

---

3. Approach

Step-by-step Strategy

Step 1: Replace invalid values

Convert all values ≤ 0 or > N to a placeholder (e.g., N+1)

Step 2: Mark presence

For each value v in array:

index = abs(v) - 1
if index in range:
    mark nums[index] as negative (if not already)

Step 3: Find first missing positive

Scan from index 0 onward:

• first index i with positive value → answer = i + 1

Step 4: If all marked

Return N + 1

---

4. Time and Space Complexity

Time Complexity: O(N)

• Single pass normalize
• Single pass mark
• Single pass detect

Space Complexity: O(1)

• In-place marking
• No extra data structures

---

5. Java Solution

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // Step 1: Clean values outside range
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0 || nums[i] > n) {
                nums[i] = n + 1;
            }
        }

        // Step 2: Mark presence using index
        for (int i = 0; i < n; i++) {
            int val = Math.abs(nums[i]);
            if (val >= 1 && val <= n) {
                int index = val - 1;
                if (nums[index] > 0) {
                    nums[index] = -nums[index];
                }
            }
        }

        // Step 3: Find first positive index
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        // Step 4: All present
        return n + 1;
    }
}

---

6. Dry Run Examples

Example 1

Input:

nums = [1, 2, 0]

Step 1 cleanup:

[1, 2, 3]  // 0 replaced with n+1 (3)

Step 2 marking:

• mark index 0 → [-1, 2, 3]
• mark index 1 → [-1, -2, 3]
• 3 out of range → ignore

Step 3 scan:
index 2 is positive → answer = 3

Output:

3

---

Example 2

Input:

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

Step 1 cleanup:

[3, 4, 5, 1]

Step 2 marking:

• val=3 → mark index 2 → [3, 4, -5, 1]
• val=4 → mark index 3 → [3, 4, -5, -1]
• val=5 ignored
• val=1 → mark index 0 → [-3, 4, -5, -1]

Step 3 scan:
index 1 is positive → answer = 2

Output:

2

---

Example 3

Input:

nums = [7, 8, 9, 11, 12]

Step 1 cleanup:

[6, 6, 6, 6, 6]  // all replaced

Step 2 marking:
none in range, nothing changes

Step 3 scan:
index 0 positive → answer = 1

Output:

1

---

Example 4

Input:

nums = [1, 2, 3, 4]

Process results in all marked → answer = N+1 = 5

Output:

5

---

7. Why This Solution Works

• Restricts search space to realistic bounds
• Uses array itself as presence map
• Marks only valid values
• Exactly matches O(N) and O(1) constraints
• Avoids sorting or hash sets
• Mathematically proven correctness

---

8. Common Mistakes

1. Sorting the array (O(N log N), fails constraints)
2. Using HashSet (extra space, fails constraints)
3. Ignoring negative or zero effects
4. Off-by-one indexing errors
5. Returning 0 (answer must be ≥ 1)