1539. Kth Missing Positive Number

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

O(N)과 O(lgN)이 존재하므로 흥미롭다고 생각되는 문제

Easy

54918Add to ListShare

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

Find 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

Keep track of how many positive numbers are missing as you scan the array.

Solution

Approach 1: Brute Force, \mathcal{O}(N) time

The first idea is to solve the problem in a linear time by parsing all array elements. It's easy to say how many positive numbers are missing between two array elements: arr[i + 1] - arr[i] - 1, and we could use it to solve the problem.

Figure 1. Approach 1. Iterate over the array and compute the number of missing numbers in-between the elements.

Algorithm

Check if the kth missing number is less than the first element of the array. If it's the case, return k.
Decrease k by the number of positive integers which are missing before the array starts: k -= arr[0] - 1.
Iterate over the array elements:
- At each step, compute the number of missing positive integers in-between i + 1th and ith elements: currMissing = arr[i + 1] - arr[i] - 1.
- Compare k to the currMissing. If k <= currMissing then the number to return is in-between arr[i + 1] and arr[i], and you could return it: arr[i] + k.
- Otherwise, decrease k by currMissing and proceed further.
We're here because the element to return is greater than the last element of the array. Return it: arr[n - 1] + k.

Implementation

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        # if the kth missing is less than arr[0]
        if k <= arr[0] - 1:
            return k
        k -= arr[0] - 1

        # search kth missing between the array numbers
        for i in range(len(arr) - 1):
            # missing between arr[i] and arr[i + 1]
            curr_missing = arr[i + 1] - arr[i] - 1
            # if the kth missing is between
            # arr[i] and arr[i + 1] -> return it
            if k <= curr_missing:
                return arr[i] + k
            # otherwise, proceed further
            k -= curr_missing

        # if the missing number if greater than arr[-1]
        return arr[-1] + k

Complexity Analysis

Time complexity: \mathcal{O}(N) because in the worst case, we have to parse all array elements.
Space complexity: \mathcal{O}(1), we don't allocate any additional data structures.

Approach 2: Binary Search, \mathcal{O}(\log N) time

Approach 1 doesn't profit from the fact that the input array is sorted. And the sorted input should ring the bell: "let's try to solve it in a logarithmic time using binary search".

We need a way to check on how many positive integers are missing before the given array element to use binary search. To do that, let's compare the input array [2, 3, 4, 7, 11] with an array with no missing integers: [1, 2, 3, 4, 5]. The number of missing integers is a simple difference between the corresponding elements of these two arrays:

Before 2, there is 2 - 1 = 1 missing integer.
Before 3, there is 3 - 2 = 1 missing integer.
Before 4, there is 4 - 3 = 1 missing integer.
Before 7, there are 7 - 4 = 3 missing integers.
Before 11, there are 11 - 5 = 6 missing integers.

The number of positive integers which are missing before the arr[idx] is equal to arr[idx] - idx - 1.

Figure 2. The number of missing positive integers before the index idx.

Now we have everything to proceed with the classical binary search algorithm:

Choose the pivot index in the middle of the array.
If the number of positive integers which are missing before arr[pivot] is less than k - continue to search on the right side of the array.
Otherwise, continue to search on the left side.

Algorithm

Initialize search boundaries: left = 0, right = arr.length - 1.
While left <= right:
- Choose the pivot index in the middle: pivot = left + (right - left) / 2. Note that in Java we couldn't use straightforward pivot = (left + right) / 2 to avoid the possible overflow. In Python, the integers are not limited, and we're fine to do that.
- If the number of positive integers which are missing before is less than k arr[pivot] - pivot - 1 < k - continue to search on the right side of the array: left = pivot + 1.
- Otherwise, continue to search on the left: right = pivot - 1.
At the end of the loop, left = right + 1, and the kth missing number is in-between arr[right] and arr[left]. The number of integers missing before arr[right] is arr[right] - right - 1. Hence, the number to return is arr[right] + k - (arr[right] - right - 1) = k + left.

Implementation

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 number of positive integers
            # which are missing before arr[pivot]
            # is less than k -->
            # continue to search on the right.
            if arr[pivot] - pivot - 1 < k:
                left = pivot + 1
            # Otherwise, go left.
            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

Complexity Analysis

Time complexity: \mathcal{O}(\log N), where N is a number of elements in the input array.

Let's compute time complexity of the binary search with the help of master theorem T(N) = aT\left(\frac{N}{b}\right) + \Theta(N^d). The equation represents dividing the problem up into a subproblems of size \frac{N}{b} in \Theta(N^d) time. Here, at each step, there is only one subproblem a = 1, its size is a half of the initial problem b = 2, and all this happens in a constant time d = 0. That means that \log_b{a} = d and hence we're dealing with case 2 that results in \mathcal{O}(N^{\log_b{a}} \log^{d + 1} N) = \mathcal{O}(\log N) time complexity.
Space complexity: \mathcal{O}(1), we don't allocate any additional data structures.