41. First Missing Positive - Detailed Explanation

Explanation: The code uses a while-loop to continually swap nums[i] into its correct position (index nums[i]-1) as long as nums[i] is a value between 1 and n and not already positioned correctly. After this first phase, it scans for the first index j where nums[j] != j+1 and returns j+1 as the answer. We copy the list with nums[:] when printing results to avoid modifying the original test list for subsequent tests.

Java Implementation

Complexity Analysis

Let’s summarize the time and space complexity for each approach discussed:

• Brute Force Approach: Time O(n^2), Space O(1).
  Explanation: For each candidate number (up to n+1 in worst case), we scan the array of length n to check if it’s present. This nested operation makes it quadratic time. No extra space besides a few counters is used.

• Using Extra Space (HashSet/Boolean Array): Time O(n) on average, Space O(n).
  Explanation: Building the set or boolean array is O(n), and checking from 1 to n+1 is O(n) in worst case. Using a hash set assumes average O(1) membership checks. The space complexity is linear because of the additional data structure that can hold up to n elements or n booleans.

• Sorting-Based Approach: Time O(n log n), Space O(1) (or O(n) depending on sort implementation).
  Explanation: Sorting dominates the time complexity. After sorting, scanning for the missing positive is O(n). Space depends on the sorting algorithm (in-place sorts use constant extra space, but some languages use O(n) space for sorting). We count it as O(1) extra for simplicity here, not including the output or input storage.

• Optimal In-Place Approach (Cyclic Sort Index Placement): Time O(n), Space O(1) .
  Explanation: We perform at most n swaps and at most 2n total loop iterations (n for the initial placement loop and n for the checking loop), which is linear. Space is constant because we reorganize the array in place and only use a few index/temp variables. This meets the strict requirements of the problem.

Comparison: The in-place approach is clearly the best in terms of Big-O for large input sizes, as it scales linearly. The sorting approach is a close second in terms of simplicity but is slower for very large n. The hash set approach is linear time but fails the space constraint (which might be fine in practical scenarios with ample memory). The brute force approach is mostly theoretical here to illustrate the basic idea – it would be too slow on large inputs.

Step-by-Step Walkthrough of the Optimal Solution

Let's walk through the Optimal In-Place (Approach 4) with a detailed example to see how it works in action. We’ll use a tricky example that covers various cases (out-of-range values, negatives, needing multiple swaps):

Example: nums = [3, 4, -1, 1] (from Example 2)

Initial array (with indices for clarity):

Index:  0   1   2   3
Value: [3,  4, -1,  1]
n = 4

We expect the answer to be 2 for this input. Let’s see how the algorithm finds that.

Phase 1: Place numbers in correct positions via swapping.

We iterate i from 0 to 3.

• i = 0:

  • Current value nums[0] = 3.
  • 3 is in the range 1..4 and not at its correct position. The correct index for value 3 is 3 - 1 = 2.
  • The value at index 2 is -1. We swap the values at index 0 and index 2.

  After swap:

  Index:  0    1   2   3
  Value: [-1,   4,  3,  1]
  

  Now, at index 0 we have -1. We will re-check index 0 in the while-loop:

  • nums[0] = -1, which is not in 1..4 (it's out of range), so we stop swapping at i=0.
  • (Index 0 now holds an "irrelevant" value -1 that we can ignore from now on. Essentially, index 0 didn't get a correct positive placed because 1 was missing from the array, which we'll discover later.)

• i = 1:

  • nums[1] = 4.
  • 4 is in range 1..4 and not at its correct position (correct index for 4 is 4-1 = 3).
  • Value at index 3 is 1. Swap index 1 and index 3.

  After swap:

  Index:  0   1   2   3
  Value: [-1,  1,  3,  4]
  

  Now, nums[1] has become 1 (after the swap). We continue the while-loop for index 1:

  • nums[1] = 1, which is in range and should be at index 1-1 = 0.
  • Value at index 0 is -1. Swap index 1 with index 0.

  After swap:

  Index:  0   1   2   3
  Value: [ 1, -1,  3,  4]
  

  Now, nums[1] is -1. -1 is out of range, so we stop swapping at i=1.

  • What happened here is that we successfully placed 1 into its correct slot (index 0). Index 1 now has -1 (an out-of-range placeholder) after placing 1 where it belongs.

• i = 2:

  • nums[2] = 3.
  • 3 is in range and should be at index 2 (since 3’s correct index is 2). Is it already there? Yes, nums[2] is 3 and index 2 corresponds to value 3 (which means this is correct, nums[2] == 3 and we expect 3 at index 2).
  • So nums[2] is already in the right place. No swap needed. Move on.

• i = 3:

  • nums[3] = 4.
  • 4 is in range and should be at index 3. It is indeed at index 3 already (nums[3] == 4).
  • No swap needed.

After the first phase, the array has been rearranged to:

Index:  0   1   2   3
Value: [ 1, -1,  3,  4]

Let's interpret this state:

• At index 0, we have 1. Ideally, we want nums[0] == 1 for the array to be "complete" from 1... That is correct.

• At index 1, we would want nums[1] == 2 if 2 were present. But we have -1 (which is just a leftover non-positive number). This indicates that 2 was never placed in the array – likely because 2 is not in the array at all.

• Index 2 has 3 (correct, since we want nums[2] == 3).

• Index 3 has 4 (correct, since we want nums[3] == 4).

We can already see that index 1 is out-of-place (it doesn’t have 2). The algorithm will detect that in the next phase.

Phase 2: Find the first index with a mismatch.

Now we do a linear scan to find the first index j such that nums[j] != j+1:

• j = 0: Check nums[0] against 1. Here nums[0] = 1, and 1 == 1 (expected value), so index 0 is fine.

• j = 1: Check nums[1] against 2. We find nums[1] = -1, and this is not equal to 2 (the value that should be here if everything from 1 up to 2 were present). This is the first discrepancy.
  This means 2 is missing. We immediately identify that the smallest missing positive is j+1 = 1+1 = 2. We can return 2.

We don’t need to check further indices once we found the first mismatch. The answer for this example is indeed 2.

This walkthrough shows how the array is rearranged so that each index tries to hold the correct number (index + 1). Any index that fails to have the correct number indicates the missing positive. In our example, index 1 failed to have 2, hence 2 was missing.

Additional thoughts on this approach with different scenarios:

• If the array were something like [1,2,3] (already containing 1 through n), the rearrangement phase would leave it unchanged (each index already has the correct value). The second phase would check index0 (has 1, good), index1 (has 2, good), index2 (has 3, good) and then finish the loop and return n+1 which is 4. This correctly handles the case where the array contains all numbers from 1 to n.

• If the array starts without 1 (e.g., [2,3,4] for n=3), then:

  • During placement: 2 and 3 will get placed to indices 1 and 2, and 1 is never placed (since it doesn’t exist in the array, index 0 will remain with an out-of-range number like 4 or something after swaps).
  • In the second phase, at index 0 we’ll find nums[0] != 1 and return 1 immediately. This handles the case where 1 is missing (the answer is 1, the smallest positive).

• Duplicate values don’t break the algorithm: if a number is duplicated, the swap condition nums[i] != nums[nums[i]-1] will fail once the duplicate is in place, preventing an infinite loop. For example, [1,1]: at i=0, we won’t swap because nums[0] == nums[nums[0]-1] (both are 1). The algorithm will then move on, and in phase 2, index 1 will be mismatched (expect 2, found 1), yielding 2 as answer.

The in-place approach is robust and covers all these scenarios systematically.

Common Mistakes & Edge Cases

When implementing this solution (or similar ones), it’s easy to run into some pitfalls. Here are common mistakes and important edge cases to watch out for:

Common Pitfalls:

• Infinite Loop in Swap: If the swap logic is not implemented carefully, you could end up in an infinite loop. For instance, forgetting to check the condition nums[i] != nums[nums[i] - 1] before swapping can cause a case where you keep swapping the same two equal values back and forth. The condition ensures that if a number is already in its correct place (or a duplicate is already placed at its target), we don't swap endlessly.

• Using incorrect index calculations: Remember that the target index for a value x is x-1 (because of 0-based indexing). Off-by-one errors can lead to either index out-of-bound errors or incorrect placement. Double-check indexing math.

• Skipping elements during swap: When a swap occurs, do not increment the index i immediately. The swapped in value at nums[i] needs to be processed in the next iteration of the while-loop at the same index. Some implementations mistakenly increase i inside the loop, which can skip processing a value that was just swapped in. In our approach, we use a while loop specifically to handle this – we only move i forward in the outer for loop when the current position is settled.

• Not accounting for values out of range: It’s important to only swap values that are in the range 1..n. If you don't check nums[i] <= n and nums[i] >= 1, you might try to place an out-of-range value into an index that doesn't exist, causing errors. We explicitly ignore values <= 0 or > n by not entering the swap loop for them (treating them as already "in place" in a sense that they’re in a useless spot).

• Forgetting the final case (n+1): After rearranging and checking the array, if all positions 1 through n are filled correctly, the answer is n+1. A common mistake is to not handle this and thus miss the scenario where the array contains all smaller positives. For example, if nums = [1,2,3], a faulty solution might not return 4. In our implementations, we return n+1 if no missing index is found in the second loop.

Important Edge Cases:

• Array of length 1: e.g., [1] or [2].

  • If the array is [1], the answer should be 2 (since 1 is present, next positive missing is 2).
  • If the array is [2] (or any value not 1), the answer should be 1 (because 1 is missing). Our algorithm handles this: it will not swap anything, and in the check phase, index 0 expects 1 but finds 2, so it returns 1.

• All non-positive or large values: e.g., [-1, -2] or [100, 200].

  • These contain no positive numbers in the range 1..n at all. The smallest missing positive is 1 in such cases. The in-place algorithm will essentially ignore all values (since none are in 1..n) and then immediately find index 0 is wrong (expecting 1 but it's something else or unchanged), returning 1.

• Already sorted or consecutive sequence: e.g., [1,2,3,4].

  • Here, the answer should be 5. The algorithm will place everything (they are already placed), then after checking all indices correct, return n+1 which is 5.

• Missing number in the middle: e.g., [1,2,4,5] (missing 3).

  • The algorithm will place 1 and 2 correctly, place 4 and 5 (5 is out of range if n=4, so it will be ignored or treated as placeholder), and then find index 2 has 4 instead of 3, returning 3.

• Duplicates and unsorted mix: e.g., [2, 2, 1, 1].

  • Duplicates should not confuse the algorithm. In this example, after placement, we should end up with [1, 2, ...] in the first two indices (the exact content of later indices isn't important), and the answer will be 3. The algorithm's swap logic naturally handles duplicates by not swapping a number into a position that already holds the same number.

• Largest values present: e.g., an array containing values like [1, 2, ..., n] where n is the length.

  • We covered this: the answer is n+1, which the algorithm returns after verifying all positions.

By considering these edge cases, we ensure the solution is robust. The provided code examples handle all these cases correctly.

Alternative Variations

The problem of finding the first missing positive is a classic application of using array indexing tricks to achieve linear time without extra space. Here are some variations and related insights:

• Alternate Optimal Solution (Marking Technique): Instead of swapping elements in place, another common approach for this problem is to mark the presence of numbers by using the array indices as flags. For example, one can:

  1. First, replace any number that is out of range (<=0 or >n) with a dummy value like n+1. This way, all numbers in the array are now positive and within a manageable range.
  2. Then, for each number x in the array (now all are >0), if 1 <= x <= n, mark its presence by making the value at index x-1 negative (multiply by -1 as a flag, for instance).
  3. Finally, the first index that has a positive value indicates the missing number (because its index was never marked), otherwise if all indices 0..n-1 are marked (negative), answer is n+1.

  This approach achieves the same O(n) time and O(1) space goal without explicit swapping. It’s a bit trickier to implement correctly (handling the sign flips carefully and not double-flipping a value). The swapping method and the marking method are two sides of the same coin – both effectively use the array itself to track presence/absence of numbers.

• Cyclic Sort Technique: The approach we used is an example of the cyclic sort technique, which is broadly useful in problems dealing with finding missing or duplicate numbers in a range. The idea is to repeatedly swap misplaced elements until everything that can be placed correctly is placed. This technique can be applied to similar problems (see related problems below).

• Different ranges or k-th missing: A variation of missing positive problems is finding the k-th missing positive number, or the smallest missing in a different range. For instance, there's a problem where given a sorted array of positive numbers, you need to find the k-th missing positive (which can be solved via binary search or two-pointer since the array is sorted). That is a different scenario because the input is sorted and you allow skipping larger gaps. It uses a different approach (counting gaps), but it’s related in the sense of reasoning about "missing" values.

• Multiple missing numbers: Sometimes you might be asked to find all missing numbers in a range (not just the first). One can extend these ideas to gather all missing positives (for example, LeetCode’s "Find All Numbers Disappeared in an Array" asks for all missing numbers from 1..n). The marking technique can be easily extended to collect all such indices. The cyclic sort can also be extended: after placement, scan and collect all indices where nums[i] != i+1 to get all missing numbers.

• Using similar index placement for duplicates: A related class of problems uses a similar concept to find duplicates. For example, to find a duplicate number in an array, you can swap or mark as you traverse. One known problem is to find the one duplicate in an array of length n+1 where numbers are in [1..n]; this can be done by placing numbers and seeing which index ends up with the wrong number (or via Floyd’s cycle detection). The index marking (negation) trick is often used to find duplicates by seeing if an index was visited twice (you’d find a value already negative).

In summary, the technique used in "First Missing Positive" is widely applicable. The essence is: when you have a range of integers [1..n] and you want to find something missing or duplicate, consider using the array’s indices as a proxy for those values. Either place each value at its index or mark the index when a value is seen. This way, you can avoid extra space. Many array problems of this nature can be tackled with this mindset.

Related Problems for Further Practice

To strengthen your understanding, you can practice these related LeetCode problems that involve similar concepts:

• LeetCode 268. Missing Number: Given an array of size n containing numbers from 0 to n, find the one number missing from 0..n. (This is simpler than First Missing Positive because here the range is 0..n and only one number is missing with no extra negatives or large values. Can be solved with sum/XOR or similar index ideas.)

• LeetCode 448. Find All Numbers Disappeared in an Array: Given an array of length n with numbers in 1..n (some appear, some missing, some may repeat), find all the numbers in [1..n] that are not in the array. (This can be solved by using the same index marking technique by negating values at indices. It’s like finding all missing positives instead of just the first one.)

• LeetCode 442. Find All Duplicates in an Array: Given an array of length n with numbers in 1..n, some appear twice, find all duplicates. (Can also be solved with a similar marking strategy: when you encounter a number, flip the sign at its index; if you find it’s already negative, that number is a duplicate. Or using cyclic sort and checking mismatches.)

• LeetCode 645. Set Mismatch: An array of length n contains numbers 1..n but one number is missing and another is duplicated. Find the duplicate and the missing. (This is a combination of missing and duplicate finding; you can use index placement or marking to detect both anomalies in one pass.)

• LeetCode 41. First Missing Positive: (The problem we just solved – listed here for completeness, as many lists include the problem itself as a reference.)

• LeetCode 1539. Kth Missing Positive Number: Given a sorted array of positive integers and an integer k, find the k-th positive integer that is missing from the array. (This is a different twist: the input is sorted and you have to count missing numbers until you reach the k-th one. It uses a different approach, typically a binary search or linear scan counting gaps, since the array is sorted. It’s good to see the contrast in approach when the input conditions change.)