PPractick

The problem

A ticketing system issued seat numbers in increasing order, but some numbers were skipped. Given the sorted list of issued numbers, the box office wants the k-th smallest positive number that was never issued, to reuse it. Walking up from 1 is O(n + k). The binary search insight: at index i, the number of missing positives before arr[i] is exactly arr[i] − (i + 1), since without gaps arr[i] would equal i + 1. That count only grows along the array, so binary search finds where the k-th missing number falls.

Example: arr = [2, 3, 4, 7, 11], k = 5 → 9 (missing: 1, 5, 6, 8, 9, ...).

Function signature

int findKthPositive(const vector<int>& arr, int k);  // arr strictly increasing positive integers

Test cases

Input (arr, k)	Output	Explanation
([2, 3, 4, 7, 11], 5)	9	Missing 1, 5, 6, 8, 9
([1, 2, 3, 4], 2)	6	Missing 5, 6
([5, 6, 7], 4)	4	Missing 1, 2, 3, 4 before the array starts
([1], 1)	2
([2], 1)	1

(Confirm: arr is strictly increasing; the answer may be smaller than arr[0] or larger than the last element.)

How interviewers phrase it

• "Return the kth positive integer missing from a sorted array" (LeetCode 1539).
• "Can you do better than O(n)?"

Clarifying questions to ask

1. Is the array strictly increasing?
2. Positive integers only?
3. Could the answer lie beyond the last element?

Follow-ups to expect

1. "Why is arr[i] − (i + 1) the number of missing values before arr[i]?"
2. "What does the binary search find?"
3. "Why is the answer lo + k?"
4. "What's the linear approach?"
5. "Complexity?"

Related questions

• Find missing number Easy
• Search X in sorted array Easy
• Lower Bound Easy
• Upper Bound Easy
• Search insert position Easy
• Floor and Ceil in Sorted Array Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in