1539.Kth_Missing_Positive_Number(Easy).md

1539. Kth Missing Positive Number (Easy)

Date and Time: Dec 21, 2024, 11:00 (EST)

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

Question:

Given an array arr of positive integers sorted in a strictly increasing order, and an integer k.

Return the kth positive integer that is missing from this array.

Example 1:

Input: arr = [2,3,4,7,11], k = 5

Output: 9

Explanation: The missing positive integers are [1,5,6,8,9,10,12,13,...]. The 5th missing positive integer is 9.

Example 2:

Input: arr = [1,2,3,4], k = 2

Output: 6

Explanation: The missing positive integers are [5,6,7,...]. The 2nd missing positive integer is 6.

Constraints:

• 1 <= arr.length <= 1000

• 1 <= arr[i] <= 1000

• 1 <= k <= 1000

• arr[i] < arr[j] for 1 <= i < j <= arr.length

Walk-through:

For index in arr, arr[i] - i - 1 eqauls to the number of missing positive number. And we can run Binary Search on arr with k. Finally, when l passes r, we just return l + k, which is the kth missing positive number.

Binary Search:

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # arr[i] - i - 1 is num of integers missing before arr[i]
        # If num of integers missing < k, search on its right. Otherwise, go to left. We want to find the number that i + k is the kth missing positive number

        # TC: O(log n), n = len(arr), SC: O(1)
        l, r = 0, len(arr)-1
        while l <= r:
            m = (l+r) // 2
            # If number of missing number < k
            if arr[m] - m - 1 < k:
                l = m + 1
            else:
                r = m - 1
        return l + k

Time Complexity: $O(log\ n)$
Space Complexity: $O(1)$

Brute Force:

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # Start from i += 1, if i not in arr, decrement k
        # When k == 0, return i

        # TC: O(n), n = len(arr), SC: O(1)
        i = 1
        while k:
            if i not in arr:
                k -= 1
            if k == 0:
                return i
            i += 1

Time Complexity: $O(n)$
Space Complexity: $O(1)$