algoadvance

Leetcode 1539. Kth Missing Positive Number

Problem Statement

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

Example 1:

Input: arr = [2,3,4,7,11], k = 5
Output: 9
Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2
Output: 6
Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

Clarifying Questions

  1. Q: Are there any gaps between consecutive elements of the array? A: Yes, the numbers in the array increase strictly, so there can be gaps.

  2. Q: What is the expected return value if k is out of the bounds of the missing sequence? A: The constraints guarantee that k is always a valid positive integer, so it will be within the bounds of the missing positive numbers.

Strategy

  1. Initialization:
    • Define a counter missing_count to track the number of missing positive numbers found so far.
    • Use a variable current to track the current positive integer being checked.
    • Use an index i to iterate through the elements of the array.
  2. Iteration:
    • Iterate from the smallest positive integer 1 upwards.
    • If the current integer is in the array (i.e., arr[i] == current), move to the next element in the array by incrementing i.
    • If the current integer is not in the array, increment the missing_count.
    • When missing_count is equal to k, the current integer is the k-th missing positive number.
  3. Termination:
    • Return the current number when the missing_count reaches k.

Code

#include <vector>
#include <iostream>

int findKthPositive(std::vector<int>& arr, int k) {
    int missing_count = 0;
    int current = 1;
    int i = 0;
    
    while (true) {
        // If current number is in the array, move to the next element in the array
        if (i < arr.size() && arr[i] == current) {
            i++;
        } else {
            // If current number is missing, increment the missing count
            missing_count++;
            // If missing count reaches k, return the current number
            if (missing_count == k) {
                return current;
            }
        }
        // Move to the next number
        current++;
    }
}

int main() {
    std::vector<int> arr1 = {2, 3, 4, 7, 11};
    int k1 = 5;
    std::cout << "The 5th missing positive number is: " << findKthPositive(arr1, k1) << std::endl;

    std::vector<int> arr2 = {1, 2, 3, 4};
    int k2 = 2;
    std::cout << "The 2nd missing positive number is: " << findKthPositive(arr2, k2) << std::endl;

    return 0;
}

Time Complexity

The time complexity of this solution is O(n + k) where n is the length of the array. This is because in the worst case, we might need to iterate through all elements of the array and all missing numbers up to k. However, due to the constraints provided (1 ≤ arr.length ≤ 1000 and 1 ≤ k ≤ 1000), this time complexity is acceptable.

In practice, the number of required operations will often be considerably less since we quickly skip over existing array elements.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI