Code Implementation

class Solution:
    def firstMissingPositive(self, nums):
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        return n + 1
      

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

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 temp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = temp;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1)
                return i + 1;
        }
        return n + 1;
    }
}
      

var firstMissingPositive = function(nums) {
    let n = nums.length;
    for (let i = 0; i < n; i++) {
        while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
            let temp = nums[nums[i] - 1];
            nums[nums[i] - 1] = nums[i];
            nums[i] = temp;
        }
    }
    for (let i = 0; i < n; i++) {
        if (nums[i] !== i + 1)
            return i + 1;
    }
    return n + 1;
};
      

Problem Description

You are given an unsorted integer array called nums. The task is to find the smallest missing positive integer from this array. The solution must run in linear time (O(n)) and use constant extra space (O(1)).

• Only positive integers matter (ignore zeros, negatives, and duplicates).
• Each input has exactly one solution.
• You cannot use extra data structures like hash sets or arrays proportional to n.
• Do not reuse array elements in a way that violates the in-place requirement.

For example, given nums = [3, 4, -1, 1], the answer is 2 because 1 is present, 2 is missing, and 3, 4 are present.

Thought Process

At first glance, you might think to sort the array or use a hash set to keep track of which positive numbers are present. However, sorting is O(n log n) and using a hash set requires extra space, both of which violate the problem's constraints.

The brute-force way would be to check for 1, then 2, then 3, and so on, but this is inefficient and doesn't meet the time complexity requirement.

The key insight is that the smallest missing positive number must be between 1 and n+1 (where n is the array's length). If all numbers from 1 to n are present, then the missing number is n+1.

The challenge is to find this missing number without extra space and in one pass. This leads to the idea of rearranging the array so that each positive integer x (where 1 <= x <= n) is placed at index x-1.

Solution Approach

To solve the problem efficiently, we use the input array itself as a kind of "hash map". The idea is to place each number x (where 1 <= x <= n) at position x-1. Here's how:

1. Iterate through the array: For each index i, if nums[i] is in the range 1 to n and not already in its correct position (nums[nums[i] - 1] != nums[i]), swap it with the element at its target position (nums[nums[i] - 1]).
2. Repeat swaps as needed: Keep swapping until the current position has either the correct number or an out-of-range number.
3. Final scan: After rearranging, scan the array from left to right. The first index i where nums[i] != i + 1 means i + 1 is missing.
4. Edge case: If all numbers from 1 to n are present, then the answer is n + 1.

This method works because every positive integer that can be placed in the array will be moved to its correct index. The rest (negatives, zeros, duplicates, or numbers > n) are ignored.

Example Walkthrough

Let's use nums = [3, 4, -1, 1] as an example.

1. Initial array: [3, 4, -1, 1]
2. First pass (placing numbers):
   • Index 0: 3 is in range. Swap 3 and -1 (at index 2). Array becomes [-1, 4, 3, 1]
   • Index 0: -1 is out of range. Move on.
   • Index 1: 4 is in range. Swap 4 and 1 (at index 3). Array becomes [-1, 1, 3, 4]
   • Index 1: 1 is in range. Swap 1 and -1 (at index 0). Array becomes [1, -1, 3, 4]
   • Index 1: -1 is out of range. Move on.
   • Index 2: 3 is already at index 2. Move on.
   • Index 3: 4 is already at index 3. Done.
3. Second pass (finding the missing number):
   • Index 0: 1 is correct.
   • Index 1: -1 is NOT 2. So, the missing number is 2.

The answer is 2.

Time and Space Complexity

• Brute-force approach:
  • Time: O(n^2) (for each positive integer, scan the array)
  • Space: O(1) (no extra data structures)
• Optimized approach (current solution):
  • Time: O(n). Each number is swapped at most once, so the total number of operations is linear.
  • Space: O(1). All operations are done in-place, with no extra storage proportional to n.

Summary

The problem asks for the smallest missing positive integer in an unsorted array, with strict time and space constraints. The elegant solution leverages in-place swapping to position each number at its "home" index. This approach efficiently transforms the input so that a single scan reveals the answer. The key insight is recognizing the relationship between values and their ideal indices, allowing us to avoid extra space and meet the linear time requirement.