Documenting LeetCode solving.
Celebrate 10 days completed 🎉
Q1
Medium. Binary search
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS, COLS = len(matrix), len(matrix[0])
top, bott = 0, ROWS - 1
# First, find the row
while top <= bott:
row = top + ((bott - top) // 2)
if target > matrix[row][-1]:
top = row + 1
elif target < matrix[row][0]:
bott = row - 1
else:
break
# Check if the target exists in a row,
# return false immediately if doesn't
if not top <= bott:
return False
l, r = 0, COLS - 1
# Find the target in the row
while l <= r:
mid = l + ((r - l) // 2)
if target > matrix[row][mid]:
l = mid + 1
elif target < matrix[row][mid]:
r = mid - 1
else:
return True
return False
Q2
Medium. Binary search
Basically same to brute force, but we use binary search to for the k. Because k is in increasing order, e.g. 1, 2, 3, 4, ... .
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
# It's guaranteed koko can finish all piles when k == max(piles)
res = max(piles)
while l <= r:
mid = l + ((r - l) // 2)
hours = 0
for p in piles:
# Round the number up
hours += math.ceil(p / mid)
if hours <= h:
res = min(res, mid)
r = mid - 1
else:
l = mid + 1
return res
Q3
153. Find Minimum in Rotated Sorted Array
Medium. Binary search
class Solution:
def findMin(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
res = nums[0]
while l <= r:
# When we are on the regular increasing order subarray
# For example [3, 4, 5] or [1, 2] of [3, 4, 5, 1, 2]
# The most left is the smallest
if nums[l] < nums[r]:
res = min(res, nums[l])
break
mid = l + ((r - l) // 2)
# Remember to update result after initialize mid pointer
res = min(res, nums[mid])
# Because the array has been rotated, the right part is
# smaller than the left
if nums[mid] >= nums[l]:
l = mid + 1
else:
r = mid - 1
return res