Solutions to LeetCode 378 Kth Smallest Element in a Sorted Matrix and LeetCode 875 Koko Eating Bananas.
LeetCode 378
Kth Smallest Element in a Sorted Matrix (Medium). [link]
We want to find value m such that the number of values smaller or equal to the m does not exceed k. upper_bound is used to count the number of values <= m for each binary split.
class Solution(object):
def kthSmallest(self, matrix, k):
"""
:type matrix: List[List[int]]
:type k: int
:rtype: int
"""
l = matrix[0][0] # the smallest value
r = matrix[-1][-1] # the largest value
while l < r:
m = l + (r - l) // 2
total = 0
for row in matrix:
total += self.upper_bound(row, m)
if total >= k:
r = m
else:
l = m + 1
return l
def upper_bound(self, array, val):
l = 0
r = len(array)
while l < r:
m = l + (r - l) // 2
if array[m] > val:
r = m
else:
l = m + 1
return l
LeetCode 875
Koko Eating Bananas (Medium) [link]
We want to find the minimum speed K such that Koko can eat all bananas within H hours, so this can be solved by binary search. According to the problem statement, Koko will take (p-1) // k + 1 hours to finish one pile.
The time complexity to calculate the total hours is O(N). The total time complexity is O(N log W), where N is the number of piles, W is the max number of bananas in one pile. The space complexity is O(1).
class Solution(object):
def minEatingSpeed(self, piles, h):
"""
:type piles: List[int]
:type h: int
:rtype: int
"""
l = 1
r = max(piles) + 1
while l < r:
m = r + (l - r) // 2
count = 0
for p in piles:
count += (p - 1) // m + 1
if count <= h:
r = m
else:
l = m + 1
return l
