Monotone Function, O(NlogN)¶
Split Input Array¶
1011. Capacity To Ship Packages Within D Days (Medium)¶
Solution
Monotonicity
If we can successfully ship all packages within
Ddays with capacitym, then we can definitely ship them all with any capacity larger thanm
We can design a condition function, let’s call i canNotShip, given an input capacity mid, it returns whether it’s not possible to ship all packages within D days. This can run in a greedy way: if there’s still room for the current package, we put this package onto the conveyor belt, otherwise we wait for the next day to place this package. If the total days needed exceeds D, we return True, otherwise we return False.
Next, we need to initialize our boundary correctly. Obviously right should be at least max(weights), otherwise the conveyor belt couldn’t ship the heaviest package. On the other hand, right need not be more than sum(weights), because then we can ship all packages in just one day.
Reference: * Written solution * Video solution * Time complexity
Analysis
Time Complexity: O(Nlog****_S_**)**
where:
N is the length of the array
S is the sum of all weights in the array
We perform logN analyses, and for each we process n packages.
Space Complexity: O(1)
def shipWithinDays(self, weights: List[int], days: int) -> int:
def canNotShip(mid):
total_days = 1
total_weight = 0
for weight in weights:
if weight > mid:
return True
total_weight += weight
if total_weight > mid:
total_weight = weight
total_days += 1
return total_days > days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + (hi - lo) // 2
if canNotShip(mid):
lo = mid + 1
else:
hi = mid
return lo
410. Split Array Largest Sum (Hard)¶
Solution
Monotonicity
If we can split array into several subarrays such that every subarray-sum is less than or equal to
threshold, then we can split arrays with any number greater thanthreshold.
This is very similar to 1011. Capacity To Ship Packages Within D Days (Medium)
Reference: * Written solution
Analysis
Time Complexity: O(Nlog****_S_**)**
where:
N is the length of the array
S is the sum of all nums in the array
We perform logN analyses, and for each we process n numbers.
Space Complexity: O(1)
def splitArray(self, nums: List[int], m: int) -> int:
def canNotHold(mid):
total = 0
splits = 1
for num in nums:
if num > mid:
return False
total += num
if total > mid:
total = num
splits += 1
return splits > m
lo, hi = max(nums), sum(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if canNotHold(mid):
lo = mid + 1
else:
hi = mid
return lo
875. Koko Eating Bananas (Medium)¶
Solution
Monotonicity (with image)
If Koko can eat
kbananas-per-hour and can eat all bananas withinhhours, then Koko can eat at any rate starting fromkand finish eating all bananas withinkhours.!` <https://t7208592.p.clickup-attachments.com/t7208592/37c6f30d-47d5-4c5f-b97f-6e75fc8defbb/image.png>`_
!` <https://t7208592.p.clickup-attachments.com/t7208592/eefa1314-2218-4c71-af44-4fcc38201a28/image.png>`_
Again similar to 1011. Capacity To Ship Packages Within D Days (Medium).
Obviously, the lower bound of the search space is 1, and upper bound is max(piles), because Koko can only choose one pile of bananas to eat every hour.
Reference: * Official Leetcode solution * Written solution
Analysis
Time Complexity: O(Nlog****_M_**)**
where:
N is the length of the array
M is the maximum number of bananas in a pile
We perform logN analyses, and for each we process n piles.
Space Complexity: O(1)
def minEatingSpeed(self, piles: List[int], h: int) -> int:
def canNotEat(mid):
hours = 0
for bananas in piles:
# hours += math.ceil(bananas/mid) # slower
hours += ((bananas - 1) // mid) + 1 # faster
return hours > h
lo, hi = 1, max(piles)
while lo < hi:
mid = lo + (hi - lo) // 2
if canNotEat(mid):
lo = mid + 1
else:
hi = mid
return lo
1482. Minimum Number of Days to Make m Bouquets (Medium)¶
TODO_RST
Solution
Monotonicity
If we can make
mbouquets after waiting forddays, then we can definitely finish that as well if we wait for more thanddays.
Again similar to 1011. Capacity To Ship Packages Within D Days (Medium).
Obviously, the lower bound of the search space is 1, and upper bound is max(bloomDay), because we can bloom m flowers within max(bloomDays) if possible, else we however need to return -1.
The below code is written initially, and will be easier for anyone to understand the logic of the optimized code.
Reference: * Written solution * Video Solution
Analysis
Time Complexity: O(Nlog****_M_**)**
where:
N is the length of the array
M is the maximum number of days to bloom in a
bloomDays.We perform
logNanalyses, and for each we processnpiles.Space Complexity: O(1)
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
def canNotBloom(mid): # Space optimized subproblem
flowers = 0
bouqets = 0
for bloom in bloomDay:
if flowers == k:
bouqets += 1
flowers = 0
if bloom > mid:
flowers = 0
else:
flowers += 1
bouqets += int(flowers == k)
return bouqets < m
if len(bloomDay) < m * k:
return -1
lo, hi = 1, max(bloomDay)
while lo < hi:
mid = lo + (hi - lo) // 2
if canNotBloom(mid):
lo = mid + 1
else:
hi = mid
return lo
1231. Divide Chocolate (Hard)¶
Solution
Monotonicity (kind of Inverted version from previous problems)
If a cutting plan with the minimum value of
xexists, then there also exists a cutting plan with the minimum value ofx - 1In other words, since 5 is a workable value, 4 is guaranteed to be a workable value.
!` <https://t7208592.p.clickup-attachments.com/t7208592/37a2fe71-2843-4c0e-ba13-bb47365683aa/image.png>`_
Divide the sub-array into K+1 sub-arrays such that the minimum sub-array sum is as maximum as possible. In essence, it is asking for the maximum of the minimum sum of continuous subarrays.
Hence, once we find a cutting plan with a minimum workable value of x, there are only two possible scenarios:
There exists a piece with a sweetness of exactly
x.There does not exist a piece with an exact sweetness of
x. However, a workable value exists that is larger thanx.Reference: * Official Leetcode soution * Leetcode discuss by dcvan24
Analysis
Time Complexity: O(Nlog****_S_**)**
where:
N is the length of the array
S is the sum of all sweetness in the array
We perform logN analyses, and for each we process n numbers.
Space Complexity: O(1)
def maximizeSweetness(self, sweetness: List[int], k: int) -> int:
def canNotDivide(mid):
total_sweet = 0
splits = 0
for sweet in sweetness:
total_sweet += sweet
if total_sweet > mid:
total_sweet = 0
splits += 1
return (
splits > k
) # The reason is that when a fixed cutting plan with the minimal value x exists but we can not find a single piece with the sweetness of exactly x, it means that every piece has a sweetness greater than x.
lo, hi = min(sweetness), sum(sweetness)
while lo < hi:
mid = lo + (hi - lo) // 2
if canNotDivide(mid):
lo = mid + 1
else:
hi = mid
return lo