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.

• Linear Search
• Binary Search

Approach 1: Linear Search

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

JavaScript

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;
 }

TypeScript

Written by @manishh12

 function findKthPositive(arr: number[], k: number): number {
   let missingCount = 0;
   let current = 1;

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

   return current;
 }

Python

Written by @manishh12

 class Solution:
     def findKthPositive(self, arr: List[int], k: int) -> int:
         missing_count = 0
         current = 1

         while missing_count < k:
             if current not in arr:
                 missing_count += 1
             if missing_count < k:
                 current += 1

         return current

Java

Written by @manishh12

 class Solution {
     public int findKthPositive(int[] arr, int k) {
         int missingCount = 0;
         int current = 1;

         while (missingCount < k) {
             boolean found = false;
             for (int num : arr) {
                 if (num == current) {
                     found = true;
                     break;
                 }
             }
             if (!found) {
                 missingCount++;
             }
             if (missingCount < k) {
                 current++;
             }
         }

         return current;
     }
 }

C++

Written by @manishh12

 class Solution {
 public:
     int findKthPositive(vector<int>& arr, int k) {
         int missingCount = 0;
         int current = 1;

         while (missingCount < k) {
             if (find(arr.begin(), arr.end(), current) == arr.end()) {
                 missingCount++;
             }
             if (missingCount < k) {
                 current++;
             }
         }

         return current;
     }
 };

Complexity Analysis

• Time Complexity: $O(n \times m)$, where n is the length of the array and m is the kth missing positive number.
• Space Complexity: $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

• LeetCode Problem: LeetCode Problem
• Solution Link: Kth Missing Positive Number Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta

---