Day 11 of LeetCode

🌧️ Rainy

Documenting LeetCode solving.

Q1

33. Search in Rotated Sorted Array

Medium. Binary search

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1

        while l <= r:
            mid = l + ((r - l) // 2)

            if nums[mid] == target:
                return mid

             # First see mid pointer is in left or right portion
            if nums[mid] >= nums[l]: # In left portion
                if target > nums[mid] or target < nums[l]:
                    l = mid + 1
                else:
                    r = mid - 1
            else: # In right portion
                if target < nums[mid] or target > nums[r]:
                    r = mid - 1
                else:
                    l = mid + 1

        return -1

Q2

981. Time Based Key-Value Store

Medium. Binary search

In an interview, it's good to ask if the values are stored in an ascending order by default based on timestamp.

class TimeMap:

    def __init__(self):
        self.store = {} # key : list of [value, timestamp]

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.store:
            self.store[key] = []
        self.store[key].append([value, timestamp])

    def get(self, key: str, timestamp: int) -> str:
        res = ""
        values = self.store.get(key, "")

        # Binary search
        l, r = 0, len(values) - 1
        while l <= r:
            mid = l + ((r - l) // 2)
            if values[mid][1] <= timestamp:
                res = values[mid][0] # Closest value
                l = mid + 1
            else:
                r = mid - 1     

        return res

Q3

4. Median of Two Sorted Arrays

Hard. Binary search

When calculating index j, to avoid index out of bound, we first calculate the number of items in A left portion index_i + 1, then the number of items in B left portion is half - (index_i + 1), then convert it to index by -1, which is half - (i + 1) - 1.

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        total = len(nums1) + len(nums2)
        half = total // 2

        # Binary search on the shorter list
        if len(B) < len(A):
            A, B = B, A

        l, r = 0, len(A) - 1
        while True:
            i = l + ((r - l) // 2)
            j = half - (i + 1) - 1 # index_j = number - (index_i + 1) - 1
                                                        # number
            # Consider out of bound
            # -infinity | 0, 1, 2, 3 .... | infinity
            Aleft = A[i] if i >= 0 else float("-infinity")
            Aright = A[i + 1] if (i + 1) < len(A) else float("infinity")
            Bleft = B[j] if j >= 0 else float("-infinity")
            Bright = B[j + 1] if (j + 1) < len(B) else float("infinity")

            # Partition is correct, remember the = condition
            if Aleft <= Bright and Bleft <= Aright:
                # odd
                if total % 2:
                    return min(Aright, Bright)
                # even
                else:
                    return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
            # Too many items in A left portion,
            # reduce the size of A left portion
            elif Aleft > Bright:
                r = i - 1
            else:
                l = i + 1