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.

Description Hints 1 Solution Video 22:52

1539. Kth Missing Positive Number

Easy63.9% acceptance9 companies

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

Return the k^th 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 5^th 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 2^nd 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?

Asked at 9 companies

Meta Tiktok Morgan Stanley

Google Amazon Microsoft Bloomberg

IBM Oracle

Topics

Array Binary Search

Hints open one at a time

Hint 1

Keep track of how many positive numbers are missing as you scan the array.

22:52

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution