Coding Interview PatternsKth Missing Positive Number
EasyCyclic Sort

Kth Missing Positive Number

Explanation & Solution

Practice Problem

Description

Given an array arr of positive integers sorted in strictly increasing order, and an integer k, return the k-th positive integer that is missing from this array.

Input:arr = [2, 3, 4, 7, 11], k = 5
0
2
1
3
2
4
3
7
4
11

Output: 9

Explanation: The missing positives in order are: 1, 5, 6, 8, 9, 10... The 5th missing is 9.

Constraints

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000
  • 1 <= k <= 1000
  • arr[i] < arr[i+1]

Approach

Cyclic Sort pattern

1. The Counting Approach

  • Iterate through every positive integer starting from 1
  • Maintain a pointer i into arr and a count of missing numbers found

2. For Each Candidate Number

  • If the current number num equals arr[i], it is present — advance i and continue
  • Otherwise, the number is missing — increment missingCount
  • When missingCount === k, return the current num

3. Why Sorted Order Helps

  • Because arr is sorted, comparing the candidate with arr[i] in order is sufficient
  • There is no need to search or use a hash set

4. When the Answer Exceeds the Array

  • If k is large enough that all of arr is exhausted, the loop continues counting missing positives beyond arr[arr.length - 1]
  • The pointer i stops advancing once past the end of arr, and every subsequent num is missing

🧠 Key Insight

  • A binary search approach can solve this in O(log n) by counting how many numbers up to arr[m] are missing (arr[m] - m - 1), but the linear scan is easier to visualize and is fast enough for the given constraints
Time
O(n + k)at most n comparisons with arr plus up to k missing counts
Space
O(1)two integer variables

Visualization

Input:
[2, 3, 4, 7, 11], k = 5
20314273114
—

Press ▶ or use ← → to step through

Pointer iPointer jProcessedDone
11 steps

Solution Code

Previous
Find the Duplicate Number
Next
Find First K Missing Positive Numbers