We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Kth Missing Positive Number

Number: 1646

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, IBM, Microsoft, Bloomberg, TikTok

Problem Description

Given a sorted array of positive integers (in strictly increasing order) and an integer k, find the kth positive integer that is missing from the array.

Key Insights

  • The number of missing integers until the current element arr[i] can be calculated as arr[i] - (i + 1).
  • Binary search can be employed to efficiently locate the position where the kth missing number would reside.
  • If the kth missing integer is greater than the last element of the array, it can be computed by adding the remaining missing count to the last element.

Space and Time Complexity

Time Complexity: O(log n) using binary search
Space Complexity: O(1)

Solution

We use binary search to determine the smallest index where the count of missing numbers is at least k. At each step, calculate the missing count as arr[mid] - (mid + 1). If this missing count is less than k, the kth missing number must lie on the right, so we shift the left bound. Otherwise, we search on the left side. Finally, if the kth missing positive integer is beyond the array, it can be calculated with the relation: kth missing = k + (length of arr).

Code Solutions

# Python implementation of the solution using binary search.
def findKthPositive(arr, k):
    # Set initial binary search bounds.
    left, right = 0, len(arr) - 1

    while left <= right:
        # Calculate the middle index.
        mid = (left + right) // 2
        # Calculate the number of missing integers up to the current element.
        missing = arr[mid] - (mid + 1)
        
        # If missing numbers are less than k, search in the right half.
        if missing < k:
            left = mid + 1
        else:
            # Otherwise, search in the left half.
            right = mid - 1

    # After binary search, 'left' is the index where missing count is >= k.
    # The kth missing number is k added to the index (position shift).
    return left + k

# Sample usage:
print(findKthPositive([2, 3, 4, 7, 11], 5))  # Output should be 9
← Back to All Questions