🌧️ 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