Algorithm-Day17-First-Missing-Positive-lc-41

Posted on Edited on In , Views:

🧩 Problem Description

Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example:

1
2
Input: nums = [3,4,-1,1]
Output: 2

💡 Brute Force (Not Acceptable)

  • Sort the array → O(n log n)
  • Check for the first missing positive
  • ❌ Not allowed by problem constraints

💡 Optimal Approach: Index Placement (Cyclic Sort Pattern)

✨ Key Idea

  • If nums[i] is in range [1, n], ideally it should be placed at nums[nums[i] - 1].
  • Swap elements until every number is placed correctly.
  • Then scan once to find the first index i where nums[i] != i + 1.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]) {
                // Swap nums[i] with nums[nums[i] - 1]
                int temp = nums[i];
                nums[i] = nums[temp - 1];
                nums[temp - 1] = temp;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        return n + 1;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(n)
    Each number is swapped at most once.
  • Space Complexity: O(1)
    In-place swaps only.

✍️ Summary

  • This is a textbook application of the cyclic sort pattern.
  • Focus on the fact that only numbers within [1, n] matter.
  • Understand why O(n) solutions are possible by leveraging in-place swaps.

Problems like this appear often in data structure interviews where array indexing and in-place manipulation are tested.