First Missing Positive

▶

Steps

setup

Initialize variables and start first loop

We start by setting n to the length of the array and initializing the index i to 0 to begin the first iteration over the array.

💡 Setting up the loop index and array length is essential to control the iteration over the array elements.

Line:

n = len(nums)
i = 0

💡 The algorithm will process each element to place it in its correct position if possible.

compare

Check if nums[i] = 3 is in range and not at correct position

At index i=0, the value is 3. Since 3 is between 1 and n=4, and nums[2] != 3 (nums[2] = -1), we decide to swap nums[0] with nums[2].

💡 This step checks if the current number can be placed at its correct index (value 3 should be at index 2).

Line:

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:

💡 Numbers in the valid range should be placed at index value-1 to organize the array.

swap

Swap nums[0] and nums[2]

We swap the values at indices 0 and 2. The array changes from [3, 4, -1, 1] to [-1, 4, 3, 1].

💡 Swapping places the number 3 at its correct index 2, moving closer to a sorted arrangement.

Line:

nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

💡 Swapping corrects the position of one number without advancing i, to check the new number at i.

compare

Check nums[0] = -1, not in range, move i forward

Now at i=0, nums[0] = -1 which is not in the range [1,4], so no swap is done and we move i to 1.

💡 Numbers outside the valid range are ignored since they cannot be placed correctly.

Line:

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
    # condition fails, move on

i += 1

💡 Only positive numbers within the array length are rearranged; others are left as is.

compare

Check nums[1] = 4 in range and not at correct position

At i=1, nums[1] = 4 is in range and nums[3] != 4 (nums[3] = 1), so we swap nums[1] and nums[3].

💡 We try to place 4 at index 3, its correct position, by swapping.

Line:

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:

💡 The algorithm continues to place each valid number at its correct index.

swap

Swap nums[1] and nums[3]

Swap values at indices 1 and 3. The array changes from [-1, 4, 3, 1] to [-1, 1, 3, 4].

💡 Placing 4 at index 3 puts it in the correct position.

Line:

nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

💡 Swapping moves the correct number into place and brings a new number to check at index i.

compare

Check nums[1] = 1 in range and not at correct position

At i=1, nums[1] = 1 is in range but nums[0] != 1 (nums[0] = -1), so we swap nums[1] and nums[0].

💡 We try to place 1 at index 0, its correct position, by swapping.

Line:

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:

💡 The algorithm continues to place each valid number at its correct index.

swap

Swap nums[1] and nums[0]

Swap values at indices 1 and 0. The array changes from [-1, 1, 3, 4] to [1, -1, 3, 4].

💡 Placing 1 at index 0 puts it in the correct position.

Line:

nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]

💡 Swapping moves the correct number into place and brings a new number to check at index i.

compare

Check nums[1] = -1 not in range, move i forward

At i=1, nums[1] = -1 is not in the range [1,4], so no swap is done and we move i to 2.

💡 Numbers outside the valid range are ignored since they cannot be placed correctly.

Line:

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
    # condition fails, move on

i += 1

💡 Only positive numbers within the array length are rearranged; others are left as is.

compare

Check nums[2] = 3 in range and at correct position

At i=2, nums[2] = 3 is in range and nums[2] == 3, so no swap is needed. Move i to 3.

💡 When the number is already at its correct index, we simply move forward.

Line:

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
    # condition fails, move on

i += 1

💡 Correctly placed numbers are left untouched.

compare

Check nums[3] = 4 in range and at correct position

At i=3, nums[3] = 4 is in range and nums[3] == 4, so no swap is needed. First loop ends.

💡 The last element is also correctly placed, so the first loop completes.

Line:

while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
    # condition fails, move on

i += 1

💡 All possible numbers are now placed correctly or ignored.

traverse

Start second loop to find first missing positive

We start scanning the array from index j=0 to find the first index where nums[j] != j+1.

💡 This loop identifies the smallest missing positive integer by checking the rearranged array.

Line:

for j in range(n):

💡 The first mismatch between value and index+1 indicates the missing positive.

compare

Check if nums[0] == 1

At j=0, nums[0] = 1 which equals j+1 = 1, so we continue to next index.

💡 If the value matches the expected number, the missing positive is not here.

Line:

if nums[j] != j + 1:

💡 Positions with correct values are not missing numbers.

compare

Check if nums[1] == 2

At j=1, nums[1] = -1 which does not equal j+1 = 2, so we found the first missing positive integer: 2.

💡 Mismatch indicates the smallest missing positive integer is j+1.

Line:

if nums[j] != j + 1:
    return j + 1

💡 The first index where value != index+1 reveals the missing positive integer.

def firstMissingPositive(nums):
    n = len(nums)  # STEP 1
    i = 0  # STEP 1
    while i < n:  # STEP 1
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:  # STEP 2,5,7,13
            nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]  # STEP 3,6,8
        else:
            i += 1  # STEP 4,9,10,11
    for j in range(n):  # STEP 12
        if nums[j] != j + 1:  # STEP 13,14
            return j + 1  # STEP 14
    return n + 1

📊

First Missing Positive - Watch the Algorithm Execute, Step by Step

Watching each swap and pointer movement helps you understand how the cyclic sort places numbers in their correct positions, revealing the missing positive integer without extra space.

traverse

i

3

0

4

1

-1

2

1

3

compare

i

3

0

4

1

target

-1

2

1

3

swap

i

-1

0

4

1

target

3

2

1

3

move_right

-1

0

i

4

1

3

2

1

3

compare

-1

0

i

4

1

3

2

target

1

3

swap

target

-1

0

i

1

1

3

2

4

3

compare

target

-1

0

i

1

1

3

2

4

3

swap

1

0

i

-1

1

3

2

4

3

move_right

1

0

-1

1

i

3

2

4

3

move_right

1

0

-1

1

3

2

i

4

3

traverse

1

0

-1

1

3

2

4

3

traverse

j

1

0

-1

1

3

2

4

3

compare

1

0

j

-1

1

3

2

4

3

compare

1

0

j

-1

1

3

2

4

3

Result: 2

Key Takeaways

✓ The cyclic sort rearranges the array so that each number is placed at the index corresponding to its value minus one.

This insight is hard to see from code alone because the swapping happens inside a nested while loop that can be confusing without visualization.

✓ Numbers outside the range [1, n] are ignored because they cannot affect the smallest missing positive integer within the array length.

Understanding this helps learners see why negative numbers and zeros do not interfere with the sorting process.

✓ The first index where the value does not match index + 1 after rearrangement reveals the smallest missing positive integer.

This concrete example shows how the algorithm efficiently finds the missing number without extra space or sorting the entire array.

Practice

1. Given the following code snippet implementing the cyclic sort approach, what is the returned output when the input array is [2, 2, 3]?

easy

A. [2, 1]

B. [2, 1]

C. [2, 1]

D. [2, 1]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [2, 2, 3]. i=0, nums[0]=2, correct_index=1. nums[0] == nums[1], so increment i to 1. i=1, nums[1]=2, correct_index=1, same index, increment i to 2. i=2, nums[2]=3, correct_index=2, correct place, increment i to 3.

2. Step 2: Identify mismatch in final array

   Final array remains [2, 2, 3]. Check indices: i=0 expects 1 but has 2 (duplicate), i=1 expects 2 and has 2 (correct), i=2 expects 3 and has 3 (correct). The mismatch at i=0 means duplicate=2, missing=1.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Output matches expected corrupt pair [2, 1] [OK]

Hint: Trace swaps carefully; duplicates cause no swap but increment index [OK]

Common Mistakes:

• Off-by-one in indexing
• Returning wrong pair order
• Missing increment after swap

2. What is the time complexity of the cyclic sort approach for finding the corrupt pair in an array of size n with one duplicate and one missing number?

medium

A. O(n log n) due to sorting inside the algorithm

B. O(n^2) because of nested loops swapping elements repeatedly

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

D. O(n) because each element is swapped at most once

Solution

1. Step 1: Identify the main loop behavior

   The while loop runs with index i from 0 to n-1, but swaps only occur when elements are out of place, and each swap places at least one element correctly.

2. Step 2: Analyze swap count and increments

   Each element can be swapped at most once to its correct position, so total swaps ≤ n. The index increments ensure no infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

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

Hint: Each element swapped once -> O(n) time [OK]

Common Mistakes:

• Assuming sorting inside algorithm
• Thinking swaps cause O(n^2)
• Confusing auxiliary space with time

3. What is the time complexity of the optimal approach that uses cyclic sort combined with a boolean array to find the first k missing positive numbers in an array of size n?

medium

A. O(n * k) due to nested loops scanning for missing numbers

B. O(n + k) because cyclic sort is O(n) and scanning for missing numbers is O(k)

C. O(n log n) due to sorting inside cyclic sort

D. O(n + k + n*k) due to extra space scanning

Solution

1. Step 1: Analyze cyclic sort complexity

   Cyclic sort runs in O(n) because each number is swapped at most once to its correct position.

2. Step 2: Analyze missing number scanning

   Scanning for missing numbers and filling missing list takes O(k) time, as it may extend beyond array length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum of O(n) + O(k) = O(n + k) [OK]

Hint: Cyclic sort is linear; extra scanning adds O(k) [OK]

Common Mistakes:

• Assuming sorting inside cyclic sort causes O(n log n)
• Confusing nested loops causing O(n*k)
• Ignoring that scanning missing numbers is linear in k

4. Consider the following buggy implementation of the cyclic sort approach to find the smallest missing positive range. Identify the line that contains the subtle bug causing incorrect results or infinite loops.

def find_smallest_missing_range(nums):
    n = len(nums)
    i = 0
    while i < n:
        correct_pos = nums[i] - 1
        if 1 <= nums[i] <= n and nums[i] != nums[correct_pos]:
            nums[i], nums[correct_pos] = nums[correct_pos], nums[i]
            # Missing increment of i here
        else:
            i += 1
    start = 1
    for i in range(n):
        if nums[i] != i + 1:
            start = i + 1
            break
    else:
        return [n + 1, n + 1]
    end = start
    while end <= n and nums[end - 1] != end:
        end += 1
    return [start, end - 1]

medium

A. Line missing increment of i after swap inside the while loop

B. Line with the swap: nums[i], nums[correct_pos] = nums[correct_pos], nums[i]

C. Line checking if nums[i] != i + 1 in the for loop

D. Line returning [n + 1, n + 1] if no missing range found

Solution

1. Step 1: Identify the infinite loop cause

   After swapping, the index i is not incremented, so the same index is checked repeatedly causing infinite loop.

2. Step 2: Confirm other lines are correct

   Swap line correctly swaps elements; the for loop and return lines handle missing range detection properly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing i increment after swap causes infinite loop or incorrect behavior [OK]

Hint: Always increment index after swap or carefully control loop [OK]

Common Mistakes:

• Forgetting to increment i after swap
• Misplacing swap condition

5. Suppose the input array can contain duplicate numbers and numbers outside the range 0 to n, or the array is immutable. Which modification to the cyclic sort approach correctly finds the missing number under these constraints?

hard

A. Use the sum formula approach since cyclic sort requires unique numbers and mutable array

B. Modify cyclic sort to skip numbers outside 0 to n and duplicates, swapping only valid numbers

C. Use a hash set to track all numbers and then find the missing one in O(n) time and O(n) space

D. Sort the array using built-in sort and scan for missing number, ignoring duplicates

Solution

1. Step 1: Understand constraints

   Duplicates and out-of-range numbers break cyclic sort assumptions; immutability prevents in-place swaps.

2. Step 2: Choose approach handling duplicates and immutability

   Hash set tracks presence without modifying input, handling duplicates and invalid numbers safely.

3. Step 3: Analyze tradeoffs

   Hash set uses O(n) space but guarantees correctness under constraints where cyclic sort fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Hash set approach works with duplicates and immutable inputs [OK]

Hint: Cyclic sort requires unique, mutable arrays [OK]

Common Mistakes:

• Trying to adapt cyclic sort without handling duplicates
• Assuming sum formula always works with duplicates
• Ignoring immutability constraints