leetcode 1060, 1901

1060. Missing Element in Sorted Array

n = [1, 2, 4],  k = 3일 때를 생각해보면 좋다.

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        
        missing = lambda idx: nums[idx] - nums[0] - idx
        
        n = len(nums)
        # for the case [1, 2, 4]
        # 4 + 3 - 1 = 6
        if k > missing(n-1):
            return nums[-1] + k - missing(n-1)
        
        idx = 1
        
        while missing(idx) < k:
            idx += 1
        
        return nums[idx-1] + k - missing(idx-1)

binary serach로 탐색이 가능한지는 고민을 많이했어야했는데, condition을 어떻게 할 지 고민만 하면 된다.

class Solution:
    def missingElement(self, nums: List[int], k: int) -> int:
        
        n = len(nums)
        missing = lambda idx: nums[idx] - nums[0] - idx
        
        l, r = 0, n - 1
        
        if k > missing(n-1):
            return nums[-1] + k - missing(n-1)
        
        while l < r:
            # how to check condition 
            m = l + (r - l) // 2
            
            # check condition 
            if missing(m) >= k:
                r = m
                
            else:
                l = m + 1
        return nums[l - 1] + k - missing(l - 1)

1901. Find a Peak Element II

음 아직도 condition을 설계하는 부분에서 헷갈린다.

class Solution:
    def findPeakGrid(self, mat: List[List[int]]) -> List[int]:
        m, n = len(mat), len(mat[0])      
        l, r = 0, m-1
        while l < r:
            mid = l + (r - l) // 2
            mmax, lmax, hmax = max(mat[mid]), max(mat[mid-1]), max(mat[mid+1])
            if mmax > max(lmax, hmax):
                return [mid, mat[mid].index(mmax)]
            elif lmax > max(mmax, hmax):
                r = mid
            else:
                l = mid + 1
        return [l, mat[l].index(max(mat[l]))]