Kth Missing Positive Number

▶

Steps

setup

Initialize low and high pointers

Set low to 0 and high to the last index of the array to start binary search over the entire array.

💡 Initializing these pointers sets the search boundaries for the binary search.

Line:

low, high = 0, len(arr) - 1

💡 The search space covers the entire array initially.

compare

Calculate mid index

Calculate mid as the integer midpoint between low and high to check the missing count at this position.

💡 Midpoint divides the search space to decide which half to explore next.

Line:

mid = (low + high) // 2

💡 Mid is 2, pointing to arr[2] = 4.

compare

Calculate missing count at mid

Calculate how many positive integers are missing before arr[mid] by subtracting (mid + 1) from arr[mid].

💡 This formula counts missing numbers before the current element.

Line:

missing = arr[mid] - (mid + 1)

💡 missing = 4 - (2 + 1) = 1, so 1 number is missing before index 2.

compare

Compare missing count with k

Check if the missing count at mid is less than k to decide which half to search next.

💡 This comparison guides the binary search direction.

Line:

if missing < k:

💡 Since fewer than k numbers are missing before mid, the kth missing must be to the right.

move_right

Move low pointer right

Since missing < k, move low pointer to mid + 1 to search the right half.

💡 Moving low narrows the search space to the right side.

Line:

low = mid + 1

💡 Low moves from 0 to 3, focusing on indices 3 to 4.

compare

Calculate new mid index

Calculate mid again as the midpoint between updated low and high pointers.

💡 Mid recalculates to check missing count in the new search space.

Line:

mid = (low + high) // 2

💡 Mid is now 3, pointing to arr[3] = 7.

compare

Calculate missing count at new mid

Calculate missing numbers before arr[mid] at index 3.

💡 This tells how many numbers are missing before arr[3].

Line:

missing = arr[mid] - (mid + 1)

💡 missing = 7 - (3 + 1) = 3, so 3 numbers are missing before index 3.

compare

Compare missing count with k again

Check if missing count at mid is less than k to decide pointer movement.

💡 This comparison guides the next binary search step.

Line:

if missing < k:

💡 Still fewer than k missing numbers before mid, so search right half.

move_right

Move low pointer right again

Move low pointer to mid + 1 to continue searching the right half.

💡 Narrowing search space further to the right.

Line:

low = mid + 1

💡 Low moves from 3 to 4, focusing on index 4 only.

compare

Calculate mid at single element

Calculate mid as the midpoint between low and high, which are both 4.

💡 Mid points to the last element to check missing count.

Line:

mid = (low + high) // 2

💡 Mid is 4, pointing to arr[4] = 11.

compare

Calculate missing count at last element

Calculate missing numbers before arr[mid] at index 4.

💡 This tells how many numbers are missing before the last element.

Line:

missing = arr[mid] - (mid + 1)

💡 missing = 11 - (4 + 1) = 6, so 6 numbers are missing before index 4.

compare

Compare missing count with k at last element

Check if missing count at mid is less than k to decide pointer movement.

💡 This comparison determines if we move high pointer left.

Line:

if missing < k:

💡 Since missing >= k, the kth missing is to the left, so move high left.

move_left

Move high pointer left

Move high pointer to mid - 1 to search the left half.

💡 Moving high narrows the search space from the right.

Line:

high = mid - 1

💡 High moves from 4 to 3, so low (4) > high (3) ends the loop.

reconstruct

Binary search ends, compute kth missing

Since low > high, binary search ends. Compute kth missing as k + high + 1.

💡 This formula calculates the kth missing positive number based on the final high pointer.

Line:

return k + high + 1

💡 k + high + 1 = 5 + 3 + 1 = 9, the 5th missing positive number.

def findKthPositive(arr, k):
    low, high = 0, len(arr) - 1  # STEP 1
    while low <= high:  # STEP 2 loop start
        mid = (low + high) // 2  # STEP 2
        missing = arr[mid] - (mid + 1)  # STEP 3
        if missing < k:  # STEP 4
            low = mid + 1  # STEP 5
        else:
            high = mid - 1  # STEP 13
    return k + high + 1  # STEP 14

if __name__ == '__main__':
    print(findKthPositive([2,3,4,7,11], 5))  # Output: 9

📊

Kth Missing Positive Number - Watch the Algorithm Execute, Step by Step

Watching each pointer move and calculation helps you understand how the algorithm efficiently finds the kth missing number without enumerating all missing numbers.

setup

low

2

0

3

1

4

2

7

3

high

11

4

compare

low

2

0

3

1

mid

4

2

7

3

high

11

4

compare

low

2

0

3

1

mid

4

2

7

3

high

11

4

compare

low

2

0

3

1

mid

4

2

7

3

high

11

4

move_right

2

0

3

1

4

2

low

7

3

high

11

4

compare

2

0

3

1

4

2

mid

7

3

high

11

4

compare

2

0

3

1

4

2

mid

7

3

high

11

4

compare

2

0

3

1

4

2

mid

7

3

high

11

4

move_right

2

0

3

1

4

2

7

3

high

11

4

compare

2

0

3

1

4

2

7

3

mid

11

4

compare

2

0

3

1

4

2

7

3

mid

11

4

compare

2

0

3

1

4

2

7

3

mid

11

4

move_left

2

0

3

1

4

2

high

7

3

low

11

4

record

2

0

3

1

4

2

high

7

3

low

11

4

Result: 9

Key Takeaways

✓ Binary search efficiently finds the kth missing positive number by comparing missing counts instead of enumerating missing numbers.

This insight is hard to see from code alone because the missing count calculation and pointer updates are subtle and intertwined.

✓ The missing count at arr[mid] is arr[mid] - (mid + 1), which measures how many positive integers are missing before that index.

Understanding this formula is key to grasping why the binary search works.

✓ Pointer movements depend on whether the missing count is less than k, guiding the search space narrowing.

Seeing each pointer move step-by-step clarifies the binary search decision process.

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. Consider the following Python function that finds the first k missing positive numbers using cyclic sort and a boolean array. What is the output of find_k_missing_numbers([3, -1, 4, 5, 5], 3)?

easy

A. [2, 3, 6]

B. [1, 2, 3]

C. [1, 4, 6]

D. [1, 2, 6]

Solution

1. Step 1: Perform cyclic sort on input [3, -1, 4, 5, 5]

   After sorting, the array becomes [1, -1, 3, 4, 5] with 1 at index 0, -1 at index 1, 3 at index 2, 4 at index 3, and 5 at index 4. Negative numbers are ignored in placement.

2. Step 2: Identify missing numbers and extras

   Missing numbers are 2 (since index 1 != 2), and since k=3, the next missing number beyond array length is 6. So missing = [1, 2, 6].

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected missing positives [OK]

Hint: Cyclic sort places numbers correctly; missing are indices not matching values [OK]

Common Mistakes:

• Confusing indices and values after cyclic sort
• Forgetting to add missing numbers beyond array length
• Miscounting duplicates as missing

3. 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

4. What is the time complexity of the optimal cyclic sort approach for finding the first missing positive integer in an array of length n?

medium

A. O(n) amortized because each swap places an element correctly

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

C. O(n log n) due to sorting-like swaps

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

Solution

1. Step 1: Analyze the loops

   The outer loop runs n times, and the inner while loop swaps elements to their correct positions.

2. Step 2: Understand swap frequency

   Each element can be swapped at most once to its correct position, so total swaps ≤ n, making the inner loop amortized O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized analysis confirms O(n) time complexity [OK]

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

Common Mistakes:

• Assuming nested loops mean O(n^2)
• Confusing amortized with worst-case per iteration
• Thinking swaps are unlimited causing O(n log n)

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