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·
Explanation

We don't binary-search over an array index - we binary-search over the answer itself: the ship's capacity. This works because feasibility is monotone: if we can ship every package within days days at capacity m, we can also ship them at any capacity > m. So the valid capacities form a contiguous suffix and we want its leftmost element.

The condition function:

  • canNotShip(mid) greedily simulates loading at capacity mid: keep adding packages onto the current day until the next one would overflow, then start a new day.
  • If a single package is heavier than mid, it can never ship, so it returns True.
  • It returns True when mid is too small (total_days > days), which is exactly the "go right" signal for the lower-bound template.

The search range:

  • Lower bound is max(weights) - the belt must at least carry the heaviest single package.
  • Upper bound is sum(weights) - that capacity ships everything in one day.
Analysis
Time
O(N log S)
  • N is the number of packages, S is the sum of all weights.
  • Binary search over the capacity range takes log S steps; each step scans all N packages.
Space
O(1)
  • Only scalar counters are used.
FIG. 1011 CAPACITY TO SHIP PACKAGES WITHIN D DAYS● INTERACTIVE
visualization loads as you reach it
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​

Hard·
Explanation

Instead of searching an index, we binary-search over the answer itself: the largest allowed subarray sum (the threshold). Feasibility is monotone: if the array can be split into m subarrays each with sum <= threshold, then it can also be split with any threshold > threshold. So the valid thresholds form a contiguous suffix and we want its leftmost element.

The condition function:

  • canNotHold(mid) greedily packs numbers into the current subarray until adding the next one exceeds mid, then starts a new split.
  • It returns True when mid is too small (splits > m), which is the "go right" signal for the lower-bound template.

The search range:

  • Lower bound is max(nums) - any threshold below the largest element is infeasible.
  • Upper bound is sum(nums) - that threshold keeps everything in one subarray.

This mirrors 1011. Capacity To Ship Packages Within D Days almost exactly.

Analysis
Time
O(2N + N log S)
  • N is the length of nums, S is the sum of all numbers.
  • max(nums) and sum(nums) are each a separate O(N) pass to set up lo and hi - N + N collapses to 2N.
  • The while lo < hi binary search takes log S steps, and each step's canNotHold(mid) scans all N numbers - N log S.
Space
O(1)
  • Only the scalar counters total, splits, lo, hi, and mid are used.
FIG. 410 SPLIT ARRAY LARGEST SUM● INTERACTIVE
visualization loads as you reach it
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​

Medium·
Explanation

Here we don't binary-search over an array index - we binary-search over the answer itself: the eating speed k. This works because the feasibility test is monotone: if Koko can finish within h hours at speed k, she can also finish at any speed > k. So the set of valid speeds is a contiguous suffix [answer, max(piles)], and we want its leftmost element.

The condition function:

  • canNotEat(mid) greedily computes the hours needed at speed mid: each pile takes ceil(bananas / mid) hours, written branch-free as ((bananas - 1) // mid) + 1.
  • It returns True when mid is too slow (hours > h), which is exactly the "go right" signal for the lower-bound template.

The search range:

  • Lower bound is 1 (must eat at least one banana per hour).
  • Upper bound is max(piles) - any faster wastes time since only one pile is eaten per hour.
Analysis
Time
O(N + N log M)
  • N is the number of piles, M is the largest pile.
  • max(piles) is one O(N) pass to set hi.
  • Binary search over [1, M] takes log M steps, and each step's canNotEat(mid) scans all N piles - N log M.
Space
O(1)
  • Only scalar counters are used.
FIG. 875 KOKO EATING BANANAS● INTERACTIVE
visualization loads as you reach it
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·
Explanation

We binary-search over the answer itself: the number of days to wait. Feasibility is monotone: if we can make m bouquets after waiting d days, we can also make them after waiting any number of days > d. So the valid wait-times form a contiguous suffix and we want its leftmost element.

The condition function:

  • canNotBloom(mid) scans the flowers in order. A flower has bloomed if bloomDay <= mid. We greedily collect runs of k adjacent bloomed flowers into one bouquet; any unbloomed flower resets the current run.
  • It returns True when mid days are not enough (bouqets < m), which is the "go right" signal for the lower-bound template.

The search range:

  • Lower bound is 1.
  • Upper bound is max(bloomDay), by which every flower has bloomed.
  • If len(bloomDay) < m * k, there aren't enough flowers and the answer is -1.
Analysis
Time
O(N log M)
  • N is the length of the array, M is the maximum value in bloomDay.
  • Binary search over [1, M] takes log M steps; each step scans all N flowers.
Space
O(1)
  • Only scalar counters are used.
FIG. 1482 MINIMUM NUMBER OF DAYS TO MAKE M BOUQUETS● INTERACTIVE
visualization loads as you reach it
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·
Explanation

We binary-search over the answer itself: the minimum piece sweetness we're willing to keep. We split the bar into k + 1 contiguous pieces and want to maximize the minimum piece sum. Feasibility is monotone (an inverted version of the usual shape): if a target minimum x is achievable, then x - 1 is also achievable - making the bar easier to cut into enough pieces. So the valid targets form a contiguous prefix and we want its rightmost element.

The condition function:

  • canNotDivide(mid) greedily accumulates sweetness, cutting a new piece whenever the running sum exceeds mid, and counts how many such cuts (splits) are possible.
  • It returns True when mid is achievable (splits > k), pushing lo up to find the largest workable minimum.

The search range:

  • Lower bound is min(sweetness).
  • Upper bound is sum(sweetness) - keep the entire bar as one piece.
Analysis
Time
O(N log S)
  • N is the length of the array, S is the sum of all sweetness values.
  • Binary search over the sweetness range takes log S steps; each step scans all N chunks.
Space
O(1)
  • Only scalar counters are used.
FIG. 1231 DIVIDE CHOCOLATE● INTERACTIVE
visualization loads as you reach it
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.