Skip to main content
Talentd

Kth Missing Positive Number - Solution & Explanation

EasyArrayBinary Search14 min readAsked at: Amazon, Microsoft, Meta +6
Practice this problem

Problem Statement

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

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

 

Example 1:

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

Example 2:

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

 

Constraints:

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

 

Follow up:

Could you solve this problem in less than O(n) complexity?

Approach Overview

Problem Overview: You are given a strictly increasing sorted array of positive integers. Some numbers are missing from the sequence starting at 1. The task is to return the k-th missing positive number that does not appear in the array.

Approach 1: Iterative Approach (O(n) time, O(1) space)

This method walks through the array while tracking how many numbers are missing before each element. For an index i, the number of missing integers before arr[i] equals arr[i] - (i + 1). That expression works because a perfect sequence without gaps would contain i + 1 numbers up to that index. As you iterate, compare the missing count with k. Once the missing count becomes greater than or equal to k, the answer lies before the current element and can be computed directly using arithmetic. If the loop finishes without reaching k, the remaining missing numbers occur after the last element, so you extend the sequence beyond arr[n-1]. This approach is simple and reliable when scanning the array once is acceptable.

The technique relies only on index arithmetic and sequential traversal, making it a clean application of basic array processing. Interviewers often expect candidates to derive the missing-count formula during discussion because it shows you understand how indices relate to ideal sequences.

Approach 2: Binary Search Optimization (O(log n) time, O(1) space)

The sorted property of the array enables a faster solution using binary search. Instead of scanning every element, search for the first index where the number of missing values becomes at least k. At each midpoint mid, compute the missing count using the same formula: missing = arr[mid] - (mid + 1). If this value is less than k, move the search window to the right. Otherwise, move left to find the earliest position where the missing count reaches k.

After the search finishes, the answer can be derived using the final left boundary. The key observation: the k-th missing number must appear between two array elements or after the array ends. Binary search efficiently finds that boundary in logarithmic time without explicitly enumerating missing values.

This optimization becomes valuable when the array is large. The algorithm performs only logarithmic comparisons while still using constant memory.

Recommended for interviews: Start by explaining the iterative logic because it clearly demonstrates how missing numbers relate to array indices. Once that idea is established, transition to the binary search solution. Interviewers usually expect the optimized O(log n) approach for a sorted array, since recognizing the monotonic missing-count pattern shows strong algorithmic reasoning.

Approach 1: Iterative Approach

This approach involves iterating through the array and maintaining a counter for missing positive integers. We start with the first positive number, which is 1, and determine if it is missing by comparing it to the current element in the array. If the number is missing, we decrement our k value. When k reaches zero, we have found our k-th missing number.

This C solution uses a simple iteration where it keeps track of what the next missing number should be while iterating over the array. It compares the current number to the next expected missing number. If the expected number is equal to the array number, it means the number is not missing, so it moves to the next array element. Otherwise, it increases the missing count and checks if it matches k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + k), where n is the length of the array. Space Complexity: O(1), as we are using constant extra space.

Try this approach in the editor →

Approach 2: Binary Search Optimization

By using binary search, a more efficient solution can be developed that reduces unnecessary checks. The key observation is that the number of missing integers before arr[i] can be calculated as arr[i] - (i + 1), which helps in deducing the position of the k-th missing number without iterating through every integer.

This implementation uses binary search to efficiently find the k-th missing positive number. The search focuses on a "missing" variable that tells how many numbers are missing up to the mid-point in the array.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(log n), Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Iterative Approach

Time Complexity: O(n + k), where n is the length of the array. Space Complexity: O(1), as we are using constant extra space.

Binary Search Optimization

Time Complexity: O(log n), Space Complexity: O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative ApproachO(n)O(1)Simple implementation when scanning the array once is acceptable
Binary Search OptimizationO(log n)O(1)Best choice for large sorted arrays where logarithmic search improves performance

Video Solution

BS-16. Kth Missing Positive Number | Maths + Binary Search • take U forward • 388,608 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Kth Missing Positive Number easy or hard?
LeetCode classifies this problem as Easy. The iterative O(n) solution is straightforward once you understand how to compute missing numbers using arr[i] - (i + 1). The binary search optimization adds a moderate algorithmic twist but follows standard sorted-array search patterns.
Kth Missing Positive Number Python or Java solution?
Both Python and Java implementations follow the same logic. The iterative solution scans the array while tracking missing counts, while the binary search version repeatedly checks arr[mid] - (mid + 1) to locate the kth missing value in O(log n) time.
How to solve Kth Missing Positive Number in O(log n)?
Use binary search on the array to locate the first index where the number of missing values is at least k. The missing count before index i is arr[i] - (i + 1). Compare this value with k while adjusting the search range. Once the boundary is found, compute the exact kth missing value using the index and k.
What is the best approach for Kth Missing Positive Number?
Binary search is the most efficient approach because the array is sorted. By computing how many numbers are missing before each index using arr[i] - (i + 1), you can binary search for the first position where the missing count reaches k. This reduces the time complexity to O(log n) with constant extra space.
Is Kth Missing Positive Number asked at Google/Amazon/Meta?
Variations of this problem appear in interviews at companies like Amazon, Google, and Meta because it tests reasoning about sorted arrays and binary search boundaries. Candidates must recognize the mathematical relationship between indices and missing values.
What data structure is used in Kth Missing Positive Number?
The problem primarily uses arrays. The optimized solution also applies binary search on the array indices to exploit the monotonic increase of missing counts across the sorted sequence.
What is the time complexity of Kth Missing Positive Number?
Two common solutions exist. A straightforward iterative scan runs in O(n) time and O(1) space. The optimized binary search solution runs in O(log n) time and O(1) space by leveraging the sorted nature of the array.

Ready to solve this problem?

Practice Kth Missing Positive Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Append K Integers With Minimal Sum