Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 1539. Kth Missing Positive Number

Given a sorted strictly increasing array of positive integers, find the k-th positive integer missing from the sequence. Observe that the count of missing numbers up to index i is arr[i] - (i+1), which lets you locate the correct interval and compute the answer in O(log n) with binary search.

Asked at:

Meta

DESCRIPTION

Input:

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

Output:

Explanation: Missing numbers are 1, 5, 6, 8, 9, 10, 12, 13... The 5th missing number is 9

Constraints:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
arr is sorted in strictly increasing order
All integers in arr are positive

Understanding the Problem

Let's understand what we're being asked to do. We have a sorted array like [2, 3, 4, 7, 11] and need to find the k-th positive integer that's missing from this sequence.

For example, if k=5, let's trace which positive integers are missing: 1 is missing (1st missing), 5 is missing (2nd missing), 6 is missing (3rd missing), 8 is missing (4th missing), 9 is missing (5th missing). So the answer is 9.

Key insight from the problem: At any index i, the value arr[i] tells us how many positive integers exist up to that point. Since indices are 0-based, there are i+1 positions. Therefore, arr[i] - (i+1) gives us the count of missing numbers up to index i.

Important constraint: The array is sorted in strictly increasing order with positive integers only.

Edge cases to consider: What if k is smaller than all missing numbers before the first element? What if k is larger than all missing numbers within the array range?

Brute Force Approach

The straightforward approach is to iterate through the array and count missing numbers at each position using the formula arr[i] - (i+1). Once we find an index where the count of missing numbers is greater than or equal to k, we know the k-th missing number lies in that interval. We can then calculate it directly using the previous index's information. This approach is simple but doesn't fully exploit the sorted property of the missing counts.

Visualization

def find_kth_missing(arr, k):
    """
    Find the k-th positive integer missing from a sorted array.
    Brute force approach: iterate through array and count missing numbers.
    """
    # Track count of missing numbers found so far
    missing_count = 0
    # Current positive integer we're checking
    current = 1
    # Index in the array
    index = 0
    n = len(arr)
    
    # Iterate through positive integers
    while missing_count < k:
        # If we've exhausted the array or current is less than arr[index]
        if index >= n or current < arr[index]:
            # Current number is missing
            missing_count += 1
            # If this is the k-th missing number, return it
            if missing_count == k:
                return current
        else:
            # Current number exists in array, move to next array element
            index += 1
        
        # Move to next positive integer
        current += 1
    
    return -1

Start finding k-th missing positive number

0 / 46

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We potentially scan through all n elements in the array to find the correct interval

Space Complexity: O(1) We only use a constant amount of extra space for loop variables and calculations

Building Intuition

At each index i, we can calculate how many numbers are missing up to that point using the formula arr[i] - (i+1).

For example, at index 2 with value arr[2]=4, we know there should be 3 numbers (indices 0,1,2), but the value is 4, meaning 4-3=1 number is missing before this position.

This monotonically increasing count of missing numbers means we can locate which interval contains the k-th missing number.

Since the count of missing numbers increases as we move right through the array, we can use this property to eliminate half the search space at each step.

If the missing count at the middle is less than k, the k-th missing number must be to the right. If it's greater than or equal to k, it must be to the left or at that position.

This transforms a linear scan into a logarithmic search, reducing time from O(n) to O(log n).

Think of the array as creating 'gaps' between consecutive integers. Each gap represents missing numbers.

For [2, 3, 4, 7, 11]: gap before 2 has 1 missing (1), gap between 4 and 7 has 2 missing (5, 6), gap between 7 and 11 has 3 missing (8, 9, 10).

The cumulative count of missing numbers up to each position is sorted, which is exactly what we need for efficient searching. We're essentially searching for the right gap that contains our k-th missing number.

Common Mistakes

Off-by-one errors in the missing count formula: remember it's arr[i] - (i+1), not arr[i] - i, because indices are 0-based but positive integers start at 1

Incorrect final calculation: after binary search, the k-th missing number is typically left + k where left is the final left pointer position, but this requires careful derivation

Not handling edge cases: when k is less than arr[0] - 1 (all missing numbers are before the array), the answer is simply k

Forgetting that the array is strictly increasing: this guarantees no duplicates and ensures the missing count is monotonically increasing

Confusing the search target: we're searching for the interval where missing count transitions from < k to >= k, not searching for k itself in the array

Optimal Solution

The optimal approach uses binary search on the array to find the interval containing the k-th missing number. At each step, calculate the missing count at the middle index using arr[mid] - (mid+1). If this count is less than k, the k-th missing number must be to the right, so search the right half. Otherwise, search the left half. Once we find the correct interval (or determine it's before/after the array), we calculate the k-th missing number using the formula based on the boundary index and remaining missing count.

Visualization

def find_kth_missing(arr, k):
    """
    Find the k-th missing positive integer from a sorted array.
    Uses binary search on missing count: arr[i] - (i+1).
    """
    # Binary search initialization
    left = 0
    right = len(arr) - 1
    
    # Binary search to find the interval containing k-th missing
    while left <= right:
        mid = (left + right) // 2
        # Calculate missing count up to index mid
        missing_count = arr[mid] - (mid + 1)
        
        # If missing count < k, search right half
        if missing_count < k:
            left = mid + 1
        else:
            # Search left half
            right = mid - 1
    
    # Calculate k-th missing number
    # If left == 0, k-th missing is before array: k
    # Otherwise: arr[right] + (k - missing_at_right)
    if left == 0:
        return k
    
    missing_at_right = arr[right] - (right + 1)
    return arr[right] + (k - missing_at_right)

Start finding k-th missing positive number

0 / 16

Test Your Knowledge

Complexity Analysis

Time Complexity: O(log n) Binary search eliminates half the search space in each iteration, resulting in logarithmic time complexity

Space Complexity: O(1) We only need two pointers (left and right) and a few variables for calculations, regardless of array size

What We've Learned

Missing element formula: In a sorted array starting from 1, the count of missing numbers up to index i is `arr[i] - (i + 1)`. This mathematical insight transforms a counting problem into a searchable property, enabling binary search on an implicit monotonic function.
Binary search on derived properties: You don't need to binary search on array values directly - search on computed properties like "missing count". The key is recognizing that `missing_count(i)` is monotonically increasing, making it binary-searchable even though we're not searching for a target value.
Interval-based answer computation: Once binary search identifies the interval where the k-th missing number falls (between indices), calculate it as `left + k` or `arr[right] - (missing_at_right - k)`. The missing number exists in the gap, not in the array itself.
Off-by-one in array indexing: A critical mistake is forgetting that `arr[i]` should contain value `i+1` if nothing is missing (not `i`). Always use `arr[i] - (i + 1)` for missing count, and remember the answer when k exceeds all missing numbers is `arr[n-1] + (k - missing_at_end)`.
O(log n) vs O(n) decision point: When you need the k-th element of something not explicitly stored but derivable from a sorted structure, consider binary search. The linear scan `O(n)` solution works but misses that "missing count" increases predictably, making logarithmic search possible.
Gap analysis in sequences: This pattern applies to database pagination (finding the n-th available slot), memory allocation (locating free blocks), scheduling (finding available time slots), and version control (identifying missing commits in a sequence) - anywhere you track what's present to infer what's absent.

Test Your Understanding

Why is array the right data structure for this problem?

array provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2025

Meta

Mid-level

Mid September, 2025

Meta

Staff

Early September, 2025

Meta

Senior

Get Premium to View All 10+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 1539. Kth Missing Positive Number

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact