• 1 <= nums.length <= 10⁵
• -2³¹ <= nums[i] <= 2³¹ - 1
• Constraint: O(n) time and O(1) space.

Cyclic Sort is a powerful pattern for problems where the input array contains a range of numbers, typically from 1 to N. The key insight is simple: if we know the values are in a specific range, we also know exactly where each value belongs.

In an "ideal" sorted array of range [1, N]:
- The number 1 belongs at index 0
- The number 2 belongs at index 1
- The number x belongs at index x - 1

Instead of comparing elements against each other (like in Quick Sort), we iterate through the array and check if the current number is at its "home" index. If it isn't, we swap it with whatever is currently at its home. We repeat this until the current index holds the correct number.

Imagine an array of size 4 containing [3, 1, 4, 3] (where numbers should be 1 to 4). We use a simple loop to place every number in its "home":

# Basic Cyclic Sort for range [1, N]
i = 0
WHILE i < n:
    correct_idx = nums[i] - 1
    # If the number is not at its correct home...
    IF nums[i] != nums[correct_idx]:
        SWAP(nums[i], nums[correct_idx])
    ELSE:
        i += 1

After the swaps, the array becomes [1, 3, 3, 4]. By scanning the result, we see that at index 1, there is a 3 instead of the expected 2. Conclusion: 2 is missing, and the 3 at index 1 is a duplicate.

While the 1-to-N case is straightforward, the "First Missing Positive" problem adds a layer of complexity: the array can contain negative numbers, zeros, and values much larger than the array size (N).

We can still use the Cyclic Sort logic by simply ignoring the "noise". We treat the array as a restricted hash map that only cares about the range [1, n].

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Place nums[i] in its correct home index: nums[i] - 1
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            target_idx = nums[i] - 1
            nums[i], nums[target_idx] = nums[target_idx], nums[i]
            
    # First index that doesn't hold (index + 1) is the missing value
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
            
    return n + 1

Other O(N) techniques like "Sum of Range" or "XOR" fail here because the array can contain negative numbers and duplicates that disrupt the math. Cyclic Sort is purely structural—it physically moves elements to where they would be in a sorted array, making the "missing" slot immediately visible.

> Complexity Note: While there is a while loop inside a for loop, each swap puts at least one number into its final correct position. Since a number is only moved once, the total number of swaps is at most N, keeping the overall complexity O(N).