Skip to main content

Kth Missing Positive Number Solution

In this page, we will solve the Kth Missing Positive Number problem using different approaches: linear search and binary search. We will provide the implementation of the solution in JavaScript, TypeScript, Python, Java, C++, and more.

Problem Description

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.

Examples

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

Solution for Kth Missing Positive Number Problem

Intuition and Approach

The problem can be solved using linear search or binary search. Linear search is straightforward, while binary search is more efficient.

We iterate through the positive integers, checking if they are present in the array. If a number is missing, we decrement k. When k reaches 0, we have found the kth missing positive integer.

Implementation

Live Editor
function kthMissingPositiveNumber() {
  const arr = [2, 3, 4, 7, 11];
  const k = 5;

  const findKthPositive = function(arr, k) {
    let missingCount = 0;
    let current = 1;

    while (missingCount < k) {
      if (!arr.includes(current)) {
        missingCount++;
      }
      if (missingCount < k) {
        current++;
      }
    }

    return current;
  };

  const result = findKthPositive(arr, k);
  return (
    <div>
      <p>
        <b>Input:</b> arr = {JSON.stringify(arr)}, k = {k}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}
Result
Loading...

Codes in Different Languages

Written by @manishh12
 function findKthPositive(arr, k) {
let missingCount = 0;
let current = 1;

while (missingCount < k) {
if (!arr.includes(current)) {
missingCount++;
}
if (missingCount < k) {
current++;
}
}

return current;
}

Complexity Analysis

  • Time Complexity: O(n×m)O(n \times m), where n is the length of the array and m is the kth missing positive number.
  • Space Complexity: O(1)O(1), as no additional space is used.
  • The time complexity is high due to the nested loops in arr.includes().
Note

By using both linear search and binary search approaches, we can efficiently solve the Kth Missing Positive Number problem. The binary search approach is more efficient, especially for larger inputs.

References