Kth Positive Integer Missing from an Increasing Array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Other
### Problem
Given the strictly increasing positive array arr,return the kth positive integer absent from it. Missing values may occur before,between,or after the array entries.
```cpp
class Solution {
public:
int findKthPositive(vector<int>& arr, int k);
};
```
### Examples
**Example 1:**
```text
Input: arr = [1,4,6], k = 3
Output: 5
Explanation: The missing positive values begin2,3,5,7; the third is5.
```
**Example 2:**
```text
Input: arr = [2], k = 1
Output: 1
Explanation: The first missing value occurs before the first array entry.
```
### Constraints
- arr has length 1 to 1000 and contains strictly increasing positive integers.
- `1 <= arr[i] <= 1000` and `1 <= k <= 1000`.
### Contract considerations
Account for missing values before the first entry, between entries, and beyond the last entry.
```hint Read the boundary condition
Positive counting starts at one. Missing values may lie before the first entry, between entries, or beyond the last entry.
```
### Boundary reminders
Account for missing values before the first entry, between entries, and beyond the last entry.
### Optional extensions
Can you solve the problem in less than O(n) time?
Overview: Kth Positive Integer Missing from an Increasing Array. Given the strictly increasing positive array arr,return the kth positive integer absent from it.
