1539. Kth Missing Positive Number (Array, Binary Search)

링크 - https://leetcode.com/problems/kth-missing-positive-number/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

1) Linear Search

직관적인 풀이법이다. 왼쪽부터 arr을 for문으로 돌리면서 나온값들을 비교해서 missing positive integer들을 추적하는 방법이다. 

class Solution:
    def findKthPositive(self, arr: List[int], k: int) -> int:
        cur_int = 0
        for num in arr:
            diff = num - cur_int
            if diff > 1:
                if k < diff:
                    return cur_int + k
                else:
                    k -= (diff - 1)
            cur_int = num

        return cur_int + k

Time Complexity: O(n) 최악의 경우 arr을 다 돌아야 하기 때문에 arr의 원소의 개수인 n만큼 시간이 소요된다.

Space Complexity: O(1) 상수 변수만 저장한다.

2) Binary Search (O(logn) time)

우리는 이미 input이 strictly sorted임을 알고있다. 이를 활용하여 Binary Search를 사용하면 Time complexity를 더 줄일 수 있다. 

예를 들어 [2,3,4,7,11]이라는 배열을 보자 우리는 각 원소의 인덱스와 값을 가지고 얼마만큼의 positive integers가 missing인지 알 수 있다. 다시 말해, 첫번째 원소 2의 이전에는 1이라는 positive integer가 빠져있는데 이를 구하는 방법은 2(현재값) - 1(index+1)이다. 마찬가지로 3도 1개가 빠져있는데 이는 3 - 2로 알수있다. 4도 4-3으로 알 수 있다. 7원소 앞에는 1,5,6 3개가 빠져있는데 이는 7 - 4 = 3으로 알 수 있다. 11원소도 11 - 5 = 6으로 11앞에는 6개의 양의정수가 빠져있음을 알 수 있다. 

이를 Binary Search와 접목해보자

1. left, right를 0, n-1로 초기화 한다.

2. mid = (left+right)/2로 설정하고 arr[mid]와 mid값을 사용하여 얼마나 양의정수가 missing인지 알아낸다.

3. 만약 arr[mid] - (mid + 1)이 k보다 작다면, 우리가 찾고자 하는 수는 mid보다 오른쪽에 있다는 뜻이다. 따라서 left=mid+1로 설정한다.

4. 만약 k보다 크거나 같다면, 우리가 찾고자 하는 수는 mid보다 왼쪽에 있다는 뜻이다. 따라서 right = mid-1로 설정한다.

5. 루프가 끝나면, left = right+1을 가지게 된다. 그리고 우리가 찾는 kth-missing positive integer은 arr[right]과 arr[left]에 있게된다. arr[right]이전의 missing 수는 arr[right] - (right+1)이므로 우리가 찾고자 하는 수는 arr[right] + k - (arr[right] - (right+1)) = k + right + 1 = k + left이다.

Code

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

        return left + k

Complexity

Time Complexity: O(logn)

Space Complexity: O(1)