1539. Kth Missing Positive Number
Problem Description
The problem provides us with an array arr
which contains positive integers in increasing order. Note that the array might not contain some positive integers; hence it's not consecutive. We're also given an integer k
. Our goal is to find the kth
positive integer that is not present in the array arr
.
For example, if the array is [2, 3, 4, 7, 11]
and k
is 5, we need to find the 5th positive integer missing from this sequence. The missing numbers are [1, 5, 6, 8, 9, 10,...]
, and the 5th one is 9, which will be our answer.
Intuition
To find the kth
missing positive integer, we're using a binary search algorithm to optimize the process. Binary search helps us reduce the search space to find the answer quickly, instead of inspecting each missing number one by oneāwhich would be less efficient.
The essence of the solution lies in understanding how we can identify if a number is kth
missing or not. Since the array is strictly increasing, the number of positive integers missing before any array element arr[i]
can be found as arr[i] - i - 1
. This is because if there were no missing numbers, the value at arr[i]
would be i + 1
.
The binary search algorithm exploits this by repeatedly halving the array to find the smallest arr[i]
such that arr[i] - i - 1
is still at least k
. The algorithm keeps moving the left
or right
boundaries according to the comparison of arr[mid] - mid - 1
with k
.
Once the left
boundary crosses the right
boundary, we know that the missing number we are looking for is not in the array. It must be between arr[left - 1]
and arr[left]
(or after arr[left - 1]
if left
is equal to the length of the array). Hence, the answer can be computed by adding k
to arr[left - 1] - (left - 1) - 1
which is the number of missing numbers before arr[left - 1]
.
This solution has a time complexity of O(log n), where n is the number of elements in arr
, which is significantly faster than a linear search that would have a time complexity of O(n).
Learn more about Binary Search patterns.
Solution Approach
The implemented solution employs a binary search algorithm to efficiently locate the kth
missing positive integer in the sorted array arr
. Binary search is a popular algorithm for finding an item in a sorted list by repeatedly dividing the search interval in half.
Let's walk through the steps of the algorithm using the provided Python code:
- Check if
k
is less than the first element: Before starting the binary search, it's checked whetherarr[0]
is greater thank
. If it is,k
itself is thekth
missing number since allk
missing numbers are beforearr[0]
. The code returnsk
directly in this case.
if arr[0] > k: return k
- Initialize the binary search boundaries: The variables
left
andright
are initialized to represent the search space of the binary search, whereleft
is the start index (0) andright
is the length of the arrayarr
.
left, right = 0, len(arr)
-
Perform Binary Search: The binary search loop continues until
left
is less thanright
. In each iteration, a midpointmid
is calculated. The algorithm checks the number of missing numbers up toarr[mid]
by calculatingarr[mid] - mid - 1
.- If the calculated number of missing elements is greater than or equal to
k
, it means thekth
missing number is before or atmid
. We setright
tomid
. - If the number is less than
k
, we moveleft
forward tomid + 1
.
- If the calculated number of missing elements is greater than or equal to
while left < right: mid = (left + right) >> 1 if arr[mid] - mid - 1 >= k: right = mid else: left = mid + 1
The >> 1
is a bitwise operation equivalent to dividing by 2, efficiently calculating the mid index.
- Calculate and Return the Missing Number: After the loop, the
kth
missing number is not present in the array, and it must be found after the number at indexleft - 1
. To find it, the formulaarr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)
is used to calculate how many numbers are missing up toarr[left - 1]
, and then addk
to reach thekth
missing number.
return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)
This formula takes the last known value before the kth
missing number, adds k
, and then subtracts the count of missing numbers before the arr[left - 1]
to land exactly on the kth
missing number.
This approach results in an effective solution with a time complexity of O(log n), leveraging the power of binary search to drastically reduce the potential search space compared to more naive approaches.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with an example. Consider the array arr = [2, 3, 7, 11, 12]
, and we want to find the 5th
missing positive integer (k = 5
).
-
Initial check: We first check if the first element of the array is greater than
k
. Sincearr[0] = 2
is not greater than5
, we move on to the binary search. No numbers are returned in this initial step. -
Set up binary search: We then initialize the binary search boundaries with
left
set to0
andright
to the length of the array, which is5
. -
Binary search: Next, we begin the binary search:
- Initial values are
left = 0
andright = 5
. - First iteration: Calculate
mid = (0 + 5) >> 1 = 2
. Atarr[2] = 7
, the count of missing numbers is7 - 2 - 1 = 4
, which is less thank = 5
. Thus, we updateleft
tomid + 1 = 3
. - Second iteration: New midpoint is
mid = (3 + 5) >> 1 = 4
. Atarr[4] = 12
, the missing count is12 - 4 - 1 = 7
, which is greater thank
. Now we updateright
tomid = 4
. - Third iteration: As
left < right
no longer holds (sinceleft = 4
andright = 4
), we exit the loop.
- Initial values are
-
Determine answer: We are now left with
left = 4
. The number in the array at indexleft - 1 = 3
isarr[3] = 11
. Fromarr[3]
, we have11 - 3 - 1 = 7
missing numbers before it. Thekth
missing number is then calculated asarr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)
which equals11 + 5 - 7 = 9
.
Hence, the 5th
missing positive integer is 9
. This matches our expectation because the missing numbers before 9
are [1, 4, 5, 6, 8]
, and 9
is indeed the fifth missing number.
Solution Implementation
1from typing import List
2
3class Solution:
4 def findKthPositive(self, arr: List[int], k: int) -> int:
5 # If the first element is larger than k, the k-th positive missing number would be k
6 if arr[0] > k:
7 return k
8
9 # Use binary search to find k-th positive missing number
10 left, right = 0, len(arr)
11 while left < right:
12 mid = (left + right) // 2 # Use integer division for Python 3
13
14 # Calculate the number of negative elements up to index mid
15 missing_until_mid = arr[mid] - mid - 1
16
17 # If the number of missing elements is greater or equals k, look in the left half
18 if missing_until_mid >= k:
19 right = mid
20 else:
21 left = mid + 1 # Otherwise, look in the right half
22
23 # After binary search, calculate the k-th missing positive number
24 # by adding k to the number at the index `left - 1` in the array
25 # and then adjust it by subtracting the missing count until that point
26 missing_until_left_minus_one = arr[left - 1] - (left - 1) - 1
27 kth_missing_positive = arr[left - 1] + k - missing_until_left_minus_one
28 return kth_missing_positive
29
1class Solution {
2 public int findKthPositive(int[] arr, int k) {
3 // If the first element in the array is greater than k, the kth missing
4 // positive number would just be k, since all numbers before arr[0] are missing
5 if (arr[0] > k) {
6 return k;
7 }
8
9 // Initializing binary search boundaries
10 int left = 0, right = arr.length;
11 while (left < right) {
12 // Finding the middle index using bitwise operator to avoid overflow
13 int mid = (left + right) >> 1;
14
15 // If the number of missing numbers until arr[mid] is equal to or greater than k
16 // then the kth missing number is to the left of mid, including mid itself
17 if (arr[mid] - mid - 1 >= k) {
18 right = mid;
19 } else {
20 // Otherwise, the kth missing number is to the right of mid, so we move left
21 left = mid + 1;
22 }
23 }
24
25 // Once left is the smallest index such that the number of missing numbers until arr[left]
26 // is less than k, the kth positive integer that is missing from the array is on the right
27 // of arr[left-1]. To find it, we add k to arr[left-1] and then subtract the number of
28 // missing numbers until arr[left-1] (which is arr[left-1] - (left-1) - 1).
29 return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1);
30 }
31}
32
1#include <vector>
2
3class Solution {
4public:
5 int findKthPositive(std::vector<int>& arr, int k) {
6 // If the first element in the array is greater than k, the kth missing
7 // number must be k itself.
8 if (arr[0] > k) {
9 return k;
10 }
11
12 int left = 0;
13 int right = arr.size(); // The right boundary for the binary search.
14
15 // Binary search to find the lowest index such that the number of
16 // positive integers missing before arr[index] is at least k.
17 while (left < right) {
18 int mid = left + (right - left) / 2; // Prevents potential overflow.
19
20 // If the number of missing numbers up to arr[mid] is at least k,
21 // we need to search on the left side (including mid).
22 if (arr[mid] - mid - 1 >= k) {
23 right = mid;
24 } else {
25 left = mid + 1; // Otherwise, we search on the right side.
26 }
27 }
28
29 // After the loop, left is the smallest index such that the number of
30 // positive integers missing before arr[left] is at least k. Using the
31 // index left - 1, we find the kth missing number.
32 return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1);
33 }
34};
35
1function findKthPositive(arr: number[], k: number): number {
2 // If the first element in the array is greater than k, then the kth missing number must be k itself.
3 if (arr[0] > k) {
4 return k;
5 }
6
7 let left = 0;
8 let right = arr.length; // The right boundary for the binary search.
9
10 // Binary search to find the lowest index such that the number of
11 // positive integers missing before arr[index] is at least k.
12 while (left < right) {
13 let mid = left + Math.floor((right - left) / 2); // Math.floor is used to prevent floats since TypeScript does not do integer division.
14
15 // If the number of missing numbers up to arr[mid] is at least k,
16 // we need to search on the left side (including mid).
17 if (arr[mid] - mid - 1 >= k) {
18 right = mid;
19 } else {
20 left = mid + 1; // Otherwise, we search on the right side.
21 }
22 }
23
24 // After the loop, left is the smallest index such that the number of
25 // positive integers missing before arr[left] is at least k. Using the
26 // index left - 1, we find the kth missing number.
27 return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1);
28}
29
Time and Space Complexity
Time Complexity
The provided code uses a binary search algorithm to find the k-th positive integer that is missing from the array arr
. This is evident from the while loop that continues halving the search space until left
is less than right
. In a binary search, the time complexity is O(log n)
where n
is the number of elements in arr
, because with each comparison, the search space is reduced by half.
Space Complexity
The space complexity of the code is O(1)
since there are only a few variables used (left
, right
, mid
, k
), and no additional data structures or recursive calls that would require more space proportional to the input size. The algorithm operates in-place with constant extra space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!