Vultr DocsLatest Content

Kth Missing Positive Number

Updated on 16 June, 2025
Kth Missing Positive Number header image

Problem Statement

Given an array arr consisting of positive integers sorted in strictly increasing order, your task is to find the k-th smallest positive integer that is missing from the array. The elements in arr are unique and sorted in ascending order, meaning there are no duplicates.

You are to identify which integer in the natural number sequence—starting from 1 upwards—is the k-th missing number not present in arr.

Examples

Example 1

Input:

arr = [2,3,4,7,11], k = 5

Output:

9

Explanation:

The missing numbers are [1,5,6,8,9,10,...]. The 5th missing number is 9.

Example 2

Input:

arr = [1,2,3,4], k = 2

Output:

6

Explanation:

The missing numbers are [5,6,7,...]. The 2nd missing number is 6.

Constraints

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

Approach and Intuition

To solve this problem, follow these steps:

  1. Initialize a counter curr starting at 1, and use a pointer to traverse arr.

  2. For every number from 1 onwards:

    • If the current number matches the array element, skip it.
    • If it does not match, it is a missing number—decrement k.
    • Stop when k == 0; this number is the answer.

  3. If you reach the end of arr before finding the k-th missing number, continue incrementing curr and counting until k reaches 0.

This method leverages the sorted property of arr to efficiently track the count of missing elements. Given the constraint that arr.length <= 1000, a linear approach works effectively.

Solutions

  • Java
  • Python
java 
class Solution {
    public int kthMissingPositive(int[] sortedArr, int k) {
        int start = 0, end = sortedArr.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (sortedArr[mid] - mid - 1 < k) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start + k;
    }
}

The given Java solution finds the kth missing positive number in a sorted array of integers.

  • Understand that sortedArr is a sorted array of positive integers, and k is the kth missing position you want to find.

  • The method kthMissingPositive uses a binary search approach to efficiently find the position by comparing and adjusting the start and end indices of the array based on the calculated missing elements count.

  • Initialize two pointers, start as 0 and end as the last index of the array. Continue the search as long as start is less than or equal to end.

  • Calculate the middle position, mid, using (start + end) / 2. Check the number of missing elements up to mid index using the formula (sortedArr[mid] - mid - 1).

  • If this count is less than k, move the start index to mid + 1 to search in the right half of the array; otherwise, move the end to mid - 1 to search in the left half.

  • The loop exits when the position is determined, and the kth missing number is given by start + k. This calculation adjusts for the gaps found during the binary search.

This approach ensures optimal efficiency in searching for the kth missing positive number, leveraging the sorted nature of the array with a time complexity of O(log n).

python 
class Solution:
    def kthMissingNumber(self, numbers: List[int], k: int) -> int:
        start, end = 0, len(numbers) - 1
        while start <= end:
            middle = (start + end) // 2
            if numbers[middle] - middle - 1 < k:
                start = middle + 1
            else:
                end = middle - 1
    
        return start + k

The problem "Kth Missing Positive Number" is solved using a Python function kthMissingNumber in a class named Solution. This function takes two parameters: numbers, which is a sorted list of unique positive integers, and k, an integer representing the position of the missing number in the sequence that you need to find.

The approach implements a binary search mechanism to efficiently locate the k-th missing positive number. As the search progresses through the numbers list:

  • Initialize start to 0 and end to the last index of numbers.
  • Use a while loop to continue searching as long as start is less than or equal to end.
  • Determine the middle index using (start + end) // 2.
  • Calculate if the number of positive numbers missing before numbers[middle] is less than k.
  • If so, adjust the start to middle + 1.
  • Otherwise, adjust the end to middle - 1.
  • After exiting the loop, calculate the k-th missing number by adding k to start and return this value.

This method effectively reduces the computational complexity compared to a naive approach, capitalizing on the properties of the sorted list and the nature of binary search. This achieves faster computation, dealing directly with the discrepancies between index positions and the actual numbers in the list.

Comments