1539. Kth Missing Positive Number
Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 54.9%
Problem Breakdown
The problem asks us to find the kth positive integer that is missing from a given sorted array of positive integers. The input consists of an array arr and an integer k. The output should be the kth positive integer that is not present in the array.
Inputs:
arr: A list of positive integers sorted in strictly increasing order.k: An integer representing the position of the missing positive number to find.
Outputs:
- The
kthmissing positive integer.
Implicit Constraints or Edge Cases:
- The array can be empty, which means all positive integers are missing.
- The array might contain all numbers up to a certain point, meaning we need to look beyond the maximum value in the array.
- The array length and values are bounded by 1000, so we don’t have to worry about overflow or extremely large inputs.
Intuition
A brute-force approach would involve iterating through all positive integers starting from 1 and checking if each integer is present in the array. We count how many missing numbers we encounter until we reach the kth one. This approach has a time complexity of O(n + m), where n is the length of the array and m is the value of the kth missing number, which can be inefficient.
A better approach involves using binary search to find the position where the count of missing numbers reaches k. The key insight is that if we know how many numbers are missing up to a certain point in the array, we can determine if the kth missing number lies before or after this point. This reduces the time complexity to O(log n).
Approach
- Binary Search Setup: We initialize two pointers,
leftandright, to represent the range of indices in the array. - Count Missing Numbers: For each midpoint index
mid, we calculate how many numbers are missing up to that point using the formulaarr[mid] - (mid + 1). - Adjust Pointers: If the count of missing numbers is less than
k, it means thekthmissing number is beyond this midpoint, so we move theleftpointer tomid + 1. Otherwise, we move therightpointer tomid. - Find Result: Once the loop ends, the
leftpointer will indicate the position where the count of missing numbers reaches or exceedsk. Thekthmissing number can be calculated asleft + k.
Complexity Analysis
- Time Complexity: O(log n), where n is the length of the array. This is because we are using binary search to find the position.
- Space Complexity: O(1), as we are only using a few extra variables for pointers and calculations.
Solution
def findKthPositive(arr, k):
left, right = 0, len(arr)
while left < right:
mid = (left + right) // 2
# Calculate the number of missing elements up to arr[mid]
if arr[mid] - (mid + 1) < k:
left = mid + 1
else:
right = mid
# The kth missing positive number is at position left + k
return left + k
# Example usage:
print(findKthPositive([2,3,4,7,11], 5)) # Output: 9
print(findKthPositive([1,2,3,4], 2)) # Output: 6
Edge Cases Handled
- Empty Array: If the array is empty,
leftwill remain 0, and the result will bek, which is correct since all positive integers are missing. - All Numbers Present: If all numbers up to a certain point are present, the binary search will correctly identify that the
kthmissing number is beyond the maximum value in the array.