1539. Kth Missing Positive Number

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        """  tc O(N) sc O(1)
        1. set target tail value
        2. loop arr, check if curren meet expected val
        3. if no, get diff and compare with k
        4. if k not reaching 0, continue the loop, otherwise return the value when k reaches 0 
        5. if loop finished k still not reaches 0, return k + last item in the arr 
        """
        n = len(arr)
        expect = 1
        for x in arr:
            if x != expect:
                skip = x - expect 
                if k - skip <= 0:
# note, here need to -1  since expect itself count as one missing number
                    return expect + k -1  
                k -= skip
                expect += skip
            expect += 1
        return arr[-1] + k 

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        """  tc O(lgN) sc O(1)
        if I remove intermediate var like expect, diff, runtime will be fast 
        """
        n = len(arr)
        l,r = 0,n
        while l < r:
            m = l + (r-l)//2
            expect = m + 1
            diff = arr[m] - expect 
            if diff < k : # target position should on right 
# l = m + 1 means,there are already mid + 1 non-missed elements on the left, and we still need k missed elements, so l + k <= ans still holds true;
                l = m + 1
            elif diff >= k :
                r = m
        return l + k 
     
#         if l >= n:
#             return arr[-1] + ( n - arr[-1] + k)
#         record = k - (arr[-1]-l) if l > 0 else k
#         return record + arr[-1] if l > 0 else record