What happens if you not accounting for missing numbers before the first element?

Incorrect answer when kth missing is less than arr[0] Fix: Check if kth missing is less than arr[0] and return k directly if so

What happens if you off-by-one errors in binary search boundaries?

Infinite loops or wrong index found Fix: Carefully update left and right pointers and test boundary conditions

What happens if you miscomputing missing count as arr[mid] - mid instead of arr[mid] - (mid + 1)?

Wrong missing count leads to incorrect binary search decisions Fix: Remember missing count before index mid is arr[mid] - (mid + 1)

What happens if you not handling case when kth missing is beyond last element?

Code returns wrong number or crashes Fix: Calculate total missing before last element and handle k accordingly

Interview Prepmodified-binary-searcheasyAmazonGoogle

Find Kth Positive Missing Number

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

easyBINARY_SEARCHAmazonGoogle

Imagine you have a sorted list of positive integers representing IDs assigned to users, but some IDs are missing. You want to find the Kth missing ID to assign it next.

💡 This problem is about finding missing elements in a sorted sequence. Beginners often struggle because they try to scan linearly or guess the missing numbers instead of using the sorted property to efficiently find the answer.

📋

Problem Statement

Given a sorted array arr of positive integers and an integer k, return the kth positive integer that is missing from this array.

1 ≤ arr.length ≤ 10^51 ≤ arr[i] ≤ 10^71 ≤ k ≤ 10^8arr is strictly increasing

💡

Example

Input"arr = [2,3,4,7,11], k = 5"

Output9

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

Input"arr = [1,2,3,4], k = 2"

Output6

Missing positive integers are [5,6,7,...]. The 2nd missing is 6.

k is smaller than the first missing number → output is less than arr[0]
k is larger than all missing numbers within arr range → output beyond arr[-1]
arr contains consecutive numbers with no missing in between → missing numbers start after arr[-1]
arr has only one element → missing numbers start before or after that element

⚠️

Common Mistakes

Not accounting for missing numbers before the first element

Incorrect answer when kth missing is less than arr[0]

✅ Check if kth missing is less than arr[0] and return k directly if so

Off-by-one errors in binary search boundaries

Infinite loops or wrong index found

✅ Carefully update left and right pointers and test boundary conditions

Miscomputing missing count as arr[mid] - mid instead of arr[mid] - (mid + 1)

Wrong missing count leads to incorrect binary search decisions

✅ Remember missing count before index mid is arr[mid] - (mid + 1)

Not handling case when kth missing is beyond last element

Code returns wrong number or crashes

✅ Calculate total missing before last element and handle k accordingly

🧠

Brute Force (Linear Scan)

💡 This approach exists to build intuition by directly simulating the missing numbers. It is simple but inefficient, helping beginners understand the problem before optimizing.

Intuition

Check every positive integer starting from 1, count how many are missing from the array until we reach the kth missing.

Algorithm

Initialize a pointer i for the array and a counter for missing numbers.
Iterate from 1 upwards, checking if the current number matches arr[i].
If it matches, move i forward; else increment missing count.
When missing count reaches k, return the current number.

💡 This algorithm is straightforward but inefficient because it checks every number one by one, which is easy to understand but slow for large inputs.

</>

Code

def findKthPositive(arr, k):
    missing_count = 0
    current = 1
    i = 0
    n = len(arr)
    while True:
        if i < n and arr[i] == current:
            i += 1
        else:
            missing_count += 1
            if missing_count == k:
                return current
        current += 1

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

Line Notes

missing_count = 0Initialize count of missing numbers found so far

current = 1Start checking from the smallest positive integer

if i < n and arr[i] == currentCheck if current number is present in array

missing_count += 1Increment missing count when current is not in array

if missing_count == kReturn current when kth missing number is found

public class Solution {
    public static int findKthPositive(int[] arr, int k) {
        int missingCount = 0, current = 1, i = 0, n = arr.length;
        while (true) {
            if (i < n && arr[i] == current) {
                i++;
            } else {
                missingCount++;
                if (missingCount == k) {
                    return current;
                }
            }
            current++;
        }
    }

    public static void main(String[] args) {
        System.out.println(findKthPositive(new int[]{2,3,4,7,11}, 5)); // 9
    }
}

Line Notes

int missingCount = 0Initialize missing count to zero

int current = 1Start checking from 1

if (i < n && arr[i] == current)Check if current number is in array

missingCount++Increment missing count if current is missing

if (missingCount == k)Return current when kth missing found

#include <iostream>
#include <vector>
using namespace std;

int findKthPositive(vector<int>& arr, int k) {
    int missingCount = 0, current = 1, i = 0, n = arr.size();
    while (true) {
        if (i < n && arr[i] == current) {
            i++;
        } else {
            missingCount++;
            if (missingCount == k) {
                return current;
            }
        }
        current++;
    }
}

int main() {
    vector<int> arr = {2,3,4,7,11};
    cout << findKthPositive(arr, 5) << endl; // 9
    return 0;
}

Line Notes

int missingCount = 0Initialize count of missing numbers

int current = 1Start from smallest positive integer

if (i < n && arr[i] == current)Check if current is in array

missingCount++Increment missing count if current missing

if (missingCount == k)Return current when kth missing found

function findKthPositive(arr, k) {
    let missingCount = 0, current = 1, i = 0, n = arr.length;
    while (true) {
        if (i < n && arr[i] === current) {
            i++;
        } else {
            missingCount++;
            if (missingCount === k) {
                return current;
            }
        }
        current++;
    }
}

// Test
console.log(findKthPositive([2,3,4,7,11], 5)); // 9

Line Notes

let missingCount = 0Initialize missing count

let current = 1Start checking from 1

if (i < n && arr[i] === current)Check if current number is in array

missingCount++Increment missing count if current missing

if (missingCount === k)Return current when kth missing found

⏱

Complexity

TimeO(k + n)

SpaceO(1)

We potentially iterate up to k missing numbers and scan through the array with pointer i. For large k, this is inefficient.

💡 If k=10^5, this means up to 100,000 iterations, which is slow but still feasible; for larger k, it becomes impractical.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(k + n)`	`O(1)`	No	N/A	Mention only - never code for large inputs
2. Binary Search on Missing Count	`O(log n)`	`O(1)`	No	N/A	Optimal approach to code in interviews
3. Direct Mathematical Calculation + Binary Search	`O(log n)`	`O(1)`	No	N/A	Best practical approach combining math and binary search

Practice

(1/5)

1. Given the following code for finding a peak element, what is the final output when the input array is [1, 3, 2]?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid + 1]:
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

print(findPeakElement([1, 3, 2]))

easy

A. None of the above

B. 0

C. 2

D. 1

2. Given the following code snippet, what is the final output when running with piles = [3, 6, 7, 11] and h = 8?

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += ceil(pile / speed)
        if hours > h:
            return false
    return true

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)
    while low < high:
        mid = (low + high) // 2
        if can_finish(piles, mid, h):
            high = mid
        else:
            low = mid + 1
    return low

piles = [3,6,7,11]
h = 8
print(minEatingSpeed(piles, h))

easy

A. 3

B. 4

C. 5

D. 6

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Trace first call binarySearch(0, 2)

Step 2: Trace second call binarySearch(0, 1)

Step 3: Trace third call binarySearch(1, 1)

Final Answer:

Quick Check:

Solution

Step 1: Trace binary search iterations

Step 2: Return final low value

Final Answer:

Quick Check:

Solution

Step 1: Initialize min-heap with first elements

Step 2: Extract elements until count == k

Final Answer:

Quick Check:

Solution

Step 1: Identify outer loop complexity

Step 2: Identify inner loop complexity

Final Answer:

Quick Check:

Solution

Step 1: Understand matrix constraints

Step 2: Evaluate approaches

Step 3: Consider sorting columns

Final Answer:

Quick Check:

Ready to prove it?