Domain 1EasyCORE

Kth Missing Positive Number

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table

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 kth missing 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

  1. Binary Search Setup: We initialize two pointers, left and right, to represent the range of indices in the array.
  2. Count Missing Numbers: For each midpoint index mid, we calculate how many numbers are missing up to that point using the formula arr[mid] - (mid + 1).
  3. Adjust Pointers: If the count of missing numbers is less than k, it means the kth missing number is beyond this midpoint, so we move the left pointer to mid + 1. Otherwise, we move the right pointer to mid.
  4. Find Result: Once the loop ends, the left pointer will indicate the position where the count of missing numbers reaches or exceeds k. The kth missing number can be calculated as left + 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, left will remain 0, and the result will be k, 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 kth missing number is beyond the maximum value in the array.