What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Binary Search Boundary

Builds on Lower Bound and Upper Bound, which you haven’t finished yet.

P1MediumBuilt on Lower Bound~6 min speedrun

Binary Search on Answer (Parametric Search)

Built on

Lower BoundThe candidates are possible answers, not positions in a list, and the check simulates the problem for one answer.

Unlocks

Kth Smallest Continuous Bisection

The problem

Capacity To Ship Packages Within D Days (LC 1011)(opens leetcode.com)

A conveyor belt lines up packages that must all ship out within days days. The i-th package weighs weights[i]; each day you load the ship with the next packages in belt order, but the total you load in a single day can never exceed the ship's weight capacity.

Find the smallest ship capacity that still gets every package shipped within days days.

Example 1

Input:weights = [1,2,3,4,5,6,7,8,9,10], days = 5

Output:15

With capacity 15, the days can be 1+2+3+4+5 = 15, 6+7 = 13, 8, 9, 10: exactly 5 days. With capacity 14, the same rule needs 6 days, so 15 is the smallest capacity that works.

Feasible Function

answers that are numbers ➔ a check that simulates the task for one number ➔ the first number that passes

Spot it when: The problem asks for the smallest capacity, speed or number of days that lets a task succeed, and a larger value never makes the task harder.

Feasible Function

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: Every capacity before lo fails can_ship, and every capacity from hi on passes it, so the smallest passing capacity is at least lo and at most hi.

A larger capacity never needs more days, so can_ship(capacity) is False for small capacities and True from some capacity on. The first True is the answer, so call binary_search_lower_bound(lo, hi, can_ship) with lo = 1 and hi = sum(weights) + 1. can_ship is exact for one capacity: it fills each day in order until the next package would overflow, and it counts the days. The total weight always passes, because the ship carries everything in one day, so the answer is never above sum(weights). The trap is a package that is heavier than the ship, so keep the guard w > capacity in can_ship. Without it, can_ship(1) opens a new day for a package of weight 5 and still loads it, so shipWithinDays([5], 2) returns 1 and the right answer is 5.

See it run

Feasible Function, step by step

lo 1hi 9mid -

Each column is one capacity to try. T means True and F means False. The last column is one past the total weight 8: it always works, so it is never tested.

lo the left end of the range. Every candidate before lo is False.
hi the right end of the range. The total weight always works, so hi is allowed as the answer, and it is never tested.
mid the candidate that this pass tests
mid = lo mid and lo are the same candidate
answer the smallest capacity that works

Start: lo = 1 and hi = 9. The answer is somewhere from lo to hi, and hi is never tested.

capacity

1lo

endhi

can_ship(capacity)

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the guard w > capacity
Mistake
```
pass
```
Fix
```
if w > capacity:
    return False
```
What happens: Without the guard, a package that is heavier than the ship opens a new day and is still loaded. So can_ship passes for a capacity that is too small. For weights = [5] and days = 2, capacity 1 is reported as working, and the search returns 1. The right answer is 5.
Example: weights = [5], days = 2
Mistake: returns 1Fix: returns 5
Gotcha 2: Writing days_needed == days instead of days_needed <= days
Mistake
```
return days_needed == days
```
Fix
```
return days_needed <= days
```
What happens: A big ship needs fewer days than days. With ==, such a capacity is rejected, so the row is not False then True. For the input below, no capacity is accepted in the range, and the search returns hi, which is 56.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 56Fix: returns 15
Gotcha 3: Writing load + w >= capacity instead of load + w > capacity
Mistake
```
if load + w >= capacity:
```
Fix
```
if load + w > capacity:
```
What happens: A day may carry exactly capacity. With >=, a package that fills the day exactly starts a new day, so can_ship counts too many days and rejects a capacity that works. For the input below, capacity 15 is rejected, and the search returns 16.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 16Fix: returns 15
Gotcha 4: Setting hi too low
Mistake
```
hi = max(weights)
```
Fix
```
hi = sum(weights) + 1
```
What happens: The range must hold the answer. With hi = max(weights), the range ends before the heaviest package, and the answer 15 is outside it. No capacity in the range passes, so the search returns hi, which is 10.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 10Fix: returns 15
Gotcha 5: Counting the first day as 0
Mistake
```
days_needed, load = 0, 0
```
Fix
```
days_needed, load = 1, 0
```
What happens: The simulation starts on day 1. Starting the count at 0 gives every capacity one day less than it needs. So the check passes for capacities that are too small. For the input below, the search returns 11, and the right answer is 15.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 11Fix: returns 15

Not this one if…

The candidates already exist as positions (versions 1..n) and each check is one call, as in First Bad Version (LC 278): there is no answer range to invent and no plan to simulate. See Lower Bound
The question asks for a rank, the k-th smallest value of a large sorted structure, as in Kth Smallest Number in Multiplication Table (LC 668), not the smallest setting that makes a plan work. See Kth Smallest
Each candidate is tested with one formula and there is no plan to simulate, as in Sqrt(x) (LC 69): the answer is simply the last k whose square still fits in x. See Upper Bound
The answer is a real number accepted within 10^-5, the best average in Maximum Average Subarray II (LC 644): there is no next value to step to, so lo = mid + 1 skips answers and while lo < hi never ends. The same holds when this card's greedy check drives a real-valued answer, as in Minimize Max Distance to Gas Station (LC 774): keep the check, switch to the Continuous Bisection loop. See Continuous Bisection

Theory

The question we build

What we know

The packages ship in the given order. Each day carries a run of packages, and the total weight of that run cannot pass the capacity.

What the problem gives us

The input is weights and days. The answer is a capacity, not an index, so no list holds it. We ask one yes-or-no question for each capacity.

The question we build

For each capacity we ask: "can the packages ship within days days?" We use weights = [1, 2, 3, 1, 1] and days = 4, Example 3 of Capacity To Ship Packages Within D Days (LC 1011). The total weight is 8, so the candidates are the capacities 1 to 8. The answers are False, False, True, True, True, True, True, True. The first True is capacity 3, which is the answer.

capacity

can_ship(capacity)

Capacity 1 and 2 fail: a package of weight 3 does not fit. Capacity 3 passes, and every larger capacity passes too.

Narrowing down to the template

The candidates are the capacities from 1 up to the total weight, so lo = 1 and hi = sum(weights) + 1. The call is binary_search_lower_bound(lo, hi, can_ship).

Step 1: Try every capacity

The check can_ship runs the task for one capacity. The answer is the first capacity for which can_ship is True. The scan tries the capacities 1, 2, 3, and so on.

Step 1: Try every capacityPython

1		def ship_scan(weights, days):
2		def can_ship(capacity):
3		days_needed, load = 1, 0
4		for w in weights:
5		if w > capacity:
6		return False # one package is heavier than the ship
7		if load + w > capacity:
8		days_needed += 1 # start a new day
9		load = 0
10		load += w
11		return days_needed <= days
12
13		capacity = 1
14		while not can_ship(capacity):
15		capacity += 1
16		return capacity

Cost: Up to S checks, where S is the answer. One check costs O(N), with N = len(weights), so the time is O(S * N).

Step 2: Lower Bound over the capacities

The scan asks the check about every capacity. Lower Bound asks about one capacity, and removes half of the remaining capacities. The check can_ship does not change.

Step 2: Lower Bound over the capacitiesPython

1	+	New line: def ship_within_days(weights, days):
2		def can_ship(capacity):
3		days_needed, load = 1, 0
4		for w in weights:
5		if w > capacity:
6		return False # one package is heavier than the ship
7		if load + w > capacity:
8		days_needed += 1 # start a new day
9		load = 0
10		load += w
11		return days_needed <= days
12
13	+	New line: lo = 1 # smallest capacity to try
14	+	New line: hi = sum(weights) + 1 # one past the total weight, which always works
15	+	New line: return binary_search_lower_bound(lo, hi, can_ship)

Cost: About log S checks, with S = sum(weights), so the time is O(N * log S) and the space is O(1).

Item	Try every capacity	Lower Bound
`capacity = 1` and `while not can_ship(capacity): capacity += 1`	`lo = 1`, `hi = sum(weights) + 1`, and one Lower Bound call	The loop over every capacity becomes one Lower Bound call.

The shorter version

The shorter versionPython

1		import bisect
2
3		def ship_within_days_short(weights, days):
4		def can_ship(capacity):
5		days_needed, load = 1, 0
6		for w in weights:
7		if w > capacity:
8		return False
9		if load + w > capacity:
10		days_needed += 1
11		load = 0
12		load += w
13		return days_needed <= days
14
15		return bisect.bisect_left(range(1, sum(weights) + 1), True, key=can_ship) + 1

range(1, sum(weights) + 1) holds the candidate capacities. bisect_left returns a position in that range, so + 1 turns it back into a capacity. This form needs Python 3.10 or later, because of key=.

Build the check and the range

State the question. "Can the task be done with this value?" It is always a yes-or-no question.
Write the simulation. Usually one pass over the input. It returns True or False.
Show that a larger value cannot hurt. Say why, and draw the row on a tiny input to see it.
Choose the range. lo is the smallest value that could work. hi is one past a value that always works.

For shipping, lo = 1 and hi = sum(weights) + 1. The guard w > capacity makes can_ship return False for every capacity below the heaviest package, so lo = 1 is correct. Starting at max(weights) gives the same answer and skips those checks. For Koko Eating Bananas (LC 875), lo = 1 and hi = max(piles) + 1. In both cases the last candidate always passes, so the search always returns a candidate and never needs a "not found" value.

Write the check first, and read it on its own, before you read the search.

Second check: Koko Eating Bananas (LC 875)

There are piles of bananas, and Koko eats at a speed of k bananas per hour. Koko eats from one pile per hour at most. We return the smallest speed that finishes all the piles within h hours.

Code / Blueprint

import math
 
def min_eating_speed(piles, h):
    def can_finish(speed):
        hours = 0
        for pile in piles:
            hours += math.ceil(pile / speed)    # whole hours this pile needs
        return hours <= h
 
    lo = 1
    hi = max(piles) + 1                         # one past the biggest pile, which always works
    return binary_search_lower_bound(lo, hi, can_finish)

For piles = [3, 6, 7, 11] and h = 8, the answer is 4. For piles = [30, 11, 23, 4, 20], h = 5 gives 30, and h = 6 gives 23.

	Shipping (LC 1011)	Koko (LC 875)
Can an item be split across periods?	No. A package that does not fit moves whole to the next day.	Yes. A pile that is bigger than the speed continues in the next hour.
Can a period be shared by two items?	Yes. Several packages ride on one day.	No. Koko starts the next pile only in the next hour, so the rest of an hour is unused. With `[1, 1, 1]` at speed 1, each pile takes its own hour.
Does the order of the items matter?	Yes. The check packs in order.	No. The check is a sum.
The check	A running load, reset when it would overflow.	The sum of `ceil(pile / speed)`.

speed

can_finish(speed)

piles = [3, 6, 7] and h = 5: speed 3 needs 1 + 2 + 3 = 6 hours, and speed 4 needs 1 + 2 + 2 = 5 hours.

How does your check count?

Look at how your check counts, and pick one of the four kinds below. All four sit under the same Lower Bound call. Only the check changes.

Kind	How the check counts	Example
Greedy packing in order	A running total, reset on overflow, counts the periods. This is the `can_ship` above.	Capacity To Ship Packages Within D Days (LC 1011), Split Array Largest Sum (LC 410)
A formula per item, summed	Each item adds its own `ceil` or `floor`. The order does not matter.	Koko Eating Bananas (LC 875), Minimum Speed to Arrive on Time (LC 1870)
Greedy count of groups or picks	One scan counts how many groups or picks fit.	Minimum Number of Days to Make m Bouquets (LC 1482)
Reachability under a limit	A search (BFS, DFS or union-find) asks if the goal can be reached when each step may use at most the limit.	Path With Minimum Effort (LC 1631), Swim in Rising Water (LC 778)

A check that asks for the largest value that works belongs to the Upper Bound card.

Every check returns a plain True or False, and its row must read False…False True…True. A check that counts cost, such as days or hours, uses <= its limit. A check that counts output, such as trips or bouquets, uses >= the amount needed. With the other comparison, the row reads True…True False…False, and Lower Bound cannot use it.

Skeleton 2: A formula per item, summed

Code / Blueprint

def can_do(x):
    total = 0
    for item in items:
        total += formula(item, x)               # what this item costs (or produces) for the value x
    return total <= budget                      # use >= when the formula counts output that grows with x

Koko Eating Bananas (LC 875) uses formula = math.ceil(pile / speed) and <= h. A second instance counts output. Each bus makes x // time trips in x minutes, and the test is >= total_trips:

Code / Blueprint

def min_time_for_trips(times, total_trips):
    def can_do(x):
        trips = 0
        for time in times:
            trips += x // time                  # whole trips this bus makes in x minutes
        return trips >= total_trips
 
    lo = 1
    hi = min(times) * total_trips + 1           # the fastest bus alone makes every trip in this time
    return binary_search_lower_bound(lo, hi, can_do)

minutes

can_do(x)

times = [1, 2, 3] and total_trips = 5: in 3 minutes the buses make 3 + 1 + 1 = 5 trips.

Skeleton 3: Count groups or picks

Code / Blueprint

def can_do(x):
    groups, run = 0, 0
    for item in items:
        if fits(item, x):
            run += 1
            if run == group_size:
                groups += 1
                run = 0                         # start the next group
        else:
            run = 0                             # a gap breaks the group
    return groups >= needed

Minimum Number of Days to Make m Bouquets (LC 1482) uses fits = bloom_day <= x, group_size = k and needed = m. The answer is -1 when m * k is larger than the number of flowers.

Code / Blueprint

def min_days_for_bouquets(bloom_day, m, k):
    if m * k > len(bloom_day):
        return -1                               # there are not enough flowers
 
    def can_do(x):
        groups, run = 0, 0
        for day in bloom_day:
            if day <= x:
                run += 1
                if run == k:
                    groups += 1
                    run = 0                     # start the next bouquet
            else:
                run = 0                         # a flower that is not ready breaks the bouquet
        return groups >= m
 
    lo = min(bloom_day)
    hi = max(bloom_day) + 1                     # one past the last bloom day, which always works
    return binary_search_lower_bound(lo, hi, can_do)

day

can_do(x)

bloom_day = [1, 10, 3, 10, 2], m = 3, k = 1: on day 3 three flowers are ready.

Skeleton 4: Reachability under a limit

Code / Blueprint

from collections import deque
 
def can_do(limit):
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            return True
        for nxt in neighbors(node):
            if nxt not in seen and step_cost(node, nxt) <= limit:
                seen.add(nxt)
                queue.append(nxt)
    return False

Path With Minimum Effort (LC 1631) uses step_cost as the height difference between two cells.

Code / Blueprint

from collections import deque
 
def minimum_effort_path(heights):
    rows, cols = len(heights), len(heights[0])
 
    def can_do(limit):
        seen = {(0, 0)}
        queue = deque([(0, 0)])
        while queue:
            r, c = queue.popleft()
            if (r, c) == (rows - 1, cols - 1):
                return True
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                    if abs(heights[nr][nc] - heights[r][c]) <= limit:
                        seen.add((nr, nc))
                        queue.append((nr, nc))
        return False
 
    biggest_step = max(max(row) for row in heights) - min(min(row) for row in heights)
    lo = 0
    hi = biggest_step + 1                       # one past the biggest possible step, which always works
    return binary_search_lower_bound(lo, hi, can_do)

limit

can_do(limit)

heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]: a path exists when no step is larger than 2.

Two edge cases that need no special case

For Capacity To Ship Packages Within D Days (LC 1011), two edge cases fall out of the search directly, with no extra if:

When days equals len(weights), every package must ship on its own day, so the answer is max(weights).
When days equals 1, the ship must take every package at once, so the answer is sum(weights).

Both values are inside the range from 1 to sum(weights), and can_ship reports them correctly. The search returns them without the caller checking for either case.

Real-world use

A service must handle a recorded day of traffic. The team wants the smallest machine size that does it without dropping requests. A replay of the traffic on one machine size answers "does it handle the traffic?" for that size. A bigger machine never handles less, so Lower Bound over the machine sizes finds the smallest size with about log R replays, where R is the number of sizes.

Say it in an interview

"The answer is a capacity, not an index, so I write the check can_ship as a simulation. It fills each day in order until the next package would overflow, counts the days, and returns days_needed <= days. A larger capacity never needs more days, so the answers are False and then True, and I run Lower Bound over the capacities from 1 to sum(weights) + 1. The check must return False when a package is heavier than the ship, so the guard w > capacity stays in it. The time is O(N * log S), with N = len(weights) and S = sum(weights). The space is O(1)."

Common Questions

How do I show that the check is monotone?: Show that any plan that works for one value also works for a larger value. For shipping, the same loads fit in a larger ship, so the same number of days is enough. For Koko Eating Bananas (LC 875), a faster speed never needs more hours for a pile.
What is the cost when one check is expensive?: One check costs T, and Lower Bound makes about log R checks, where R is the size of the range. The time is O(T * log R). For shipping, T = O(N) and R = sum(weights), so the time is O(N * log S) with S = sum(weights).

Practice

Canonical LeetCode:Capacity To Ship Packages Within D Days (LC 1011)Koko Eating Bananas (LC 875)Magnetic Force Between Two Balls (LC 1552)Divide Chocolate (LC 1231)Cutting Ribbons (LC 1891)Minimum Number of Days to Make m Bouquets (LC 1482)Minimum Limit of Balls in a Bag (LC 1760)Maximum Candies Allocated to K Children (LC 2226)Split Array Largest Sum (LC 410)Minimum Speed to Arrive on Time (LC 1870)Path With Minimum Effort (LC 1631)Swim in Rising Water (LC 778)Maximum Number of Removable Characters (LC 1898)

Many books teach this search with two bounds that are both answers: lo = max(weights) and hi = sum(weights). The loop keeps hi as a possible answer. This course uses the template with the range [lo, hi), where hi is one past the last candidate.

The classic loop

Old Way

Python

1	from typing import List
2
3	def shipWithinDays(weights: List[int], days: int) -> int:
4	def can_ship(capacity: int) -> bool:
5	needed_days = 1
6	curr_load = 0
7	for w in weights:
8	if curr_load + w > capacity:
9	needed_days += 1
10	curr_load = 0
11	curr_load += w
12	return needed_days <= days
13
14	lo = max(weights) # Minimum possible capacity
15	hi = sum(weights) # Maximum possible capacity
16
17	while lo < hi:
18	mid = lo + (hi - lo) // 2
19	if can_ship(mid):
20	hi = mid # Capacity feasible; attempt smaller capacity
21	else:
22	lo = mid + 1 # Capacity infeasible; must increase
23
24	return lo

From the classic loop to our template

Old Way line	In our template	Why
lo = max(weights)	lo = 1	The check has the guard `w > capacity`, so it returns False for a capacity below the heaviest package. The start can be 1.
hi = sum(weights)	hi = sum(weights) + 1	The template's `hi` is one past the last candidate. The total weight is the last candidate.
while lo < hi: ... if can_ship(mid): hi = mid else: lo = mid + 1	binary_search_lower_bound(lo, hi, can_ship)	The same loop, written once as the template.
if curr_load + w > capacity:	if w > capacity: return False, then if load + w > capacity:	The guard rejects a ship that is smaller than one package.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same loop. The template only gives the loop a name.

Gotchas of the classic loop

Gotchas1 of 4

The trap
Gotcha 1: Starting lo at 1 instead of max(weights), in this loop
Mistake
```
lo = 1
```
Fix
```
lo = max(weights)
```
What happens: This older loop has no guard w > capacity. Its can_ship never checks that one package fits on a day by itself. With a capacity below the heaviest package, it opens a new day and still loads that package. So can_ship can pass for a capacity that cannot carry the package. Starting at max(weights) keeps every tested capacity large enough for each package.
Example: weights = [1, 10], days = 2
Mistake: returns 1Fix: returns 10
Gotcha 2: Writing needed_days < days instead of needed_days <= days
Mistake
```
return needed_days < days
```
Fix
```
return needed_days <= days
```
What happens: A capacity that ships everything in exactly days days is allowed. needed_days < days rejects that capacity. The search then moves lo above it and returns a larger capacity than needed.
Example: Capacity To Ship Packages Within D Days (LC 1011): weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 17Fix: returns 15
Gotcha 3: Running this loop when the question asks for a maximum
What happens: This loop returns the smallest value that passes the check. Magnetic Force Between Two Balls (LC 1552) asks for the largest distance that still passes. Maximum Candies Allocated to K Children (LC 2226) asks for the largest pile size that still passes. There, small values pass and large values fail. Run the Upper Bound loop on the answer range instead, because it returns the last value that passes.
Gotcha 4: Writing p // k for the hours of one pile
Mistake
```
hours += p // k
```
Fix
```
hours += (p + k - 1) // k
```
What happens: In Koko Eating Bananas (LC 875), a pile of p bananas at speed k takes ceil(p / k) hours. p // k rounds down, so a pile with a remainder gets one hour too few. (p + k - 1) // k rounds up and stays in integers. The check then accepts speeds that are too slow.
Example: piles = [3, 6, 7, 11], k = 4 (total hours)
Mistake: returns 4Fix: returns 8

Earlier signals

The question asks for the smallest (or largest) capacity, speed, time or distance that passes a check, and a bigger value only makes the check easier.

Earlier invariant

Every capacity below lo fails can_ship, and hi always passes it, so the smallest passing capacity is in [lo, hi].

Earlier direction

implicit parameter range [smallest possible answer, largest possible answer] ➔ greedy feasibility predicate ➔ optimal value

Earlier description

can_ship is monotonic: if one capacity ships every package within days, every larger capacity does too. So binary search the capacities themselves, not an array: when can_ship(mid) passes, keep mid as the best answer so far with hi = mid; when it fails, the answer is larger, so lo = mid + 1. The greedy check is exact: filling each day until the next package won't fit uses the fewest days possible for that capacity, so a failed check proves mid is too small. The trap is the bounds: start lo at max(weights), because below it the heaviest package fits on no day and can_ship quietly counts it anyway, and start hi at sum(weights), which always ships in one day.

Earlier template

Python

1	from typing import Callable, List
2
3	def min_feasible(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
4	"""Feasible Function: the smallest answer in [lo, hi] that passes is_feasible.
5	Precondition: is_feasible is monotonic (False, ..., False, True, ..., True) and hi passes it.
6	This loop finds only the smallest answer that passes. For the largest one, use the loop of the Upper Bound card.
7	R = hi - lo, the size of the answer range. T = the cost of one is_feasible call.
8	Time: O(T * log R) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12	if is_feasible(mid):
13	hi = mid # mid passes: keep it, try smaller answers
14	else:
15	lo = mid + 1 # mid fails: every answer up to mid fails too
16
17	return lo # lo == hi: the smallest answer that passes
18
19
20	# Capacity To Ship Packages Within D Days (LC 1011): the template above, with is_feasible written as can_ship. One can_ship call costs T = O(N), so O(N * log(sum(weights) - max(weights))) time and O(1) space. The step debugger runs this code.
21	def shipWithinDays(weights: List[int], days: int) -> int:
22	def can_ship(capacity: int) -> bool:
23	needed_days = 1
24	curr_load = 0
25	for w in weights:
26	if curr_load + w > capacity:
27	needed_days += 1
28	curr_load = 0
29	curr_load += w
30	return needed_days <= days
31
32	lo = max(weights) # Minimum possible capacity
33	hi = sum(weights) # Maximum possible capacity
34
35	while lo < hi:
36	mid = lo + (hi - lo) // 2
37	if can_ship(mid):
38	hi = mid # Capacity feasible; attempt smaller capacity
39	else:
40	lo = mid + 1 # Capacity infeasible; must increase
41
42	return lo

Earlier gotchas

Starting lo at 1 instead of max(weights)

can_ship never checks that one package fits on a day by itself. With a capacity below the heaviest package, it opens a new day and still loads that package. So can_ship can pass for a capacity that cannot carry the package. Starting at max(weights) keeps every tested capacity large enough for each package.

Writing needed_days < days instead of needed_days <= days

A capacity that ships everything in exactly days days is allowed. needed_days < days rejects that capacity. The search then moves lo above it and returns a larger capacity than needed.

Running this loop when the question asks for a maximum

This loop returns the smallest value that passes the check. Magnetic Force Between Two Balls (LC 1552) asks for the largest distance that still passes. Maximum Candies Allocated to K Children (LC 2226) asks for the largest pile size that still passes. There, small values pass and large values fail. Run the Upper Bound loop on the answer range instead, because it returns the last value that passes.

Writing p // k for the hours of one pile

In Koko Eating Bananas (LC 875), a pile of p bananas at speed k takes ceil(p / k) hours. p // k rounds down, so a pile with a remainder gets one hour too few. (p + k - 1) // k rounds up and stays in integers. The check then accepts speeds that are too slow.

Earlier look-alikes

The candidates already exist as positions (versions 1..n) and each check is one call, as in First Bad Version (LC 278): there is no answer range to invent and no plan to simulate.

The question asks for a rank, the k-th smallest value of a large sorted structure, as in Kth Smallest Number in Multiplication Table (LC 668), not the smallest setting that makes a plan work.

Each candidate is tested with one formula and there is no plan to simulate, as in Sqrt(x) (LC 69): the answer is simply the last k whose square still fits in x.

The answer is a real number accepted within 10^-5, the best average in Maximum Average Subarray II (LC 644): there is no next value to step to, so lo = mid + 1 skips answers and while lo < hi never ends. The same holds when this card's greedy check drives a real-valued answer, as in Minimize Max Distance to Gas Station (LC 774): keep the check, switch to the Continuous Bisection loop.

Earlier problems

Capacity To Ship Packages Within D Days

Koko Eating Bananas

Magnetic Force Between Two Balls

Divide Chocolate

Cutting Ribbons

Minimum Number of Days to Make m Bouquets

Minimum Limit of Balls in a Bag

Maximum Candies Allocated to K Children

Split Array Largest Sum

Maximum Number of Removable Characters

Theory Context•Binary Search Boundary

Builds on Lower Bound and Upper Bound, which you haven’t finished yet.

P1MediumBuilt on Lower Bound~6 min speedrun

Binary Search on Answer (Parametric Search)

Built on

Lower BoundThe candidates are possible answers, not positions in a list, and the check simulates the problem for one answer.

Unlocks

Kth Smallest Continuous Bisection

The problem

Capacity To Ship Packages Within D Days (LC 1011)(opens leetcode.com)

Find the smallest ship capacity that still gets every package shipped within days days.

Example 1

Input:weights = [1,2,3,4,5,6,7,8,9,10], days = 5

Output:15

With capacity 15, the days can be 1+2+3+4+5 = 15, 6+7 = 13, 8, 9, 10: exactly 5 days. With capacity 14, the same rule needs 6 days, so 15 is the smallest capacity that works.

Feasible Function

answers that are numbers ➔ a check that simulates the task for one number ➔ the first number that passes

Spot it when: The problem asks for the smallest capacity, speed or number of days that lets a task succeed, and a larger value never makes the task harder.

Feasible Function

Python

1	from typing import Callable, List
2
3
4	def binary_search_lower_bound(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
5	"""First candidate in [lo, hi) where is_feasible is True.
6	Precondition: is_feasible is monotonic (False, False, ..., True, True).
7	Returns hi when no candidate is True. N = hi - lo candidates. T = the cost of one is_feasible call.
8	Time: O(T * log N) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12
13	# 1. Check the Midpoint:
14	# is_feasible(mid) shows which side of the flip mid is on: before the answer (False),
15	# or at the answer or after it (True).
16	if is_feasible(mid):
17	# 2. Keep the Candidate:
18	# mid may be the first True, so keep it in the range by moving hi down to mid.
19	hi = mid
20	else:
21	# 3. Discard the Candidate:
22	# mid is False, so the first True must be strictly to the right of mid.
23	lo = mid + 1
24
25	# 4. Return the Boundary:
26	# The loop stops when lo equals hi; that position is the first True, or hi when none was True.
27	return lo

Invariant: Every capacity before lo fails can_ship, and every capacity from hi on passes it, so the smallest passing capacity is at least lo and at most hi.

See it run

Feasible Function, step by step

lo 1hi 9mid -

Each column is one capacity to try. T means True and F means False. The last column is one past the total weight 8: it always works, so it is never tested.

lo the left end of the range. Every candidate before lo is False.
hi the right end of the range. The total weight always works, so hi is allowed as the answer, and it is never tested.
mid the candidate that this pass tests
mid = lo mid and lo are the same candidate
answer the smallest capacity that works

Start: lo = 1 and hi = 9. The answer is somewhere from lo to hi, and hi is never tested.

capacity

1lo

endhi

can_ship(capacity)

1 / 8

Gotchas1 of 5

The trap
Gotcha 1: Leaving out the guard w > capacity
Mistake
```
pass
```
Fix
```
if w > capacity:
    return False
```
What happens: Without the guard, a package that is heavier than the ship opens a new day and is still loaded. So can_ship passes for a capacity that is too small. For weights = [5] and days = 2, capacity 1 is reported as working, and the search returns 1. The right answer is 5.
Example: weights = [5], days = 2
Mistake: returns 1Fix: returns 5
Gotcha 2: Writing days_needed == days instead of days_needed <= days
Mistake
```
return days_needed == days
```
Fix
```
return days_needed <= days
```
What happens: A big ship needs fewer days than days. With ==, such a capacity is rejected, so the row is not False then True. For the input below, no capacity is accepted in the range, and the search returns hi, which is 56.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 56Fix: returns 15
Gotcha 3: Writing load + w >= capacity instead of load + w > capacity
Mistake
```
if load + w >= capacity:
```
Fix
```
if load + w > capacity:
```
What happens: A day may carry exactly capacity. With >=, a package that fills the day exactly starts a new day, so can_ship counts too many days and rejects a capacity that works. For the input below, capacity 15 is rejected, and the search returns 16.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 16Fix: returns 15
Gotcha 4: Setting hi too low
Mistake
```
hi = max(weights)
```
Fix
```
hi = sum(weights) + 1
```
What happens: The range must hold the answer. With hi = max(weights), the range ends before the heaviest package, and the answer 15 is outside it. No capacity in the range passes, so the search returns hi, which is 10.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 10Fix: returns 15
Gotcha 5: Counting the first day as 0
Mistake
```
days_needed, load = 0, 0
```
Fix
```
days_needed, load = 1, 0
```
What happens: The simulation starts on day 1. Starting the count at 0 gives every capacity one day less than it needs. So the check passes for capacities that are too small. For the input below, the search returns 11, and the right answer is 15.
Example: weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 11Fix: returns 15

Not this one if…

The candidates already exist as positions (versions 1..n) and each check is one call, as in First Bad Version (LC 278): there is no answer range to invent and no plan to simulate. See Lower Bound
The question asks for a rank, the k-th smallest value of a large sorted structure, as in Kth Smallest Number in Multiplication Table (LC 668), not the smallest setting that makes a plan work. See Kth Smallest
Each candidate is tested with one formula and there is no plan to simulate, as in Sqrt(x) (LC 69): the answer is simply the last k whose square still fits in x. See Upper Bound
The answer is a real number accepted within 10^-5, the best average in Maximum Average Subarray II (LC 644): there is no next value to step to, so lo = mid + 1 skips answers and while lo < hi never ends. The same holds when this card's greedy check drives a real-valued answer, as in Minimize Max Distance to Gas Station (LC 774): keep the check, switch to the Continuous Bisection loop. See Continuous Bisection

Theory

The question we build

What we know

The packages ship in the given order. Each day carries a run of packages, and the total weight of that run cannot pass the capacity.

What the problem gives us

The input is weights and days. The answer is a capacity, not an index, so no list holds it. We ask one yes-or-no question for each capacity.

The question we build

capacity

can_ship(capacity)

Capacity 1 and 2 fail: a package of weight 3 does not fit. Capacity 3 passes, and every larger capacity passes too.

Narrowing down to the template

The candidates are the capacities from 1 up to the total weight, so lo = 1 and hi = sum(weights) + 1. The call is binary_search_lower_bound(lo, hi, can_ship).

Step 1: Try every capacity

The check can_ship runs the task for one capacity. The answer is the first capacity for which can_ship is True. The scan tries the capacities 1, 2, 3, and so on.

Step 1: Try every capacityPython

1		def ship_scan(weights, days):
2		def can_ship(capacity):
3		days_needed, load = 1, 0
4		for w in weights:
5		if w > capacity:
6		return False # one package is heavier than the ship
7		if load + w > capacity:
8		days_needed += 1 # start a new day
9		load = 0
10		load += w
11		return days_needed <= days
12
13		capacity = 1
14		while not can_ship(capacity):
15		capacity += 1
16		return capacity

Cost: Up to S checks, where S is the answer. One check costs O(N), with N = len(weights), so the time is O(S * N).

Step 2: Lower Bound over the capacities

The scan asks the check about every capacity. Lower Bound asks about one capacity, and removes half of the remaining capacities. The check can_ship does not change.

Step 2: Lower Bound over the capacitiesPython

1	+	New line: def ship_within_days(weights, days):
2		def can_ship(capacity):
3		days_needed, load = 1, 0
4		for w in weights:
5		if w > capacity:
6		return False # one package is heavier than the ship
7		if load + w > capacity:
8		days_needed += 1 # start a new day
9		load = 0
10		load += w
11		return days_needed <= days
12
13	+	New line: lo = 1 # smallest capacity to try
14	+	New line: hi = sum(weights) + 1 # one past the total weight, which always works
15	+	New line: return binary_search_lower_bound(lo, hi, can_ship)

Cost: About log S checks, with S = sum(weights), so the time is O(N * log S) and the space is O(1).

Item	Try every capacity	Lower Bound
`capacity = 1` and `while not can_ship(capacity): capacity += 1`	`lo = 1`, `hi = sum(weights) + 1`, and one Lower Bound call	The loop over every capacity becomes one Lower Bound call.

The shorter version

The shorter versionPython

1		import bisect
2
3		def ship_within_days_short(weights, days):
4		def can_ship(capacity):
5		days_needed, load = 1, 0
6		for w in weights:
7		if w > capacity:
8		return False
9		if load + w > capacity:
10		days_needed += 1
11		load = 0
12		load += w
13		return days_needed <= days
14
15		return bisect.bisect_left(range(1, sum(weights) + 1), True, key=can_ship) + 1

Build the check and the range

State the question. "Can the task be done with this value?" It is always a yes-or-no question.
Write the simulation. Usually one pass over the input. It returns True or False.
Show that a larger value cannot hurt. Say why, and draw the row on a tiny input to see it.
Choose the range. lo is the smallest value that could work. hi is one past a value that always works.

Write the check first, and read it on its own, before you read the search.

Second check: Koko Eating Bananas (LC 875)

There are piles of bananas, and Koko eats at a speed of k bananas per hour. Koko eats from one pile per hour at most. We return the smallest speed that finishes all the piles within h hours.

Code / Blueprint

import math
 
def min_eating_speed(piles, h):
    def can_finish(speed):
        hours = 0
        for pile in piles:
            hours += math.ceil(pile / speed)    # whole hours this pile needs
        return hours <= h
 
    lo = 1
    hi = max(piles) + 1                         # one past the biggest pile, which always works
    return binary_search_lower_bound(lo, hi, can_finish)

For piles = [3, 6, 7, 11] and h = 8, the answer is 4. For piles = [30, 11, 23, 4, 20], h = 5 gives 30, and h = 6 gives 23.

	Shipping (LC 1011)	Koko (LC 875)
Can an item be split across periods?	No. A package that does not fit moves whole to the next day.	Yes. A pile that is bigger than the speed continues in the next hour.
Can a period be shared by two items?	Yes. Several packages ride on one day.	No. Koko starts the next pile only in the next hour, so the rest of an hour is unused. With `[1, 1, 1]` at speed 1, each pile takes its own hour.
Does the order of the items matter?	Yes. The check packs in order.	No. The check is a sum.
The check	A running load, reset when it would overflow.	The sum of `ceil(pile / speed)`.

speed

can_finish(speed)

piles = [3, 6, 7] and h = 5: speed 3 needs 1 + 2 + 3 = 6 hours, and speed 4 needs 1 + 2 + 2 = 5 hours.

How does your check count?

Look at how your check counts, and pick one of the four kinds below. All four sit under the same Lower Bound call. Only the check changes.

Kind	How the check counts	Example
Greedy packing in order	A running total, reset on overflow, counts the periods. This is the `can_ship` above.	Capacity To Ship Packages Within D Days (LC 1011), Split Array Largest Sum (LC 410)
A formula per item, summed	Each item adds its own `ceil` or `floor`. The order does not matter.	Koko Eating Bananas (LC 875), Minimum Speed to Arrive on Time (LC 1870)
Greedy count of groups or picks	One scan counts how many groups or picks fit.	Minimum Number of Days to Make m Bouquets (LC 1482)
Reachability under a limit	A search (BFS, DFS or union-find) asks if the goal can be reached when each step may use at most the limit.	Path With Minimum Effort (LC 1631), Swim in Rising Water (LC 778)

A check that asks for the largest value that works belongs to the Upper Bound card.

Skeleton 2: A formula per item, summed

Code / Blueprint

def can_do(x):
    total = 0
    for item in items:
        total += formula(item, x)               # what this item costs (or produces) for the value x
    return total <= budget                      # use >= when the formula counts output that grows with x

Koko Eating Bananas (LC 875) uses formula = math.ceil(pile / speed) and <= h. A second instance counts output. Each bus makes x // time trips in x minutes, and the test is >= total_trips:

Code / Blueprint

def min_time_for_trips(times, total_trips):
    def can_do(x):
        trips = 0
        for time in times:
            trips += x // time                  # whole trips this bus makes in x minutes
        return trips >= total_trips
 
    lo = 1
    hi = min(times) * total_trips + 1           # the fastest bus alone makes every trip in this time
    return binary_search_lower_bound(lo, hi, can_do)

minutes

can_do(x)

times = [1, 2, 3] and total_trips = 5: in 3 minutes the buses make 3 + 1 + 1 = 5 trips.

Skeleton 3: Count groups or picks

Code / Blueprint

def can_do(x):
    groups, run = 0, 0
    for item in items:
        if fits(item, x):
            run += 1
            if run == group_size:
                groups += 1
                run = 0                         # start the next group
        else:
            run = 0                             # a gap breaks the group
    return groups >= needed

Minimum Number of Days to Make m Bouquets (LC 1482) uses fits = bloom_day <= x, group_size = k and needed = m. The answer is -1 when m * k is larger than the number of flowers.

Code / Blueprint

def min_days_for_bouquets(bloom_day, m, k):
    if m * k > len(bloom_day):
        return -1                               # there are not enough flowers
 
    def can_do(x):
        groups, run = 0, 0
        for day in bloom_day:
            if day <= x:
                run += 1
                if run == k:
                    groups += 1
                    run = 0                     # start the next bouquet
            else:
                run = 0                         # a flower that is not ready breaks the bouquet
        return groups >= m
 
    lo = min(bloom_day)
    hi = max(bloom_day) + 1                     # one past the last bloom day, which always works
    return binary_search_lower_bound(lo, hi, can_do)

day

can_do(x)

bloom_day = [1, 10, 3, 10, 2], m = 3, k = 1: on day 3 three flowers are ready.

Skeleton 4: Reachability under a limit

Code / Blueprint

from collections import deque
 
def can_do(limit):
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            return True
        for nxt in neighbors(node):
            if nxt not in seen and step_cost(node, nxt) <= limit:
                seen.add(nxt)
                queue.append(nxt)
    return False

Path With Minimum Effort (LC 1631) uses step_cost as the height difference between two cells.

Code / Blueprint

from collections import deque
 
def minimum_effort_path(heights):
    rows, cols = len(heights), len(heights[0])
 
    def can_do(limit):
        seen = {(0, 0)}
        queue = deque([(0, 0)])
        while queue:
            r, c = queue.popleft()
            if (r, c) == (rows - 1, cols - 1):
                return True
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen:
                    if abs(heights[nr][nc] - heights[r][c]) <= limit:
                        seen.add((nr, nc))
                        queue.append((nr, nc))
        return False
 
    biggest_step = max(max(row) for row in heights) - min(min(row) for row in heights)
    lo = 0
    hi = biggest_step + 1                       # one past the biggest possible step, which always works
    return binary_search_lower_bound(lo, hi, can_do)

limit

can_do(limit)

heights = [[1, 2, 2], [3, 8, 2], [5, 3, 5]]: a path exists when no step is larger than 2.

Two edge cases that need no special case

For Capacity To Ship Packages Within D Days (LC 1011), two edge cases fall out of the search directly, with no extra if:

When days equals len(weights), every package must ship on its own day, so the answer is max(weights).
When days equals 1, the ship must take every package at once, so the answer is sum(weights).

Both values are inside the range from 1 to sum(weights), and can_ship reports them correctly. The search returns them without the caller checking for either case.

Real-world use

Say it in an interview

"The answer is a capacity, not an index, so I write the check can_ship as a simulation. It fills each day in order until the next package would overflow, counts the days, and returns days_needed <= days. A larger capacity never needs more days, so the answers are False and then True, and I run Lower Bound over the capacities from 1 to sum(weights) + 1. The check must return False when a package is heavier than the ship, so the guard w > capacity stays in it. The time is O(N * log S), with N = len(weights) and S = sum(weights). The space is O(1)."

Common Questions

How do I show that the check is monotone?: Show that any plan that works for one value also works for a larger value. For shipping, the same loads fit in a larger ship, so the same number of days is enough. For Koko Eating Bananas (LC 875), a faster speed never needs more hours for a pile.
What is the cost when one check is expensive?: One check costs T, and Lower Bound makes about log R checks, where R is the size of the range. The time is O(T * log R). For shipping, T = O(N) and R = sum(weights), so the time is O(N * log S) with S = sum(weights).

Practice

The classic loop

Old Way

Python

1	from typing import List
2
3	def shipWithinDays(weights: List[int], days: int) -> int:
4	def can_ship(capacity: int) -> bool:
5	needed_days = 1
6	curr_load = 0
7	for w in weights:
8	if curr_load + w > capacity:
9	needed_days += 1
10	curr_load = 0
11	curr_load += w
12	return needed_days <= days
13
14	lo = max(weights) # Minimum possible capacity
15	hi = sum(weights) # Maximum possible capacity
16
17	while lo < hi:
18	mid = lo + (hi - lo) // 2
19	if can_ship(mid):
20	hi = mid # Capacity feasible; attempt smaller capacity
21	else:
22	lo = mid + 1 # Capacity infeasible; must increase
23
24	return lo

From the classic loop to our template

Old Way line	In our template	Why
lo = max(weights)	lo = 1	The check has the guard `w > capacity`, so it returns False for a capacity below the heaviest package. The start can be 1.
hi = sum(weights)	hi = sum(weights) + 1	The template's `hi` is one past the last candidate. The total weight is the last candidate.
while lo < hi: ... if can_ship(mid): hi = mid else: lo = mid + 1	binary_search_lower_bound(lo, hi, can_ship)	The same loop, written once as the template.
if curr_load + w > capacity:	if w > capacity: return False, then if load + w > capacity:	The guard rejects a ship that is smaller than one package.

When the classic form is fine

Use it when an interviewer asks for this form, or when the code base already uses it. It is the same loop. The template only gives the loop a name.

Gotchas of the classic loop

Gotchas1 of 4

The trap
Gotcha 1: Starting lo at 1 instead of max(weights), in this loop
Mistake
```
lo = 1
```
Fix
```
lo = max(weights)
```
What happens: This older loop has no guard w > capacity. Its can_ship never checks that one package fits on a day by itself. With a capacity below the heaviest package, it opens a new day and still loads that package. So can_ship can pass for a capacity that cannot carry the package. Starting at max(weights) keeps every tested capacity large enough for each package.
Example: weights = [1, 10], days = 2
Mistake: returns 1Fix: returns 10
Gotcha 2: Writing needed_days < days instead of needed_days <= days
Mistake
```
return needed_days < days
```
Fix
```
return needed_days <= days
```
What happens: A capacity that ships everything in exactly days days is allowed. needed_days < days rejects that capacity. The search then moves lo above it and returns a larger capacity than needed.
Example: Capacity To Ship Packages Within D Days (LC 1011): weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5
Mistake: returns 17Fix: returns 15
Gotcha 3: Running this loop when the question asks for a maximum
What happens: This loop returns the smallest value that passes the check. Magnetic Force Between Two Balls (LC 1552) asks for the largest distance that still passes. Maximum Candies Allocated to K Children (LC 2226) asks for the largest pile size that still passes. There, small values pass and large values fail. Run the Upper Bound loop on the answer range instead, because it returns the last value that passes.
Gotcha 4: Writing p // k for the hours of one pile
Mistake
```
hours += p // k
```
Fix
```
hours += (p + k - 1) // k
```
What happens: In Koko Eating Bananas (LC 875), a pile of p bananas at speed k takes ceil(p / k) hours. p // k rounds down, so a pile with a remainder gets one hour too few. (p + k - 1) // k rounds up and stays in integers. The check then accepts speeds that are too slow.
Example: piles = [3, 6, 7, 11], k = 4 (total hours)
Mistake: returns 4Fix: returns 8

Earlier signals

The question asks for the smallest (or largest) capacity, speed, time or distance that passes a check, and a bigger value only makes the check easier.

Earlier invariant

Every capacity below lo fails can_ship, and hi always passes it, so the smallest passing capacity is in [lo, hi].

Earlier direction

implicit parameter range [smallest possible answer, largest possible answer] ➔ greedy feasibility predicate ➔ optimal value

Earlier description

Earlier template

Python

1	from typing import Callable, List
2
3	def min_feasible(lo: int, hi: int, is_feasible: Callable[[int], bool]) -> int:
4	"""Feasible Function: the smallest answer in [lo, hi] that passes is_feasible.
5	Precondition: is_feasible is monotonic (False, ..., False, True, ..., True) and hi passes it.
6	This loop finds only the smallest answer that passes. For the largest one, use the loop of the Upper Bound card.
7	R = hi - lo, the size of the answer range. T = the cost of one is_feasible call.
8	Time: O(T * log R) \| Space: O(1)
9	"""
10	while lo < hi:
11	mid = lo + (hi - lo) // 2
12	if is_feasible(mid):
13	hi = mid # mid passes: keep it, try smaller answers
14	else:
15	lo = mid + 1 # mid fails: every answer up to mid fails too
16
17	return lo # lo == hi: the smallest answer that passes
18
19
20	# Capacity To Ship Packages Within D Days (LC 1011): the template above, with is_feasible written as can_ship. One can_ship call costs T = O(N), so O(N * log(sum(weights) - max(weights))) time and O(1) space. The step debugger runs this code.
21	def shipWithinDays(weights: List[int], days: int) -> int:
22	def can_ship(capacity: int) -> bool:
23	needed_days = 1
24	curr_load = 0
25	for w in weights:
26	if curr_load + w > capacity:
27	needed_days += 1
28	curr_load = 0
29	curr_load += w
30	return needed_days <= days
31
32	lo = max(weights) # Minimum possible capacity
33	hi = sum(weights) # Maximum possible capacity
34
35	while lo < hi:
36	mid = lo + (hi - lo) // 2
37	if can_ship(mid):
38	hi = mid # Capacity feasible; attempt smaller capacity
39	else:
40	lo = mid + 1 # Capacity infeasible; must increase
41
42	return lo

Earlier gotchas

Starting lo at 1 instead of max(weights)

Writing needed_days < days instead of needed_days <= days

A capacity that ships everything in exactly days days is allowed. needed_days < days rejects that capacity. The search then moves lo above it and returns a larger capacity than needed.

Running this loop when the question asks for a maximum

Writing p // k for the hours of one pile

Earlier look-alikes

The candidates already exist as positions (versions 1..n) and each check is one call, as in First Bad Version (LC 278): there is no answer range to invent and no plan to simulate.

The question asks for a rank, the k-th smallest value of a large sorted structure, as in Kth Smallest Number in Multiplication Table (LC 668), not the smallest setting that makes a plan work.

Each candidate is tested with one formula and there is no plan to simulate, as in Sqrt(x) (LC 69): the answer is simply the last k whose square still fits in x.

Earlier problems

Capacity To Ship Packages Within D Days

Koko Eating Bananas

Magnetic Force Between Two Balls

Divide Chocolate

Cutting Ribbons

Minimum Number of Days to Make m Bouquets

Minimum Limit of Balls in a Bag

Maximum Candies Allocated to K Children

Split Array Largest Sum

Maximum Number of Removable Characters