Log inSign up
easyLeetCodeNot Started

Kth Missing Positive Number

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array arr of positive integers sorted in a strictly ascending order, and an integer k.

Return the kth positive integer that is missing from this array.

Example 1 · Standard Missing Elements:

Input: arr = [2, 3, 4, 7, 11], k = 5
Output: 9
Explanation: The missing positive integers are [1, 5, 6, 8, 9, 10, 12, ...]. The 1st missing is 1, 2nd is 5, 3rd is 6, 4th is 8, and the 5th missing is 9.

Example 2 · All Missing Elements After Array:

Input: arr = [1, 2, 3, 4], k = 2
Output: 6
Explanation: No integers are missing inside the array [1, 2, 3, 4]. The missing integers start after 4: [5, 6, 7, ...]. The 2nd missing is 6.

Example 3 · Missing Elements Before Array:

Input: arr = [7, 8, 9], k = 3
Output: 3
Explanation: The missing positive integers are [1, 2, 3, 4, 5, 6, ...]. The 3rd missing positive integer is 3.

Constraints:

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 1000
  • 1 <= k <= 1000
  • arr[i] < arr[j] for 1 <= i < j <= arr.length (strictly increasing)

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Understanding 1-based indexing for positive integers (1, 2, 3...)
  • Linear array traversal
  • Binary Search on monotonic predicate functions

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate the missing count formula at any array index: missingCount = arr[i] - (i + 1).
  • Understand why shifting k forward for every element <= k correctly calculates the missing number.
  • Implement the optimal O(log N) binary search technique.
  • Handle all boundary edge cases (k before first element, k after last element).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Given a strictly sorted array of positive integers and asked for the kth missing integer.
  • The natural sequence is 1, 2, 3, ..., but elements are skipped in the input array.
  • The count of missing elements up to index i is strictly monotonic: missing(i) = arr[i] - (i + 1).

Algorithmic Decision Tree:

  • If N <= 1000: A simple linear scan incrementing k whenever arr[i] <= k runs in O(N) time with O(1) space.
  • If N is large (up to 105): Use Binary Search on the missing count function in O(log N) time and O(1) space.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Hash Set / Lookup Table

Intuition

Store all elements of arr in a hash set, then iterate from positive integer 1 upwards, counting missing numbers until the kth is found.

Algorithm

  1. Insert all elements of arr into a hash set present.
  2. Initialize curr = 1 and missingCount = 0.
  3. While missingCount < k:
  4. If curr is not in present:
  5. Increment missingCount.
  6. If missingCount == k, return curr.
  7. Increment curr.
  8. Return curr.

Hash Set Lookup

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 4, 7, 11]
Current operationSTEP 1 OF 6
Phase 1 — Populate Set: Store elements { 2, 3, 4, 7, 11 } in set
Visual state
Values and pointers at this exact step
array
S
2
3
4
7
11
0
↑ Cand: 1
1
2
3
4
Variables at this step
Candidate
1
missingCount
0
k
5
Check / comparison
Set populated.
Decision / next transition
Begin testing candidates from 1.
Why this step matters

Phase 1 — Populate Set: Store elements { 2, 3, 4, 7, 11 } in set. Initialize candidate = 1, missingCount = 0, target k = 5.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3#include <vector>
4using namespace std;
5
6// Brute Force: Hash Set checking positive integers from 1 upwards
7int findKthPositive(vector<int>& arr, int k) {
8 unordered_set<int> present(arr.begin(), arr.end());
9 int curr = 1;
10 int missingCount = 0;
11
12 while (true) {
13 if (present.find(curr) == present.end()) {
14 missingCount++;
15 if (missingCount == k) {
16 return curr;
17 }
18 }
19 curr++;
20 }
21}
22
23int main() {
24 vector<int> arr = {2, 3, 4, 7, 11};
25 int k = 5;
26 cout << "Output: " << findKthPositive(arr, k) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Hash Set / Lookup Table.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Hash Set / Lookup Table.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Linear Displacement

Intuition

Iterate through the sorted array; for every element that is less than or equal to k, increment k by 1.

Algorithm

  1. Iterate through each number num in arr:
  2. If num <= k:
  3. k++ (increment k by 1 to skip this existing number).
  4. Else:
  5. Break out of loop (since array is sorted, all subsequent numbers are > k).
  6. Return k.

Linear Displacement

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 4, 7, 11]
Current operationSTEP 1 OF 6
Phase 1 — Invariant Rule: If an element in arr is <= k, it pushes the k-th missing number one position further right (k++)
Visual state
Values and pointers at this exact step
array
S
2
3
4
7
11
0
↑ arr[0] <= 5
1
2
3
4
Variables at this step
Current Element
2
k
6
Check / comparison
Start with k = 5. Check arr[0] = 2.
Decision / next transition
2 <= 5 -> increment k to 6.
Why this step matters

Phase 1 — Invariant Rule: If an element in arr is <= k, it pushes the k-th missing number one position further right (k++).

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Linear Displacement: Shift k for every element <= k
6int findKthPositive(vector<int>& arr, int k) {
7 for (int num : arr) {
8 if (num <= k) {
9 k++;
10 } else {
11 break; // Since array is sorted, remaining elements are > k
12 }
13 }
14 return k;
15}
16
17int main() {
18 vector<int> arr = {2, 3, 4, 7, 11};
19 int k = 5;
20 cout << "Output: " << findKthPositive(arr, k) << endl;
21 return 0;
22}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — Linear Displacement.
  • Space complexity: O(N) — Space complexity for Approach 2: Better — Linear Displacement.

3. Optimal — Binary Search (Logarithmic Time)

Intuition

Binary search for the insertion index using the formula missing = arr[mid] - (mid + 1). At termination, the answer is left + k.

Algorithm

  1. Initialize left = 0 and right = arr.length - 1.
  2. While left <= right:
  3. Calculate mid = left + (right - left) / 2.
  4. Calculate missing = arr[mid] - (mid + 1).
  5. If missing < k:
  6. left = mid + 1.
  7. Else:
  8. right = mid - 1.
  9. Return left + k.

Binary Search (Logarithmic Time O(log N))

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [2, 3, 4, 7, 11]
Current operationSTEP 1 OF 6
Phase 1 — Formula Invariant: For any index i, the count of missing numbers before index i is: missing = arr[i] - (i + 1)
Visual state
Values and pointers at this exact step
array
S
2
3
4
7
11
0
↑ low=0
1
2
↑ mid=2
3
4
↑ high=4
Variables at this step
low
0
high
4
mid
2
Check / comparison
Binary search on missing counts.
Decision / next transition
Compute mid = (0 + 4) / 2 = 2.
Why this step matters

Phase 1 — Formula Invariant: For any index i, the count of missing numbers before index i is: missing = arr[i] - (i + 1). low = 0, high = 4.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Optimal: Binary Search on Missing Count in O(log N) time
6int findKthPositive(vector<int>& arr, int k) {
7 int left = 0;
8 int right = arr.size() - 1;
9
10 while (left <= right) {
11 int mid = left + (right - left) / 2;
12 // Missing count before arr[mid]
13 int missing = arr[mid] - (mid + 1);
14
15 if (missing < k) {
16 left = mid + 1;
17 } else {
18 right = mid - 1;
19 }
20 }
21
22 // At loop exit, left is the number of elements in arr smaller than answer
23 return left + k;
24}
25
26int main() {
27 vector<int> arr = {2, 3, 4, 7, 11};
28 int k = 5;
29 cout << "Output: " << findKthPositive(arr, k) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — Binary Search (Logarithmic Time).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — Binary Search (Logarithmic Time).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Hash Set SimulationO(N + k)O(N)Very easy to understand conceptually.Baseline / conceptual only.
2.Linear DisplacementO(N)O(1)Very clean 4-line implementation, O(1) space.Good initial solution, interviewer will ask for O(log N).
3.Binary Search on Missing CountOptimalO(log N)O(1)Optimal logarithmic time, O(1) extra space.Optimal gold standard for interviews.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Missing Number Comes Before Entire Array — Input: arr = [5, 6, 7, 8], k = 2, Expected: 2 — Since 1, 2, 3, 4 are missing before 5, the 2nd missing is 2. Binary search should terminate with left = 0, returning 0 + 2 = 2.
  • Missing Number Comes After Entire Array — Input: arr = [1, 2, 3, 4], k = 3, Expected: 7 — No elements missing inside arr. The 3rd missing after 4 is 7. Binary search terminates with left = 4, returning 4 + 3 = 7.
  • First Element is 1 and k = 1 — Input: arr = [1, 3, 5], k = 1, Expected: 2 — First missing integer is 2. Ensure formulas don't produce off-by-one errors.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Initial Thoughts — Mention the O(N) linear scan first to demonstrate understanding: 'Since the array is sorted, every element <= k shifts our missing answer by 1.'
  2. Binary Search Transition — Immediately follow up: 'Since the array is sorted and missing(i) is monotonic, we can optimize this to O(log N) using Binary Search.'
  3. Math Explanation — Clearly derive why left + k is the answer on the whiteboard: explain that arr[right] has fewer than k missing numbers, and the remaining missing numbers fall beyond arr[right].

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Kth Missing Positive Number?

2.Why is the brute force approach suboptimal for large inputs in Kth Missing Positive Number?

3.Which data structure or technique enables the optimal solution for Kth Missing Positive Number?

Back to DSA Sheet