Skip to main content

Monotone Function, O(N log N)

When the array itself isn't what we search, but the answer is. If a candidate value works, every larger (or every smaller) value also works - that monotonicity lets us binary-search the answer space and replace a scan with a feasibility(mid) check. Each check costs O(N), and we run log(range) of them.

Split Input Array​

Guess a capacity / size / threshold, then greedily verify it can partition the array within the allowed number of pieces.

1011. Capacity To Ship Packages Within D Days​

Medium·
Solutions:
Visualize
class Solution:
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​

Solutions:
Visualize
class Solution:
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​

Solutions:
Visualize
class Solution:
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·
Solutions:
Visualize
class Solution:
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·
Solutions:
Visualize
class Solution:
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

More problems built on the same "guess the answer, verify greedily" shape:

Kth Smallest​

Binary-search the value, and let the feasibility check count how many elements fall at or below mid.