class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        #TC: O(n)
        #SC: O(1)
        #Still has O(log n) solution
        #need to rethink

        if arr[0] != 1:
            diff = arr[0] - 1
            if diff >= k:
                return k
            else:
                k = k - diff

        j = 1        
        while j < len(arr):
            diff = arr[j] - arr[j-1]
            if diff - 1 >= k:
                return arr[j-1] + k
            else:
                k = k - (diff - 1)
                j += 1
        return arr[-1] + k