# Kth Missing Positive Number
**Difficulty:** EASY
[External](https://leetcode.com/problems/kth-missing-positive-number)
Canonical: https://scaleengineer.com/dsa/problems/kth-missing-positive-number
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Arista Networks](https://scaleengineer.com/companies/arista-networks)
---
## 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._

**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`

**Follow up:**

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

# Approaches
## Brute Force Simulation using a Set
This approach involves a straightforward simulation. We first store all numbers from the input array into a `HashSet` for quick O(1) average time lookups. Then, we iterate through positive integers starting from 1, and for each integer, we check if it's in our set. If it's not, we've found a missing number and we decrement `k`. The process stops when `k` reaches zero, and the current integer is our answer.
**Time:** O(N + M), where N is the length of `arr` and M is the value of the k-th missing number. Building the set takes O(N). The loop runs M times. In the worst case, M can be `arr.length + k`, so the complexity is O(N + k). · **Space:** O(N), where N is the number of elements in the array `arr`. This space is used to store the elements in a `HashSet`.
**Pros:** Simple to understand and implement.; Correctly solves the problem.
**Cons:** Inefficient in terms of both time and space compared to other solutions.; The time complexity depends on the value of the result, which can be large.
### Explanation
The brute-force method systematically checks every positive integer to see if it is missing from the given array. To do this efficiently, we first convert the `arr` into a `HashSet`. This data structure provides average constant-time complexity for checking the existence of an element.

We then iterate upwards from the number 1. In each step, we see if the current number is in the set. If it is, we continue to the next number. If it's not, we've found a missing number. We decrement our counter `k`. When `k` hits zero, we have found our target, the k-th missing positive integer.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int findKthPositive(int[] arr, int k) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : arr) {
            numSet.add(num);
        }

        int num = 1;
        while (k > 0) {
            if (!numSet.contains(num)) {
                k--;
            }
            if (k == 0) {
                return num;
            }
            num++;
        }
        
        return -1; // Should not be reached given the constraints
    }
}
```
### Algorithm
- Create a `HashSet` and populate it with all the elements from the input array `arr`.
- Initialize a counter for the current positive integer, `num = 1`, and a counter for missing numbers found, `missingCount = 0`.
- Start a loop that continues as long as `k` is greater than 0.
- Inside the loop, check if the current `num` is present in the `HashSet`.
- If `num` is **not** in the set, it's a missing number. Decrement `k`.
- If `k` becomes 0, then the current `num` is the k-th missing number, so we return it.
- Increment `num` in every iteration to check the next positive integer.

## Single Pass Linear Scan
A more efficient approach is to perform a single linear scan through the array. Since the array is sorted, we can keep track of `k` and adjust it as we encounter numbers. The core idea is that if we see a number `num` from the array that is less than or equal to our current target `k`, it 'uses up' a spot, so we need to find the `(k+1)`-th missing number instead. This simple adjustment allows us to find the answer in one pass.
**Time:** O(N), where N is the length of the array `arr`. In the worst case, we iterate through the entire array once. · **Space:** O(1), as we only use a few variables to keep track of our state, regardless of the input size.
**Pros:** Very efficient in terms of space, using only O(1) extra space.; Simple and elegant logic.; Time complexity is linear, which is a significant improvement over the brute-force method.
**Cons:** Not as efficient as the binary search approach for very large arrays, as it has a linear time complexity.
### Explanation
This approach leverages the sorted nature of the array to avoid using extra space. We can think of the problem as finding the value `k` in a sequence where some numbers (those in `arr`) are skipped.

We initialize our answer to be `k`. We then iterate through the array `arr`. For each element `arr[i]`, if `arr[i]` is less than or equal to our current answer `k`, it means the number `arr[i]` is present and is taking up a spot at or before our target. This implies that our target missing number must be shifted one position to the right. Therefore, we increment `k`.

Once we encounter an `arr[i]` that is greater than `k`, we know that the k-th missing number has already been determined, as no subsequent numbers in the array can affect it. The final value of `k` after the iteration is the result.

```java
class Solution {
    public int findKthPositive(int[] arr, int k) {
        for (int num : arr) {
            if (num <= k) {
                k++;
            } else {
                break;
            }
        }
        return k;
    }
}
```
### Algorithm
- Iterate through each number `num` in the sorted input array `arr`.
- For each `num`, check if it is less than or equal to the current value of `k`.
- If `num <= k`, it means this number from the array occupies a spot that would have otherwise been one of the first `k` missing integers. To compensate for this, we must look for a number that is one position further. So, we increment `k`.
- If `num > k`, it means the k-th missing number must have come before `num`, and we have already passed it. We can stop iterating.
- After the loop finishes (or breaks), the final value of `k` is the k-th missing positive integer.

## Binary Search
The most optimal solution uses binary search to achieve logarithmic time complexity, which directly addresses the follow-up question. The key observation is that the number of missing integers up to any given index `i` (`arr[i] - (i + 1)`) is a monotonically increasing function. This allows us to efficiently search for the point in the array where the count of missing numbers surpasses `k`.
**Time:** O(log N), where N is the length of the array `arr`. This is due to the binary search algorithm, which halves the search space in each iteration. · **Space:** O(1), as the binary search is performed in-place and uses only a few variables for pointers.
**Pros:** Extremely efficient with O(log N) time complexity.; Optimal solution for the problem.; Uses O(1) space.
**Cons:** The logic can be less intuitive to grasp compared to a straightforward linear scan.
### Explanation
This approach is based on a key insight: for any element `arr[i]`, we know that there should be `i + 1` positive integers up to that position if the array were dense (i.e., `[1, 2, 3, ...]`). Therefore, the number of positive integers missing before `arr[i]` is exactly `arr[i] - (i + 1)`.

Since `arr` is strictly increasing, the function `f(i) = arr[i] - (i + 1)` is non-decreasing. This property is perfect for binary search. Our goal is to find the index `i` such that the k-th missing number lies between `arr[i-1]` and `arr[i]`.

We perform a binary search on the array's indices. For each `mid` index, we check if `arr[mid] - (mid + 1)` is less than `k`. 
- If it is, we know the k-th missing number must be further to the right, so we discard the left half by setting `left = mid + 1`.
- Otherwise, the k-th missing number is to the left of or at `mid`'s position, so we set `right = mid - 1`.

When the search concludes, `left` will point to the index where the k-th missing number would be inserted. The final answer is `k + left`, because there are `left` numbers from `arr` that are smaller than the result, and we are looking for the k-th missing number.

```java
class Solution {
    public int findKthPositive(int[] arr, int k) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // Number of missing integers before arr[mid]
            int missingCount = arr[mid] - (mid + 1);

            if (missingCount < k) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // At the end of the loop, `left` is the number of elements
        // in `arr` that are smaller than the k-th missing number.
        // The k-th missing number is k + left.
        return left + k;
    }
}
```
### Algorithm
- The number of missing positive integers before `arr[i]` is `arr[i] - (i + 1)`.
- This count of missing numbers is a non-decreasing function of the index `i`, which allows us to use binary search.
- We binary search on the indices of `arr` from `left = 0` to `right = arr.length - 1`.
- In each step, we calculate the `mid` index and find the number of missing integers up to that point: `missing = arr[mid] - (mid + 1)`.
- If `missing < k`, it means the k-th missing number is in the right part of the array. We update `left = mid + 1`.
- If `missing >= k`, the k-th missing number is in the left part (or at `mid`), so we update `right = mid - 1`.
- The loop terminates when `left > right`. The value of `left` at the end of the loop represents the number of elements from `arr` that are smaller than our answer.
- The k-th missing number is the k-th positive integer after skipping these `left` numbers. Thus, the answer is `k + left`.

# Solutions
### Java

```java
class Solution {
public
  int findKthPositive(int[] arr, int k) {
    if (arr[0] > k) {
      return k;
    }
    int left = 0, right = arr.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr[mid] - mid - 1 >= k) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int findKthPositive(vector<int> &arr, int k) {
    if (arr[0] > k)
      return k;
    int left = 0, right = arr.size();
    while (left < right) {
      int mid = (left + right) >> 1;
      if (arr[mid] - mid - 1 >= k)
        right = mid;
      else
        left = mid + 1;
    }
    return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1);
  }
};

```

### Python

```python
class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int: if arr[0] > k: return k left, right = 0, len(arr) while left < right: mid = (left + right) >> 1 if arr[mid] - mid - 1 >= k: right = mid else: left = mid + 1 return arr[left - 1] + k - (arr[left - 1] - (left - 1) - 1)

```