1539. Kth Missing Positive Number

use set

T : O(n)

S: O(n)

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)

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
 ）

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

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)

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 
    }
}

new version

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