1539. Kth Missing Positive Number LeetCode Solution

In this guide, you will get 1539. Kth Missing Positive Number LeetCode Solution with the best time and space complexity. The solution to Kth Missing Positive Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Kth Missing Positive Number solution in C++
4. Kth Missing Positive Number solution in Java
5. Kth Missing Positive Number solution in Python
6. Additional Resources

Problem Statement of Kth Missing Positive Number

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.
Return the kth positive integer that is missing from this array.

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:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr[i] < arr[j] for 1 <= i < j <= arr.length

Follow up:
Could you solve this problem in less than O(n) complexity?

Complexity Analysis

• Time Complexity: O(\log n)
• Space Complexity: O(1)

1539. Kth Missing Positive Number LeetCode Solution in C++

class Solution {
 public:
  int findKthPositive(vector<int>& arr, int k) {
    int l = 0;
    int r = arr.size();

    // Find the first index l s.t. nMissing(l) = A[l] - l - 1 >= k.
    while (l < r) {
      const int m = (l + r) / 2;
      if (arr[m] - m - 1 >= k)
        r = m;
      else
        l = m + 1;
    }

    // The k-th missing positive
    // = A[l - 1] + k - nMissing(l - 1)
    // = A[l - 1] + k - (A[l - 1] - (l - 1) - 1)
    // = A[l - 1] + k - (A[l - 1] - l)
    // = l + k
    return l + k;
  }
};
/* code provided by PROGIEZ */

1539. Kth Missing Positive Number LeetCode Solution in Java

class Solution {
  public int findKthPositive(int[] arr, int k) {
    int l = 0;
    int r = arr.length;

    // Find the first index l s.t. nMissing(l) = A[l] - l - 1 >= k.
    while (l < r) {
      final int m = (l + r) / 2;
      if (arr[m] - m - 1 >= k)
        r = m;
      else
        l = m + 1;
    }

    // The k-th missing positive
    // = A[l - 1] + k - nMissing(l - 1)
    // = A[l - 1] + k - (A[l - 1] - (l - 1) - 1)
    // = A[l - 1] + k - (A[l - 1] - l)
    // = l + k
    return l + k;
  }
}
// code provided by PROGIEZ

1539. Kth Missing Positive Number LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.