Kth Missing Positive Number

LeetCode 1646 | Difficulty: Easy

Easy

Problem Description

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the k^th *positive integer that is missing from this array.*

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 5^th 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 2^nd 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`

Follow up:

Could you solve this problem in less than O(n) complexity?

Topics: Array, Binary Search

---

Approach

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

---

Solutions

Solution 1: C# (Best: 146 ms)

Metric	Value
Runtime	146 ms
Memory	36.7 MB
Date	2022-01-12

Solution

public class Solution {
    public int FindKthPositive(int[] arr, int k) {
        int counter = k;
        int i = 0;
        int n = arr.Length;
        
        int num = 1;
        List<int> missing = new List<int>();
        while(i < n)
        {
            if(arr[i] == num) {
                i++;
                num++;
                continue;
            }
            else
            {
                for(int j=num;j<arr[i];j++)
                {
                    missing.Add(j);
                    counter--;
                    if(counter == 0) return j;
                }
                num = arr[i]+1;
                i++;
            }
        }
        
        return (counter == 0) ? missing[missing.Count-1]
                              : arr[arr.Length-1]+counter;
    }
}

---

Complexity Analysis

Approach	Time	Space
Binary Search	$O(log n)$	$O(1)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Precisely define what the left and right boundaries represent, and the loop invariant.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Keep track of how many positive numbers are missing as you scan the array.