56-First-Missing-Positive.md

First Missing Positive

Problem Link

https://leetcode.com/problems/first-missing-positive/

---

Pattern

• Index Marking

---

Approach

Place each number n at index n-1 by swapping; then first index i where nums[i] != i+1 is the answer.

---

Time Complexity

O(n)

Space Complexity

O(1)

---

Java Solution

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