Find Kth Positive Missing Number

📋

Find Kth Positive Missing Number

Edge cases:

</>

IDE

def findKthPositive(arr: list[int], k: int) -> int:public int findKthPositive(int[] arr, int k)int findKthPositive(vector<int>& arr, int k)function findKthPositive(arr, k)

def findKthPositive(arr, k):
    # Write your solution here
    pass

class Solution {
    public int findKthPositive(int[] arr, int k) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findKthPositive(vector<int>& arr, int k) {
    // Write your solution here
    return 0;
}

function findKthPositive(arr, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: kAlways returning k without considering arr elements or missing counts.✅ Implement binary search on missing counts and calculate missing = arr[mid] - mid - 1.

Wrong: arr[-1] + kAssuming all missing numbers are after last element without checking missing counts inside arr.✅ Calculate total missing inside arr as arr[-1] - len(arr) and compare with k before returning.

Wrong: Off-by-one errors in binary search index or missing count calculationIncorrect binary search boundaries or missing count formula.✅ Use missing = arr[mid] - mid - 1 and carefully adjust binary search left/right pointers.

Wrong: Timeout / TLEUsing brute force linear scan for large k and n.✅ Use binary search on missing counts to achieve O(log n) time complexity.

✓

Test Cases

Focus on base cases like empty arrays and single elements to handle boundary conditions.

Watch out for off-by-one errors and special cases where k is outside the range of missing numbers within arr.

Optimize your solution from linear to logarithmic time using binary search on missing counts.

t1_01basic

Input{"arr":[2,3,4,7,11],"k":5}

Expected9

⏱ Performance - must finish in 2000ms

The missing positive integers are [1,5,6,8,9,10,...]. The 5th missing is 9.

💡 Think about how many numbers are missing before each element in arr.

💡 Use binary search to find the smallest index where missing count >= k.

💡 Calculate result as arr[left-1] + k - missing_before(arr[left-1]) if left > 0, else k.

Why it failed: Incorrect output means missing count calculation or binary search boundary is wrong. Fix by correctly computing missing count as arr[mid] - mid - 1 and adjusting binary search accordingly.

✓ Correctly finds kth missing number using binary search on missing counts.

t1_02basic

Input{"arr":[1,2,3,4],"k":2}

Expected6

⏱ Performance - must finish in 2000ms

No missing numbers before 4; missing numbers start after 4: [5,6,...]. The 2nd missing is 6.

💡 Check if k is larger than total missing numbers within arr range.

💡 If so, answer is arr[-1] + (k - total_missing_in_arr).

💡 Calculate total missing as arr[-1] - len(arr).

Why it failed: Fails when k exceeds missing numbers within arr range; fix by returning arr[-1] + (k - total_missing) when binary search fails to find index.

✓ Handles missing numbers beyond last element correctly.

t2_01edge

Input{"arr":[],"k":1}

Expected1

⏱ Performance - must finish in 2000ms

Empty array means all positive integers are missing; 1st missing is 1.

💡 Consider what happens if arr is empty.

💡 All positive integers are missing, so kth missing is simply k.

💡 Return k directly if arr is empty.

Why it failed: Fails empty input by not handling arr length zero; fix by returning k if arr is empty.

✓ Correctly returns k when arr is empty.

t2_02edge

Input{"arr":[5],"k":3}

Expected3

⏱ Performance - must finish in 2000ms

Missing numbers before 5 are [1,2,3,4]; 3rd missing is 3.

💡 Check missing numbers before the first element.

💡 If k is less than first element - 1, answer is k.

💡 Return k if k < arr[0].

Why it failed: Fails when kth missing is before first element; fix by returning k if k < arr[0].

✓ Handles missing numbers before first element correctly.

t2_03edge

Input{"arr":[1],"k":1}

Expected2

⏱ Performance - must finish in 2000ms

No missing numbers before 1; 1st missing is 2.

💡 Check if first element is 1 and k=1.

💡 Missing numbers start after 1.

💡 Return arr[0] + k if k > 0 and arr[0] == 1.

Why it failed: Fails when arr has one element equal to 1 and k=1; fix by returning arr[0] + k in this case.

✓ Correctly handles single element array with no missing before it.

t2_04edge

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

Expected6

⏱ Performance - must finish in 2000ms

No missing numbers within arr; missing numbers start after 5; 1st missing is 6.

💡 Check if no missing numbers inside arr.

💡 Missing numbers start after arr[-1].

💡 Return arr[-1] + k.

Why it failed: Fails when no missing numbers inside arr; fix by returning arr[-1] + k.

✓ Correctly handles consecutive array with no missing inside.

t3_01corner

Input{"arr":[2,3,4,7,11],"k":1}

Expected1

⏱ Performance - must finish in 2000ms

The 1st missing positive integer is 1, which is less than arr[0].

💡 Check if k is smaller than the first missing number.

💡 If k < arr[0], answer is k.

💡 Return k directly if k < arr[0].

Why it failed: Fails to handle k smaller than first missing number; fix by returning k if k < arr[0]. This is the 0/1 constraint test.

✓ Correctly returns kth missing when it is before arr[0].

t3_02corner

Input{"arr":[1,2,3,4,5],"k":10}

Expected15

⏱ Performance - must finish in 2000ms

No missing numbers within arr; missing start after 5: [6,7,...]. 10th missing is 15.

💡 Check if k is larger than total missing numbers within arr range.

💡 If so, answer is arr[-1] + (k - total_missing).

💡 Calculate total missing as arr[-1] - len(arr).

Why it failed: Fails when k exceeds missing numbers within arr; fix by returning arr[-1] + (k - total_missing). This is the greedy trap test.

✓ Handles missing numbers beyond last element correctly.

t3_03corner

Input{"arr":[3,5,7,10],"k":4}

Expected6

⏱ Performance - must finish in 2000ms

Missing numbers are [1,2,4,6,8,9,...]. The 4th missing is 6.

💡 Use binary search on missing count to find correct index.

💡 Calculate missing count as arr[mid] - mid - 1.

💡 Return arr[left-1] + k - missing_before(arr[left-1]) if left > 0.

Why it failed: Fails off-by-one in binary search or missing count calculation; fix by using missing = arr[mid] - mid - 1 and careful binary search boundaries.

✓ Correctly handles off-by-one errors in binary search.

t4_01performance

Input{"arr":[2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,42,44,46,48,50,52,54,56,58,60,62,64,66,68,70,72,74,76,78,80,82,84,86,88,90,92,94,96,98,100,102,104,106,108,110,112,114,116,118,120,122,124,126,128,130,132,134,136,138,140,142,144,146,148,150,152,154,156,158,160,162,164,166,168,170,172,174,176,178,180,182,184,186,188,190,192,194,196,198,200],"k":100000000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, arr has even numbers from 2 to 200. Must complete in O(log n) time within 2s.

💡 Brute force O(k+n) will time out for large k.

💡 Use binary search on missing counts for O(log n) complexity.

💡 Calculate missing count as arr[mid] - mid - 1 to guide binary search.

Why it failed: TLE due to brute force linear scan over large k; fix by implementing binary search on missing counts. This is the O(k+n) complexity test.

✓ Efficient binary search solution runs within time limits.

Practice

1. You are given a 2D matrix where each row is sorted in ascending order, and the first integer of each row is greater than the last integer of the previous row. You need to determine if a target value exists in the matrix. Which algorithmic approach guarantees the most efficient search?

easy

A. Perform a linear scan over all elements using nested loops.

B. Treat the 2D matrix as a 1D sorted array and apply binary search.

C. Apply binary search independently on each row until the target is found.

D. Use dynamic programming to build a table of reachable values.

Solution

1. Step 1: Understand matrix properties

   The matrix is sorted row-wise and each row's first element is greater than the last element of the previous row, so the entire matrix can be viewed as a sorted 1D array.

2. Step 2: Identify optimal search approach

   Binary searching the entire matrix as a 1D array leverages this global ordering, yielding O(log(m*n)) time, better than searching each row separately or scanning all elements.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Global sorted order allows single binary search [OK]

Hint: Matrix can be flattened logically for binary search [OK]

Common Mistakes:

• Thinking binary search on each row is optimal
• Assuming DP is needed
• Using brute force for efficiency

2. You are given a sorted array where every element appears exactly twice except for one element which appears only once. Which algorithmic approach guarantees an optimal O(log n) time solution to find the single element?

easy

A. Modified binary search using index parity to halve the search space

B. Dynamic programming to store counts of elements and find the unique one

C. Linear scan checking pairs sequentially until the unique element is found

D. Greedy approach selecting elements based on local pair matches

Solution

1. Step 1: Understand problem constraints

   The array is sorted and every element except one appears twice consecutively.

2. Step 2: Identify algorithm that exploits sorted pairs

   Modified binary search using index parity halves the search space by comparing pairs, achieving O(log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search with parity is known optimal for this problem [OK]

Hint: Use parity-based binary search for O(log n) solution [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Using DP unnecessarily
• Applying greedy without global insight

3. Examine the following code snippet intended to count occurrences of a target in a sorted array. Which line contains a subtle bug that can cause incorrect counts when the target is not present?

medium

A. Line 2: import bisect

B. Line 4: left = bisect.bisect_left(nums, target)

C. Line 5: right = bisect.bisect_left(nums, target + 1)

D. Line 6: return right - left

Solution

1. Step 1: Understand bisect_left behavior

   bisect_left returns insertion point even if target not present.

2. Step 2: Identify issue in return statement

   Subtracting right - left without checking if target exists can yield positive count when target is absent.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Return line assumes target presence, causing incorrect counts [OK]

Hint: Check target presence before subtracting indices [OK]

Common Mistakes:

• Ignoring target absence check
• Misusing bisect_left boundaries
• Assuming import or bisect calls cause bugs

4. What is the time complexity of the optimal binary search algorithm that treats an m x n 2D matrix as a 1D sorted array to search for a target?

medium

A. O(log(m * n))

B. O(m * n)

C. O(m * log n)

D. O(log m + log n)

Solution

1. Step 1: Understand the search space size

   The matrix has m*n elements, treated as a sorted 1D array.

2. Step 2: Apply binary search complexity

   Binary search on an array of size m*n takes O(log(m*n)) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search halves search space each step, log scale [OK]

Hint: Binary search complexity depends on total elements, not rows or columns separately [OK]

Common Mistakes:

• Confusing with O(m*n) brute force
• Thinking binary search per row is O(m log n)
• Adding logs incorrectly as O(log m + log n)

5. Suppose the problem is modified so that the matrix rows are sorted but columns are not guaranteed to be sorted. Which approach would correctly find the kth smallest element efficiently?

hard

A. Use the min-heap approach merging rows as before, since rows remain sorted.

B. Flatten the matrix and sort it, then return the kth element.

C. Use binary search on the value range with a counting function scanning the entire matrix.

D. Use a min-heap merging columns instead of rows.

Solution

1. Step 1: Analyze matrix properties

   Rows are sorted but columns are not, so min-heap merging rows only partially orders elements.

2. Step 2: Evaluate approaches

   Min-heap merging rows assumes columns sorted for correctness; binary search counting requires sorted rows and columns for efficient counting; flatten and sort works regardless.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Flatten and sort is the fallback when only rows sorted [OK]

Hint: Partial sorting breaks heap and binary search assumptions [OK]

Common Mistakes:

• Assuming min-heap merging rows still works
• Using binary search counting without full sorting
• Ignoring matrix sorting properties