First Missing Positive Integer (O(n) Time, O(1) Space)

Problem: Given an unsorted integer array, find the smallest missing positive integer, in O(n) time and O(1) extra space.

Constraints: Array can contain negatives, zeros, duplicates, and numbers larger than n (the array length).

Example: Input: [3,4,-1,1] -> Output: 2. Input: [1,2,0] -> Output: 3.

Approach: Use the array itself as an implicit hash map via index placement (cyclic sort): for each value v in the range [1..n], swap it into index v-1 if not already correctly placed there. Then scan left to right; the first index i where nums[i] != i+1 gives the answer i+1; if every position matches, the answer is n+1.