# 1539. Kth Missing Positive Number

## use set

T : O(n)

S: O(n)

```java
class Solution {
    public int findKthPositive(int[] arr, int k) {
        Set<Integer> set = new HashSet<>();
        for (int num : arr) {
            set.add(num);
        }
        int missing = 0;
        int max = arr[arr.length - 1];
        for (int i = 1; i <= max; i++) {
            if (!set.contains(i)) {
                missing++;
            }
            if (missing == k) {
                return i;
            }
        }
        return max + (k - missing);
    }
}
```

## more logical thinking

T : O(n)

S: O(1)

```java
class Solution {
    public int findKthPositive(int[] arr, int k) {
        for (int num : arr) {
            if (num <= k) { // this condition will increasing, k is growing
                k++;
            } else {
                break;
            }
        }
        return k;
    }
}
/*
arr is strictly increasing order,
if every arr[i] > k
the ans is k

k = 5, arr = [6, 8, 9, 10]
ans is 5

so if there are arr[i] <= k
k sould ++

*/
```

## another one - this is important

因為 no missing 時,  arr 的值 , 和 idx 差1

```
if no missing: arr[i] = i + 1
=> 
arr[i] - i - 1 = 0, so we want k missing value
 0 1  2  3
[1,2, 3, 7], k = 3
 0 0  0  7 - 3 - 1 = 3  => i + k = 3 + 3 = 6
 也就是在 idx 3 時 有 3個 missing value 要補上 (4,5,6)
 
 0 1 2 3
 [2,3,4,7] k = 3
 
 idx = 0, 2 - 0 - 1 = 1
 idx = 1, 3 - 1 - 1 = 1
 idx = 2, 4 - 2 - 1 = 1
 idx = 3, 7 - 3 - 1 = 3, >= 3
 ans is: idx + k  => 3+3 = 6
 因為有差值時, idx 會是落後的一方, 所以最後 idx 加上 k , 就是答案

  
  0 1 2 3
 [2,3,4,7] k = 5
 
 idx = 0, 2 - 0 - 1 = 1
 idx = 1, 3 - 1 - 1 = 1
 idx = 2, 4 - 2 - 1 = 1
 idx = 3, 7 - 3 - 1 = 3, 還是沒達到 >= 5
 
 so the ans is 5 + len = 5+4 = 9 
 （if cant find in array, the ans just like no missing value in array
 ans = len + k
 ）

```

```java
// 代表前面 arr[i] - i -1 有差值, 有 missing value
// 所以當 missing value 超過等於 k 時,  
if (arr[i] - i - 1 >= k) {
    return k + i;
}
```

```java
class Solution {
    public int findKthPositive(int[] arr, int k) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            if (arr[i] - i - 1 >= k) {
                return i+k;
            }
        }
        return k+len;
    }
}

/*
arr: [1~n]
index: [0~n-1]

if no missing

arr[i] = i + 1

so if (arr[i] - i - 1 >= k) {
    return k+i;
}


都沒有 missing: k+arr len
*/
```

## binary search

```
ex: 
[1,2,3,4], k = 2

left = 0
right = 3 (if we use len-1)
mid = 0 +1 = 1
arr[1] - 1 - 1 = 1

left = mid+1 = 2
right = 3
mid= 2
arr[2] - 2 -1 = 0

 left = mid +1  = 3
 
  break: 
  left = 3 
  3 + k = 5 => wrong!
 
ex: 
[1,2,3,4], k = 2

left = 0
right = 4 (len = 4)
mid = 0 + 2 = 2
arr[2] - 2 - 1 = 0
left = 2 + 1 = 3

left = 3
right = 4
mid = 3 + 0 = 3
arr[3] - 3 - 1 = 0
left = 3+1 = 4
break;

ans: left + k = 4 + 2 = 6 => yes!

```

T: O(logn)

S: O(1)

```java
class Solution {
    public int findKthPositive(int[] arr, int k) {
        int left = 0;
        //why? for no missing number (ans is len+k, so right = arr.leng
        int right = arr.length;
        
        while (left < right) {
            int mid = left + (right - left)/2;
            int missing = arr[mid] - mid - 1;
            if (missing >= k) { // means too many missing number, 縮小範圍
                right = mid;
            } else {
                left = mid+1;
            }
        }
        return left + k; // if 都沒有 missing, 就會變成 len+k 
    }
}
```

![](/files/MDB2qv3uhNYVZs6oeJTf)

## new version

````java
```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;
            int missing = arr[mid] - mid - 1;
            if (missing >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left + k;
    }
}

/*
[2,3,4,7,11]. 0 + (4 - 0)/2 = 2 , arr[2] = 4
4-2-1 = 1 (missing 1 !)

missing > k right = mid -1
missing = k right = mid -1
missing < k left = mid + 1


left 3, right 4
mid = 3, arr[3] = 7
7 - 3 - 1 = 3

left 4 right 4
mid = 4, arr[4] = 11
11 - 4 - 1 = 6 (missing)
right = mid -1 = 3 -> left >= right end while

left + k = 4 + 5 = 9

[1,5,6,8,9,10,12,13...]


exaple: arr = [2,3,4,7,11] if k = 1
[2,3,4,7,11]. mid = 0 + (4 - 0)/2 = 2 , arr[2] = 4
4-2-1 = 1 (missing 1 !)
missing = k. right = mid -1 = 2 - 1 = 1   

left 0, right 1
mid = left + (right - left)/2 = 0 + 1/2 = 0
missing = arr[0] - 0 - 1 = 2 - 0 - 1 = 1
missing = k, right = mid - 1 = 0 -1 = -1 end while

return left + k = 0 + 1 = 1
*/
```ja
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/binary-search/1539.-kth-missing-positive-number.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.