First Missing Positive

📋

First Missing Positive

Edge cases:

</>

IDE

def firstMissingPositive(nums: list[int]) -> int:public int firstMissingPositive(int[] nums)int firstMissingPositive(vector<int>& nums)function firstMissingPositive(nums)

def firstMissingPositive(nums):
    # Write your solution here
    pass

class Solution {
    public int firstMissingPositive(int[] nums) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int firstMissingPositive(vector<int>& nums) {
    // Write your solution here
    return 0;
}

function firstMissingPositive(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Returning 1 always without checking array contents.✅ Add logic to check presence of 1 and perform cyclic placement before returning 1.

Wrong: n+1 (wrong value)Returning n+1 without verifying if all numbers 1..n are present.✅ After cyclic placement, scan array to find first index i where nums[i] != i+1 and return i+1.

Wrong: Infinite loop or timeoutNot checking for duplicates before swapping causing infinite cycles.✅ Add condition to swap only if nums[i] != nums[nums[i]-1].

Wrong: Wrong missing positive due to ignoring negative or zero incorrectlyTrying to place negative or zero values in array indices.✅ Skip numbers <= 0 or > n during cyclic placement.

Wrong: Timeout on large inputUsing brute force membership checks or sorting instead of O(n) cyclic sort.✅ Implement cyclic sort to achieve O(n) time complexity.

✓

Test Cases

Focus on handling edge cases like empty arrays and single elements correctly.

Watch out for duplicates and numbers outside the valid range causing infinite loops.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[3,4,-1,1]}

Expected2

⏱ Performance - must finish in 2000ms

The numbers 1, 3, and 4 are present, but 2 is missing and is the smallest positive missing integer.

💡 Try placing each number in its correct index position if possible.

💡 Use cyclic sort to put numbers 1 to n at indices 0 to n-1.

💡 After placement, the first index i where nums[i] != i+1 is the answer.

Why it failed: Failed basic case: likely incorrect placement or missing check for nums[i] != i+1. Fix by ensuring cyclic swaps only for valid indices and checking final array correctly.

✓ Correctly identifies smallest missing positive in canonical example.

t1_02basic

Input{"nums":[1,2,0]}

Expected3

⏱ Performance - must finish in 2000ms

Numbers 1 and 2 are present, 3 is the smallest missing positive integer.

💡 Remember to ignore numbers <= 0 and > n during placement.

💡 After cyclic placement, scan to find first mismatch between index+1 and value.

💡 If all positions match, answer is n+1.

Why it failed: Incorrect output due to not ignoring invalid numbers or failing to return n+1 when all 1..n present. Fix by skipping invalid numbers and returning n+1 if no mismatch found.

✓ Correctly handles array with zero and returns next integer after max.

t2_01edge

Input{"nums":[]}

Expected1

⏱ Performance - must finish in 2000ms

Empty array means smallest missing positive is 1.

💡 Check behavior when input array is empty.

💡 Smallest positive integer missing from empty list is always 1.

💡 Return 1 immediately if array length is zero.

Why it failed: Fails empty input by not handling zero-length array. Fix by returning 1 if nums is empty.

✓ Correctly returns 1 for empty input.

t2_02edge

Input{"nums":[-1]}

Expected1

⏱ Performance - must finish in 2000ms

Single negative element means smallest missing positive is 1.

💡 Single element negative or zero means 1 is missing.

💡 Check single element edge case carefully.

💡 Return 1 if nums[0] is not 1.

Why it failed: Fails single negative element by returning wrong value. Fix by checking if nums[0] == 1, else return 1.

✓ Correctly returns 1 for single negative element.

t2_03edge

Input{"nums":[1]}

Expected2

⏱ Performance - must finish in 2000ms

Single element 1 means smallest missing positive is 2.

💡 Single element equal to 1 means next missing positive is 2.

💡 Check if nums[0] == 1 to decide return value.

💡 Return 2 if nums[0] == 1.

Why it failed: Fails single element 1 by returning 1 instead of 2. Fix by returning 2 if nums[0] == 1.

✓ Correctly returns 2 for single element 1.

t2_04edge

Input{"nums":[1,2,3,4,5]}

Expected6

⏱ Performance - must finish in 2000ms

Array with all consecutive positive numbers starting from 1; smallest missing positive is next integer after max.

💡 Check if all numbers from 1 to n are present.

💡 If yes, return n+1 as smallest missing positive.

💡 Scan array after placement to confirm.

Why it failed: Fails to return n+1 when all 1..n present. Fix by scanning array after placement and returning n+1 if no mismatch found.

✓ Correctly returns next integer after max for consecutive array.

t3_01corner

Input{"nums":[1,1,0,-1,-2]}

Expected2

⏱ Performance - must finish in 2000ms

Duplicates of 1 present, but 2 is missing and smallest positive missing integer.

💡 Duplicates should not cause infinite loops during cyclic swaps.

💡 Ensure to check if nums[i] != nums[nums[i]-1] before swapping.

💡 Add condition to avoid swapping duplicates to prevent infinite cycles.

Why it failed: Fails due to infinite loop or incorrect handling of duplicates. Fix by adding check to swap only if nums[i] != nums[nums[i]-1]. This is the duplicates handling test.

✓ Correctly handles duplicates without infinite loops.

t3_02corner

Input{"nums":[2,2,2,2]}

Expected1

⏱ Performance - must finish in 2000ms

All elements are 2, so 1 is missing and smallest positive missing integer.

💡 Check if 1 is present in the array.

💡 If 1 is missing, answer is 1 regardless of other values.

💡 Return 1 if no element equals 1.

Why it failed: Fails to detect missing 1 when all elements are duplicates > 1. Fix by checking presence of 1 before cyclic placement. This is the missing 1 detection test.

✓ Correctly returns 1 when 1 is missing.

t3_03corner

Input{"nums":[7,8,9,11,12]}

Expected1

⏱ Performance - must finish in 2000ms

All numbers are greater than array length, so smallest missing positive is 1.

💡 Ignore numbers greater than n during placement.

💡 Check if 1 is present before placement.

💡 Return 1 if 1 is missing or no valid placement possible.

Why it failed: Fails to ignore numbers > n causing wrong swaps or missing 1 detection. Fix by skipping numbers > n and checking for 1 presence. This is the boundary ignoring test.

✓ Correctly ignores out-of-bound numbers and returns 1.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100 with consecutive numbers 1 to 100 to test O(n) complexity solution within 2 seconds.

💡 Brute force O(n^2) will time out on large inputs.

💡 Use cyclic sort or index placement for O(n) time.

💡 Avoid nested loops and repeated membership checks.

Why it failed: TLE due to O(n^2) brute force or sorting approach. Fix by implementing O(n) cyclic sort algorithm.

✓ Algorithm runs in O(n) time confirming efficient complexity.

Practice

1. Identify the bug in the following cyclic sort implementation that aims to place numbers 1 to n at their correct indices:

def cyclic_sort_buggy(arr):
    i = 0
    n = len(arr)
    while i < n:
        correct_index = arr[i] - 1
        if arr[i] != arr[correct_index]:
            arr[i], arr[correct_index] = arr[correct_index], arr[i]
        i += 1
    return arr

What is the issue causing incorrect output or infinite loops?

medium

A. Incrementing i even after a swap causes some elements to remain misplaced.

B. Not checking if arr[i] is within 1 to n causes index errors.

C. Swapping elements without a temporary variable causes data loss.

D. Using a while loop instead of a for loop causes infinite loops.

Solution

1. Step 1: Analyze loop increment

   i is incremented unconditionally even after swapping, skipping re-check of swapped element.

2. Step 2: Understand impact

   Elements swapped in may still be misplaced but are not checked again, causing incorrect final array or infinite loops.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Increment i only when no swap occurs to ensure correct placement [OK]

Hint: Only increment index if no swap occurs [OK]

Common Mistakes:

• Always incrementing index after swap
• Ignoring index bounds
• Misusing loop constructs

2. What is the time complexity of the optimal cyclic sort approach to find all duplicates in an array of size n, and why might some candidates mistakenly think it is higher?

medium

A. O(n^2) because nested swaps can happen repeatedly

B. O(n log n) because of the sorting-like swaps

C. O(n) because each element is swapped at most once to its correct position

D. O(n) but with O(n) extra space for tracking duplicates

Solution

1. Step 1: Analyze the while loop behavior

   Each swap places at least one element in its correct position, so total swaps ≤ n.

2. Step 2: Understand why time is linear

   Since each element is moved at most once, total operations are O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Swapping each element once ensures linear time [OK]

Hint: Each element moves at most once -> O(n) time [OK]

Common Mistakes:

• Assuming swaps cause O(n^2) due to nested loops
• Confusing cyclic sort with comparison-based sorting
• Forgetting that extra space is O(1)

3. What is the time complexity of the optimal cyclic sort approach to find the duplicate and missing numbers in an array of size n, and why?

medium

A. O(n) because each element is swapped at most once to its correct position

B. O(n) but with O(n) extra space for auxiliary arrays

C. O(n^2) because of nested loops inside the while loop

D. O(n log n) because of sorting the array

Solution

1. Step 1: Identify the main loop behavior

   The while loop swaps elements to their correct positions. Each swap places at least one element correctly, so total swaps ≤ n.

2. Step 2: Analyze time complexity

   Since each element is moved at most once, the total operations are proportional to n, resulting in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time due to limited swaps and single pass [OK]

Hint: Each element moves at most once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting is involved -> O(n log n)
• Mistaking nested loops inside while as O(n^2)
• Forgetting swaps reduce total operations

4. Examine the following buggy implementation of the cyclic sort approach to find the missing number:

def missingNumber(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct = nums[i]
        if nums[i] != nums[correct]:  # Bug here
            nums[i], nums[correct] = nums[correct], nums[i]
        else:
            i += 1
    for i in range(n):
        if nums[i] != i:
            return i
    return n

What is the bug in this code?

medium

A. The condition misses checking if correct < n, causing index errors

B. The swap line incorrectly swaps nums[i] and nums[correct]

C. The increment i += 1 is inside the else block, causing infinite loops

D. The final for loop should return n-1 instead of n when no mismatch found

Solution

1. Step 1: Identify the missing boundary check

   The condition lacks 'correct < n' check, so if nums[i] == n, nums[correct] causes index out of range.

2. Step 2: Consequences of missing check

   Without this, the code may crash or loop infinitely when encountering the number n, which is outside array indices.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding 'correct < n' prevents out-of-bounds errors [OK]

Hint: Always check index bounds before accessing array [OK]

Common Mistakes:

• Forgetting boundary check leads to runtime errors
• Misplacing increment causing infinite loops
• Incorrect swap lines that look correct

5. Consider this buggy code snippet for finding the duplicate and missing numbers. Which line contains the subtle bug that can cause an infinite loop or incorrect result?

medium

A. Line 5: missing check before swapping

B. Line 3: initialization of i

C. Line 8: incrementing i

D. Line 10: returning the result

Solution

1. Step 1: Analyze the swapping condition

   Without checking if nums[i] == nums[correct], swapping duplicates causes infinite loops or incorrect swaps.

2. Step 2: Confirm other lines are correct

   Initialization, increment, and return lines are standard and not buggy here.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing conditional check before swap causes infinite loop [OK]

Hint: Always check if swap is needed to avoid infinite loops [OK]

Common Mistakes:

• Forgetting to check for duplicates before swapping
• Misplacing increment of index i
• Returning wrong values after loop