algoadvance

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k, return the k-th missing positive number starting from the left.

Clarifying Questions

1. Input constraints:
   • What is the size range of the input array arr?
   • What is the range of integers in arr?
   • What is the acceptable range for k?
2. Output expectations:
   • Should the output always be within the range of positive integers?
   • What should be returned if k is impossibly large?

Strategy

1. Define the problem with sample cases:
   • For example:
     • Input: arr = [2, 3, 4, 7, 11], k = 5
     • Output: 9 (Missing numbers sequence: [1, 5, 6, 8, 9, 10, …])
2. Outline the plan:
   • Maintain a pointer missing_count to track the number of missing numbers.
   • Iterate through the natural numbers starting from 1 and compare with elements in arr.
   • Keep a counter for missing numbers until we reach the k-th missing number.
   • Use a while loop to continue checking each number for whether it is missing from the array arr.

Time Complexity

• The solution has a linear complexity in the worst case, O(n + k), where n is the length of the array and k is the k-th missing number being checked.

Code

def findKthPositive(arr, k):
    missing_count = 0
    current = 1
    index = 0
    n = len(arr)
    
    while missing_count < k:
        if index < n and arr[index] == current:
            index += 1
        else:
            missing_count += 1
        
        if missing_count < k:
            current += 1
    
    return current

# Test the function
print(findKthPositive([2, 3, 4, 7, 11], 5))  # Output: 9
print(findKthPositive([1, 2, 3, 4], 2))      # Output: 6

Explanation of Code:

• Initialize missing_count to count the missing numbers.
• Initialize current to evaluate each natural number sequentially.
• Use index to track the position within arr.
• Loop until the k-th missing number is found:
  • If current is present in arr, move to the next element in arr.
  • If current is missing in arr, increment the missing_count.
  • Increment current after updating either missing_count or index.
• Once missing_count equals k, the last value of current will be the k-th missing number.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?