Find K Missing Positive Numbers

▶

Steps

setup

Initialize variables and start cyclic sort

Set n to the length of the array and initialize index i to 0 to start the cyclic sort process.

💡 Setting up these variables is essential to control the cyclic sort loop and know the array size.

Line:

n = len(arr)
i = 0

💡 We prepare to iterate through the array to place numbers at their correct indices.

fill_cells

Calculate correct index and swap if needed for arr[i]

Calculate the correct index for the current element and swap if it is not at the correct position and within valid range.

💡 Finding the correct index helps decide if a swap is needed to place the number correctly.

Line:

correct_index = arr[i] - 1
if 1 <= arr[i] <= n and arr[i] != arr[correct_index]:
    arr[i], arr[correct_index] = arr[correct_index], arr[i]

💡 Swapping moves numbers closer to their correct positions, a key step in cyclic sort.

fill_cells

Continue cyclic sort swaps or move i forward

Repeat calculating correct index and swapping if needed, or increment i if no swap is required or value is invalid.

💡 Swapping identical values is skipped to avoid infinite loops; invalid values are ignored.

Line:

if 1 <= arr[i] <= n and arr[i] != arr[correct_index]:
    arr[i], arr[correct_index] = arr[correct_index], arr[i]
else:
    i += 1

💡 This loop ensures all numbers are placed correctly or skipped if invalid.

fill_cells

Skip invalid values and increment i

At indices with invalid values (e.g., negative or duplicates), increment i to continue processing.

💡 Only positive numbers within array length are placed; others are ignored here.

Line:

else:
    i += 1

💡 Negative numbers and duplicates are skipped in cyclic sort.

fill_cells

Verify correct placement or move i forward

If the current number is already at its correct index, increment i to continue.

💡 If the number is already at the correct index, move i forward.

Line:

if arr[i] == arr[correct_index]:
    i += 1

💡 No swap needed as number is correctly placed.

fill_cells

Complete cyclic sort loop

Increment i beyond array length to finish cyclic sort phase.

💡 Loop ends when i reaches array length.

Line:

else:
    i += 1

💡 Cyclic sort phase is complete.

setup

Initialize missing list and extra_nums boolean array

Create an empty list to store missing numbers and a boolean array to track extra numbers beyond array length.

💡 These structures help collect missing numbers inside and outside the array range.

Line:

missing = []
extra_nums = [False] * (k + n + 1)

💡 We prepare to identify missing numbers efficiently.

traverse

Traverse array to find missing numbers within range and mark extras

At each index, check if the number is missing (not equal to expected) and add to missing list if needed. Also mark extra numbers beyond array length.

💡 Checking each index reveals which numbers are missing and which extras exist.

Line:

if arr[i] != i + 1 and len(missing) < k:
    missing.append(i + 1)
if arr[i] > n and arr[i] < len(extra_nums):
    extra_nums[arr[i]] = True

💡 We identify missing numbers inside the array and track extras beyond array range.

traverse

Continue traversal to add missing numbers and mark extras

At index 1, value -1 is invalid but missing number 2 is added. Continue for all indices similarly.

💡 Negative values are skipped for extra marking but count as missing numbers.

Line:

if arr[i] != i + 1 and len(missing) < k:
    missing.append(i + 1)

💡 We find missing number 2 inside the array range.

traverse

Skip correctly placed numbers during traversal

At indices 2, 3, and 4, values match expected positions, so no missing numbers are added but extras are marked if needed.

💡 Numbers correctly placed are not missing.

Line:

if arr[i] != i + 1 and len(missing) < k:
    missing.append(i + 1)
if arr[i] > n and arr[i] < len(extra_nums):
    extra_nums[arr[i]] = True

💡 Correctly placed numbers are skipped; extras tracked for final missing number search.

setup

Initialize next_num to start checking beyond array range

Set next_num to n + 1 to begin searching for missing numbers beyond the array length.

💡 We look for missing numbers greater than array length after checking inside range.

Line:

next_num = n + 1

💡 Start searching for missing numbers beyond the array.

traverse

Check if next_num is missing and add to missing list

Since extra_nums[6] is False (6 not in array), add 6 to missing list, completing the required K missing numbers.

💡 Numbers not marked in extra_nums are missing beyond array range.

Line:

if next_num >= len(extra_nums) or not extra_nums[next_num]:
    missing.append(next_num)

💡 We find the third missing number beyond the array.

traverse

Increment next_num but stop as missing list size reached K

Increment next_num to 7 but since missing list size equals K=3, stop searching for more missing numbers.

💡 Stop when required number of missing numbers are found.

Line:

next_num += 1

💡 We have found all K missing numbers.

reconstruct

Return the missing numbers list [1, 2, 6]

Return the list of K missing positive numbers found by the algorithm.

💡 The final answer is the collected missing numbers in ascending order.

Line:

return missing

💡 The algorithm successfully identifies missing positive numbers including those beyond array range.

def find_k_missing_numbers(arr, k):
    n = len(arr)  # STEP 1
    i = 0  # STEP 1
    while i < n:  # STEP 2-6
        correct_index = arr[i] - 1  # STEP 2
        if 1 <= arr[i] <= n and arr[i] != arr[correct_index]:  # STEP 2
            arr[i], arr[correct_index] = arr[correct_index], arr[i]  # STEP 2
        else:
            i += 1  # STEP 3-6
    missing = []  # STEP 7
    extra_nums = [False] * (k + n + 1)  # STEP 7
    for i in range(n):  # STEP 8-10
        if arr[i] != i + 1 and len(missing) < k:
            missing.append(i + 1)  # STEP 8-9
        if arr[i] > n and arr[i] < len(extra_nums):
            extra_nums[arr[i]] = True  # STEP 8-10
    next_num = n + 1  # STEP 11
    while len(missing) < k:  # STEP 12-13
        if next_num >= len(extra_nums) or not extra_nums[next_num]:
            missing.append(next_num)  # STEP 12
        next_num += 1  # STEP 13
    return missing  # STEP 14

if __name__ == '__main__':
    print(find_k_missing_numbers([3, -1, 4, 5, 5], 3))  # Output: [1, 2, 6]

📊

Find K Missing Positive Numbers - Watch the Algorithm Execute, Step by Step

Watching each pointer move and swap helps you understand how cyclic sort places numbers correctly and how missing numbers are identified systematically.

setup

i

3

0

-1

1

4

2

5

3

5

4

Result: []

swap

i

4

0

-1

1

3

2

correct_index

5

3

5

4

Result: []

move_right

5

0

i

-1

1

3

2

4

3

5

4

Result: []

move_right

5

0

-1

1

i

3

2

4

3

5

4

Result: []

compare

5

0

-1

1

3

2

4

3

i

5

4

Result: []

move_right

5

0

-1

1

3

2

4

3

5

4

Result: []

setup

5

0

-1

1

3

2

4

3

5

4

Result: []

compare

i

5

0

-1

1

3

2

4

3

5

4

Result: [1]

compare

5

0

i

-1

1

3

2

4

3

5

4

Result: [1,2]

compare

5

0

-1

1

3

2

4

3

i

5

4

Result: [1,2]

setup

5

0

-1

1

3

2

4

3

5

4

Result: [1,2]

record

5

0

-1

1

3

2

4

3

5

4

Result: [1,2,6]

move_right

5

0

-1

1

3

2

4

3

5

4

Result: [1,2,6]

record

5

0

-1

1

3

2

4

3

5

4

Result: [1,2,6]

Key Takeaways

✓ Cyclic sort efficiently places numbers in their correct indices, enabling easy identification of missing numbers.

This insight is hard to see from code alone because the swaps and conditions are subtle and happen in a loop.

✓ Numbers outside the array range are tracked separately using a boolean array to find missing numbers beyond the array length.

Visualizing this helps understand why we need extra data structures beyond cyclic sort.

✓ The algorithm carefully avoids infinite swaps by checking if the current number is already at its correct position.

This decision prevents infinite loops and is clearer when watching pointer comparisons step-by-step.

Practice

1. 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)

2. Consider the following buggy code for finding the duplicate number. Which line contains the subtle bug that can cause an infinite loop or incorrect result?

medium

A. Line 7: else: i += 1

B. Line 4: if nums[i] == nums[correct_index]:

C. Line 9: else: nums[i], nums[correct_index] = nums[correct_index], nums[i]

D. Line 2: while i < len(nums):

Solution

1. Step 1: Compare with correct code condition

   The condition should be if nums[i] != nums[correct_index] to decide when to swap.

2. Step 2: Identify effect of wrong condition

   Using == causes swapping only when elements are equal, leading to infinite loops or missed duplicates.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect condition breaks cyclic sort logic [OK]

Hint: Swap only when elements differ, not when equal [OK]

Common Mistakes:

• Reversing the swap condition causing infinite loops
• Incrementing index incorrectly
• Swapping elements in wrong order

3. The following code attempts to find the kth missing positive number using binary search. Which line contains a subtle bug that causes incorrect results when the kth missing number is less than the first element of the array?

medium

A. Line 6: if missing <= k:

B. Line 4: mid = (low + high) // 2

C. Line 8: low = mid + 1

D. Line 10: return k + high + 1

Solution

1. Step 1: Identify the bug in condition

   The condition uses <= instead of < when comparing missing and k. This causes the binary search to move low pointer incorrectly when missing equals k.

2. Step 2: Explain impact on edge cases

   When kth missing is less than arr[0], missing counts start at zero, and using <= causes the search to skip the correct boundary, returning wrong results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing <= to < fixes boundary handling [OK]

Hint: Check strict inequality in binary search condition [OK]

Common Mistakes:

• Using <= instead of <
• Incorrect return formula

4. Suppose the input array can contain numbers outside the range 1 to n, including negatives and zeros, and duplicates. Which modification to the cyclic sort algorithm ensures correct placement of numbers 1 to n at indices 0 to n-1 while ignoring invalid numbers?

hard

A. Swap elements only if arr[i] is in [1, n] and arr[i] != arr[arr[i] - 1], else increment i.

B. Use an extra array of size n to place valid numbers at index num-1, ignoring invalids.

C. Sort the array first, then remove invalid numbers and duplicates.

D. Ignore duplicates by skipping swaps when arr[i] == arr[arr[i] - 1] without checking range.

Solution

1. Step 1: Understand input constraints

   Input may have invalid numbers (negatives, zeros, > n) and duplicates that break in-place cyclic sort.

2. Step 2: Use extra array for placement

   Creating a separate array of size n and placing valid numbers at index num-1 ensures correct placement ignoring invalids and duplicates.

3. Step 3: Avoid in-place swaps that cause index errors or infinite loops

   Extra space approach is safer and simpler for this variant.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Extra array handles invalid and duplicate numbers cleanly [OK]

Hint: Extra array avoids invalid index and duplicate issues [OK]

Common Mistakes:

• Ignoring invalid range checks
• Trying to fix in-place swaps with invalid numbers
• Not handling duplicates properly

5. If the input array can contain numbers outside the range 1 to n (including negatives and zeros), which modification to the cyclic sort approach correctly finds all duplicates?

hard

A. Use a hash set to track duplicates instead of cyclic sort

B. Ignore numbers outside 1 to n during cyclic sort and only swap valid numbers

C. Modify cyclic sort to map values to indices using modulo arithmetic

D. Sort the array first and then scan for duplicates

Solution

1. Step 1: Understand cyclic sort limitation

   Cyclic sort relies on values being in 1 to n to map to indices.

2. Step 2: Modify algorithm to skip invalid values

   Ignore values ≤ 0 or > n during swaps to avoid index errors.

3. Step 3: Continue cyclic sort on valid values only

   This preserves O(n) time and O(1) space while handling invalid values.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Skipping invalid values prevents errors and finds duplicates correctly [OK]

Hint: Skip invalid values to keep cyclic sort valid [OK]

Common Mistakes:

• Trying to map invalid values with modulo causes wrong swaps
• Switching to hash set loses O(1) space advantage
• Sorting increases time complexity unnecessarily