Kth Missing Positive Number - Practice Coding Problems

Kth Missing Positive Number - Problem

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.

The missing positive integers are those that should exist in a sequence starting from 1 but are not present in the given array.

Input & Output

Example 1 — Basic Case

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

› Output: 9

💡 Note: Missing positive integers are [1,5,6,8,9,10,11,...]. The 5th missing positive integer is 9.

Example 2 — Small Array

$ Input: arr = [1,2,3,4], k = 2

› Output: 6

💡 Note: Missing positive integers are [5,6,7,8,...]. The 2nd missing positive integer is 6.

Example 3 — Missing from Start

$ Input: arr = [2], k = 1

› Output: 1

💡 Note: The only missing positive integer before 2 is 1, which is the 1st missing.

Constraints

1 ≤ arr.length ≤ 1000
1 ≤ arr[i] ≤ 1000
1 ≤ k ≤ 1000
arr[i] < arr[i + 1]

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Sorted array [2,3,4,7,11] with k=5

Find Missing

Identify missing positive integers: 1,5,6,8,9...

Get Kth

Return the 5th missing number which is 9

Key Takeaway

🎯 Key Insight: Calculate missing count at each position using the formula missing = arr[i] - (i + 1) to efficiently find where the kth missing number falls

Asked in

F Facebook 35 a Amazon 28 G Google 22

The key insight is that at any position i in the sorted array, we can calculate how many positive integers are missing before arr[i] using the formula: missing = arr[i] - (i + 1). The best approach is binary search which finds the position where the kth missing number falls in O(log n) time. Time: O(log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Missing Count	O(log n)	O(1)	Binary search to find the exact position where kth missing number falls
Brute Force Linear Search	O(n × k)	O(1)	Check each positive integer starting from 1 until we find k missing ones
Mathematical Formula	O(n)	O(1)	Calculate missing count at each position using array values

Binary Search on Missing Count — Algorithm Steps

Set left=0, right=n-1 for binary search
For each mid, calculate missing numbers before arr[mid]
Adjust search space based on whether missing count >= k
Calculate final answer using the found position

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set left=0, right=n-1

Calculate Mid

Find missing count at mid position

Adjust Bounds

Move left or right based on comparison

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* arr, int arrSize, int k) {
    int left = 0, right = arrSize - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int missing = arr[mid] - mid - 1;
        
        if (missing < k) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // left is the insertion point
    return left + k;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[1000];
    int arrSize = 0;
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0) {
            arr[arrSize++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(arr, arrSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log n)

Binary search reduces search space by half each time

⚡ Linearithmic

Space Complexity

O(1)

Only using variables for binary search bounds

✓ Linear Space

98.5K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Missing Count — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler