Kth Missing Positive Number

📋

Kth Missing Positive 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: kReturning k directly without checking if kth missing is less than arr[0] or after last element.✅ Add condition: if k < arr[0], return k; else handle missing after last element.

Wrong: arr[-1] + kIncorrectly returning arr[-1] + k without subtracting missing count before last element.✅ Return arr[-1] + (k - (arr[-1] - n)) where n = len(arr).

Wrong: Wrong kth missing due to linear scan TLE or incorrect binary searchUsing brute force linear scan for large k or incorrect binary search implementation.✅ Implement binary search on missing count using missing = arr[i] - (i + 1).

Wrong: Off-by-one errors in missing count calculationCalculating missing count as arr[i] - i instead of arr[i] - (i + 1).✅ Use missing count formula: arr[i] - (i + 1).

Wrong: Fails empty array inputNot handling empty array case, causing index errors or wrong output.✅ If arr is empty, return k directly.

✓

Test Cases

Focus on handling empty and minimal input arrays, and cases where kth missing is outside the array range.

Ensure your binary search correctly finds the smallest index where missing count >= k and handles off-by-one errors.

Optimize your solution to O(log n) using binary search on missing counts to handle large k efficiently.

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,12,...]. The 5th missing is 9.

💡 Count how many numbers are missing before each element in the array.

💡 Use the formula missing = arr[i] - (i + 1) to find missing count at index i.

💡 Find the smallest index where missing count >= k, then calculate kth missing accordingly.

Why it failed: Incorrect output means missing count calculation or binary search logic is wrong. Fix by correctly computing missing count as arr[i] - (i + 1) and applying binary search properly.

✓ Correctly identifies kth missing positive using missing count and binary search.

t1_02basic

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

Expected6

⏱ Performance - must finish in 2000ms

No missing numbers before last element 4; missing numbers start at 5,6,... The 2nd missing is 6.

💡 Check if kth missing is beyond the last element of the array.

💡 Calculate total missing before last element: arr[-1] - n = 4 - 4 = 0.

💡 If k > total missing, kth missing = last element + (k - total missing).

Why it failed: Fails when kth missing is beyond last element due to not handling missing count after array end. Fix by returning arr[-1] + (k - missing_before_last).

✓ 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 the case when the array is empty.

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

💡 Return k directly if array is empty.

Why it failed: Fails empty array case by not returning k directly. Fix by adding a check: if arr is empty, return k.

✓ Correctly returns kth missing when array is empty.

t2_02edge

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

Expected5

⏱ Performance - must finish in 2000ms

Missing numbers before 10 are [1..9]; 5th missing is 5.

💡 Check missing numbers before the first element.

💡 If k is less than first missing number (arr[0] - 1), kth missing is k.

💡 Return k if k < arr[0].

Why it failed: Fails when kth missing is less than first element by not returning k directly. Fix by checking if k < arr[0], then return k.

✓ Handles kth missing less than first element correctly.

t2_03edge

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

Expected2

⏱ Performance - must finish in 2000ms

Array has one element 1; missing numbers start at 2; 1st missing is 2.

💡 Consider single element array with k=1.

💡 Missing numbers start after arr[0] if k > 0.

💡 Return arr[0] + k if k > 0 and no missing before arr[0].

Why it failed: Fails single element case by not handling missing after the element. Fix by returning arr[0] + k when k > missing before arr[0].

✓ Correctly handles single element array.

t2_04edge

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

Expected100000005

⏱ Performance - must finish in 2000ms

Large k beyond last element; missing numbers start at 6; kth missing is last element + (k - missing_before_last).

💡 For very large k, missing number is beyond last element.

💡 Calculate missing_before_last = arr[-1] - n = 5 - 5 = 0.

💡 Return arr[-1] + (k - missing_before_last).

Why it failed: Fails large k case by not handling missing beyond last element. Fix by returning arr[-1] + (k - missing_before_last).

✓ Handles very large k beyond last element correctly.

t3_01corner

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

Expected1

⏱ Performance - must finish in 2000ms

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

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

💡 Missing count before arr[0] is arr[0] - 1.

💡 Return k if k < arr[0].

Why it failed: Fails to handle kth missing less than first element, returning wrong value. Fix by adding condition: if k < arr[0], return k.

✓ Correctly handles kth missing less than first element (greedy trap avoided).

t3_02corner

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

Expected8

⏱ Performance - must finish in 2000ms

No missing numbers before last element 5; missing start at 6; 3rd missing is 8.

💡 Check missing count after last element.

💡 Total missing before last element is arr[-1] - n = 5 - 5 = 0.

💡 Return arr[-1] + (k - missing_before_last).

Why it failed: Fails to handle missing numbers after last element, returning wrong value. Fix by returning arr[-1] + (k - missing_before_last).

✓ Correctly handles missing numbers after last element.

t3_03corner

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

Expected8

⏱ Performance - must finish in 2000ms

Missing numbers are [2,4,6,8,10,...]; 4th missing is 8.

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

💡 Calculate missing count as arr[i] - (i + 1).

💡 Find smallest i where missing count >= k, then compute kth missing accordingly.

Why it failed: Fails binary search logic or missing count calculation, returning wrong kth missing. Fix by implementing binary search with missing count formula correctly.

✓ Correctly uses binary search to find kth missing.

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":10000000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, arr contains even numbers from 2 to 200; k=10^7 tests performance of binary search approach within 2s time limit.

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

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

💡 Calculate missing count as arr[i] - (i + 1) and apply binary search to find kth missing.

Why it failed: TLE due to brute force or linear scan approach with large k. Fix by implementing binary search on missing count for O(log n) complexity.

✓ Efficient binary search approach passes performance test.

Practice

1. You are given an unsorted array containing numbers from 1 to n with some numbers possibly missing or duplicated. The task is to rearrange the array so that each number i is placed at index i-1 if it exists. Which algorithmic approach guarantees an optimal O(n) time solution without extra sorting?

easy

A. Use cyclic sort by swapping elements to their correct indices based on their values until all are placed correctly.

B. Sort the array using a built-in sort function and then rearrange elements accordingly.

C. Use dynamic programming to track the placement of each number and build the sorted array.

D. Use a greedy approach that swaps elements to their correct positions until all are placed correctly.

Solution

1. Step 1: Understand the problem constraints

   The problem requires placing numbers 1 to n at indices 0 to n-1 respectively, handling duplicates or missing numbers efficiently.

2. Step 2: Identify the optimal approach

   Cyclic sort swaps elements to their correct positions in O(n) time without extra sorting or DP overhead, unlike greedy or sorting approaches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Cyclic sort directly places elements by index in one pass [OK]

Hint: Cyclic sort swaps elements to correct indices in O(n) time [OK]

Common Mistakes:

• Confusing greedy swaps with cyclic sort
• Assuming sorting is always needed
• Misapplying DP to placement problems

2. You are given an array containing n distinct numbers taken from the range 0 to n. Exactly one number from this range is missing in the array. Which algorithmic approach guarantees finding the missing number in O(n) time and O(1) space without using extra data structures?

easy

A. Applying a dynamic programming approach to build a state table of present numbers

B. Sorting the array and then scanning for the missing number

C. Using a hash set to track presence of numbers and then checking which is missing

D. Cyclic sort to place each number at its correct index, then scanning for the mismatch

Solution

1. Step 1: Understand problem constraints

   The array contains numbers from 0 to n with one missing; all are distinct.

2. Step 2: Identify approach with O(n) time and O(1) space

   Cyclic sort places each number at its index in one pass, then a single scan finds the missing number efficiently.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cyclic sort rearranges in-place with linear time and constant space [OK]

Hint: Cyclic sort matches numbers to indices in-place [OK]

Common Mistakes:

• Assuming sorting is always O(n log n)
• Thinking hash sets use O(1) space
• Confusing DP with presence checking

3. Given the following code snippet, what is the output when calling findErrorNums([1, 2, 2, 4])?

easy

A. [2, 4]

B. [3, 2]

C. [2, 3]

D. [1, 3]

Solution

1. Step 1: Trace the cyclic sort swaps

   Initial array: [1, 2, 2, 4]. The duplicate 2 causes a swap to place numbers correctly except index 2 which remains 2.

2. Step 2: Identify mismatch after sorting

   After sorting, array is [1, 2, 2, 4]. At index 2, expected 3 but found 2 -> duplicate=2, missing=3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected duplicate and missing pair [OK]

Hint: Mismatch found where index+1 != value after cyclic sort [OK]

Common Mistakes:

• Confusing duplicate and missing order
• Off-by-one errors in indexing
• Returning wrong pair from loop

4. Identify the bug in the following code snippet that attempts to find duplicates using cyclic sort:

medium

A. Line with duplicates.append(nums[i]) repeated twice causing duplicates in output

B. Line calculating correct_index = nums[i] - 1 is off by one

C. Condition if nums[i] != nums[correct_index] should be reversed

D. Incrementing i inside else block causes infinite loop

Solution

1. Step 1: Inspect duplicate appending loop

   Duplicates were appended twice for each mismatch, causing repeated entries. The bug is fixed by removing the repeated append.

2. Step 2: Confirm other lines are correct

   Index calculation and swap condition are correct; incrementing i is proper to avoid infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Duplicate elements appear twice in output due to repeated append [OK]

Hint: Check for repeated append calls causing duplicate outputs [OK]

Common Mistakes:

• Infinite loop due to missing i increment
• Off-by-one errors in index calculation
• Incorrect swap condition reversing logic

5. What is the time complexity of the optimal cyclic sort approach to find the duplicate and missing numbers in an array of size n, and why?

medium

A. O(n) because each element is swapped at most once to its correct position

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

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

D. O(n log n) because of sorting the array

Solution

1. Step 1: Identify the main loop behavior

   The while loop swaps elements to their correct positions. Each swap places at least one element correctly, so total swaps ≤ n.

2. Step 2: Analyze time complexity

   Since each element is moved at most once, the total operations are proportional to n, resulting in O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

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

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

Common Mistakes:

• Assuming sorting is involved -> O(n log n)
• Mistaking nested loops inside while as O(n^2)
• Forgetting swaps reduce total operations