Find Kth Positive Missing Number

▶

Steps

setup

Calculate total missing numbers before last element

Calculate how many positive numbers are missing before the last element of the array by subtracting the array length from the last element's value.

💡 This tells us if the kth missing number lies beyond the array's last element or inside the array.

Line:

n = len(arr)
total_missing = arr[-1] - n

💡 Total missing numbers before last element is 6, meaning 6 positive numbers are missing up to 11.

setup

Check if k is greater than total missing

Compare k=5 with total_missing=6 to decide if binary search is needed or if answer lies beyond last element.

💡 If k > total_missing, answer is beyond last element; otherwise, binary search is needed.

Line:

if k > total_missing:
    return arr[-1] + (k - total_missing)

💡 Since k <= total_missing, the kth missing number is inside the array range.

setup

Initialize binary search pointers

Set left pointer to 0 and right pointer to last index of array to start binary search.

💡 These pointers define the current search space for the kth missing number.

Line:

left, right = 0, n - 1

💡 Search space covers entire array initially.

compare

Calculate mid index and missing count at mid

Calculate mid index as (0+4)//2=2 and compute missing numbers before arr[mid]=4 as 4 - (2+1) = 1.

💡 Missing count at mid tells if kth missing is to left or right.

Line:

mid = (left + right) // 2
missing = arr[mid] - (mid + 1)

💡 Missing count 1 is less than k=5, so kth missing is to the right.

shrink

Move left pointer to mid + 1

Since missing < k, move left pointer to 3 to search right half of array.

💡 Eliminating left half because kth missing is not there.

Line:

if missing < k:
    left = mid + 1

💡 Search space narrowed to indices 3 to 4.

compare

Calculate mid index and missing count at mid

Calculate mid as (3+4)//2=3 and missing numbers before arr[3]=7 as 7 - (3+1) = 3.

💡 Check if kth missing is to left or right of mid=3.

Line:

mid = (left + right) // 2
missing = arr[mid] - (mid + 1)

💡 Missing count 3 is less than k=5, so kth missing is still to the right.

shrink

Move left pointer to mid + 1

Since missing < k, move left pointer to 4 to search right half.

💡 Eliminating index 3 from search space.

Line:

if missing < k:
    left = mid + 1

💡 Search space narrowed to index 4 only.

compare

Calculate mid index and missing count at mid

Calculate mid as (4+4)//2=4 and missing numbers before arr[4]=11 as 11 - (4+1) = 6.

💡 Check if kth missing is to left or right of mid=4.

Line:

mid = (left + right) // 2
missing = arr[mid] - (mid + 1)

💡 Missing count 6 is greater than or equal to k=5, so kth missing is to the left or at mid.

shrink

Move right pointer to mid - 1

Since missing >= k, move right pointer to 3 to search left half.

💡 Eliminating index 4 from search space.

Line:

else:
    right = mid - 1

💡 Search space is now invalid (lo=4 > hi=3), binary search ends.

reconstruct

Compute kth missing number from final pointers

Calculate kth missing number as arr[right] + (k - (arr[right] - (right + 1))) = 7 + (5 - (7 - 4)) = 9.

💡 This formula finds the kth missing number based on the last valid right pointer.

Line:

return arr[right] + (k - (arr[right] - (right + 1)))

💡 The 5th missing positive number is 9.

def findKthPositive(arr, k):
    n = len(arr)  # STEP 1
    total_missing = arr[-1] - n  # STEP 1
    if k > total_missing:  # STEP 2
        return arr[-1] + (k - total_missing)  # STEP 2
    left, right = 0, n - 1  # STEP 3
    while left <= right:  # STEP 4-9
        mid = (left + right) // 2  # STEP 4,6,8
        missing = arr[mid] - (mid + 1)  # STEP 4,6,8
        if missing < k:  # STEP 4,6
            left = mid + 1  # STEP 5,7
        else:  # STEP 8
            right = mid - 1  # STEP 9
    return arr[right] + (k - (arr[right] - (right + 1)))  # STEP 10

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

📊

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

Watching each pointer movement and comparison reveals how the algorithm narrows down the search space efficiently, which is hard to grasp by reading code alone.

Target: 5

lo

2

0

3

1

4

2

7

3

hi

11

4

Next: lo=0 hi=4

Target: 5

lo

2

0

3

1

4

2

7

3

hi

11

4

Next: lo=0 hi=4

Target: 5

lo

2

0

3

1

4

2

7

3

hi

11

4

Next: lo=0 hi=4

Target: 5

lo

2

0

3

1

mid

4

2

7

3

hi

11

4

mid[2]=4 - missing=1 < k=5

Next: lo=3 hi=4

Target: 5

2

0

3

1

mid

4

2

lo

7

3

hi

11

4

mid[2]=4 - missing=1 < k=5

Next: lo=3 hi=4

Target: 5

2

0

3

1

4

2

lo/mid

7

3

hi

11

4

mid[3]=7 - missing=3 < k=5

Next: lo=4 hi=4

Target: 5

2

0

3

1

4

2

mid

7

3

lo/hi

11

4

mid[3]=7 - missing=3 < k=5

Next: lo=4 hi=4

Target: 5

2

0

3

1

4

2

7

3

lo/mid/hi

11

4

mid[4]=11 - missing=6 >= k=5

Next: lo=4 hi=3

Target: 5

2

0

3

1

4

2

hi

7

3

lo/mid

11

4

mid[4]=11 - missing=6 >= k=5

Next: lo=4 hi=3

Target: 5

2

0

3

1

4

2

hi

7

3

lo

11

4

Next: lo=4 hi=3

Key Takeaways

✓ The total missing count before the last element quickly tells if binary search is needed.

This insight is hard to see from code alone because it requires understanding the relationship between array length and values.

✓ Binary search uses the missing count at mid to eliminate half the search space efficiently.

Visualizing pointer movements clarifies how the algorithm narrows down the search space.

✓ The final answer is computed using the right pointer after binary search ends, not directly from mid.

This subtle detail is easy to miss without step-by-step tracing.

Practice

1. You are given a sorted array and need to find how many times a specific target value appears. Which algorithmic approach guarantees the most efficient solution in terms of time complexity?

easy

A. Binary search to find the left and right boundaries of the target

B. Linear scan through the array counting occurrences

C. Dynamic programming to count occurrences using subproblems

D. Greedy approach selecting elements until target count is found

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so binary search can be used to find boundaries efficiently.

2. Step 2: Identify optimal approach

   Binary search for left and right boundaries finds the first and last occurrence indices in O(log n) time, enabling count calculation by subtraction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step [OK]

Hint: Sorted array -> binary search boundaries [OK]

Common Mistakes:

• Using linear scan despite sorted array
• Confusing DP with counting occurrences
• Applying greedy which doesn't guarantee correctness

2. Consider the following Python code implementing the optimal approach to find k closest elements to x in a sorted array. What is the returned output when calling findClosestElements([1, 3, 5], 2, 4)?

easy

A. [1, 3]

B. [3, 4]

C. [1, 5]

D. [3, 5]

Solution

1. Step 1: Initialize variables

   Array length is 3, k=2, so low=0, high=1.

2. Step 2: First iteration of binary search

   Calculate mid = (0+1)//2 = 0. Compare x - arr[mid] = 4 - 1 = 3 and arr[mid + k] - x = arr[2] - 4 = 5 - 4 = 1. Since 3 > 1, set low = mid + 1 = 1.

3. Step 3: Loop ends as low == high == 1

   Return arr[1:3] = [3, 5].

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Binary search correctly chooses window starting at index 1 [OK]

Hint: Check mid and window edges distances carefully [OK]

Common Mistakes:

• Off-by-one error in slicing window
• Incorrect comparison direction in if condition
• Returning wrong slice boundaries

3. Consider the following Python function to find the minimum in a rotated sorted array without duplicates. What value does the function return when called with nums = [3, 4, 1]?

easy

A. 4

B. 3

C. 1

D. IndexError due to out-of-bound access

Solution

1. Step 1: First iteration with left=0, right=2

   mid=1, nums[mid]=4, prev=0 (nums[0]=3), next=2 (nums[2]=1). Check if nums[mid] < nums[prev]: 4 < 3? No. Check if nums[mid] > nums[next_]: 4 > 1? Yes -> return nums[next_] = 1.

2. Step 2: Function returns 1 immediately

   No further iterations occur; minimum found at nums[2].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Mid element compared correctly with neighbors [OK]

Hint: Check mid against neighbors to find pivot [OK]

Common Mistakes:

• Off-by-one in prev/next indices
• Ignoring wrap-around with modulo
• Assuming mid is always minimum

4. Consider the following code snippet implementing the binary search on value range approach to find the median of two sorted arrays. Given nums1 = [1, 3] and nums2 = [2, 4], what is the final returned median?

easy

A. 2.0

B. 2.5

C. 3.0

D. 2.25

Solution

1. Step 1: Trace binary search iterations

   Initial left=1, right=4. Mid=2, countLessEqual(2)=3 ≥ 2.5 so right=2. Next mid=1, countLessEqual(1)=1 < 2.5 so left=2.

2. Step 2: Compute median for even total length

   Left=2, total length=4 (even). Candidates before 2 are nums1[0]=1 and nums2[0]=2, max=2. Median=(2+3)/2=2.5 is correct median of combined sorted array [1,2,3,4]. The code snippet's logic is incomplete but assuming correct logic, median is 2.5.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Median of combined sorted array [1,2,3,4] is 2.5 [OK]

Hint: Median of [1,2,3,4] is average of 2 and 3 [OK]

Common Mistakes:

• Off-by-one in bisect boundaries
• Confusing left with median
• Ignoring even length median averaging

5. The following code attempts to find the insert position of a target in a sorted array using recursive binary search. Identify the line containing the subtle bug that can cause incorrect results or infinite recursion.

medium

A. Line 3: if left > right: return right

B. Line 4: mid = (left + right) // 2

C. Line 7: if nums[mid] == target: return mid

D. Line 9: return binary_search(mid + 1, right)

Solution

1. Step 1: Analyze base case return value

   When left > right, the correct insertion index is left, not right.

2. Step 2: Consequence of returning right

   Returning right can cause incorrect insertion index or infinite recursion if right < left.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct base case returns left to indicate insertion point [OK]

Hint: Base case must return left, not right [OK]

Common Mistakes:

• Returning right instead of left at base case
• Incorrect mid calculation causing infinite loop
• Misplaced recursive calls