1539. Kth Missing Positive Number

https://leetcode.com/problems/kth-missing-positive-number/

Python

Linear Search

• Time: O(N)
• Space: O(1)

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        low, high = arr[0], arr[-1]

        # The lowest larger than k, won't need to search missing within arr
        if low > k:
            return k

        k = k - low + 1
        i = 0
        last_missed = None

        for num in range(low, high+1):
            if k == 0:
                return last_missed

            # Num is not the missing
            if num == arr[i]:
                i += 1
                continue

            # Missing found, num not in arr
            last_missed = num
            k -= 1

        # There are remains k after search missing within arr, ans is the highest arr num + k
        return high + k

Binary Search

Leetcode offical solution

Considering

1. 觀察arr value與index的關係

以 [2,3,4,7.11]為例

numValue	numIndex	missingCount	relation
2	0	1	2 - (0 + 1)
3	1	1	3 - (2 + 1)
4	2	1	4 - (2 + 1)
7	3	3	7 - (3 + 1)
11	4	6	11 - (4 + 1)

2. 歸納出規則

$$missingCount = numValue - (numIndex + 1)$$

3. 二分搜尋找右界，第一個不小於k的位置，也就是第一個減k為零的位置

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        left, right = 0, len(arr) - 1
        while left <= right:
            pivot = (left + right) // 2
            if arr[pivot] - pivot - 1 < k:
                left = pivot + 1
            else:
                right = pivot - 1

        # At the end of the loop, left = right + 1,
        # and the kth missing is in-between arr[right] and arr[left].
        # The number of integers missing before arr[right] is
        # arr[right] - right - 1 -->
        # the number to return is
        # arr[right] + k - (arr[right] - right - 1) = k + left
        return left + k

Optim Linear Search

Skip search smaller than low bound or higher than the up bound

• Time: O(N)
• Space: O(1)

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        low, high = arr[0], arr[-1]

        # The lowest larger than k, won't need to search missing within arr
        if low > k:
            return k

        k = k - low + 1

        # kth missing number btw low and high
        i = 0
        for num in range(low, high+1):
            if num == arr[i]:
                i += 1
                continue
            k -= 1
            if k == 0:
                return num

        # kth missing number larger than high
        return high + k