BFS + Binary Search: the Shortest Path When a Threshold, not Distance, Matters
Back with another one in the series where I break down patterns that took me too long to see. This one combines binary search with BFS to solve shortest path problems where the thing you minimize is not the number of steps.
For a while I thought I understood the BFS shortest path algorithm. Unweighted graph, queue, count levels, done. Then a grid problem asked for the path from top left to bottom right that minimizes the largest height jump between adjacent cells. Plain BFS gave the fewest steps, which was useless, because the question cared about a threshold, not step count.
The gap: BFS optimizes the wrong thing
Regular breadth first search (BFS) answers one question well: the minimum number of edges between two nodes in an unweighted graph. That is why BFS is the go to shortest path algorithm for unweighted graphs, which I covered in BFS vs DFS vs DP.
But "Path With Minimum Effort" asks you to minimize the largest single jump. Two paths of equal length can have very different maximum jumps, and BFS only counts levels. The fix was to stop asking BFS to optimize anything and let it answer yes or no instead.
Reframe "minimize the maximum" as a feasibility check
Instead of asking for the smallest possible maximum jump, ask: given a limit T, can I reach the destination if I only step between cells whose height difference is at most T?
That has a clean yes or no answer, and BFS is perfect for it. Do a plain traversal, but only cross an edge if it respects T. Reach the end, the answer is yes. Queue empties first, the answer is no. Each neighboring node only enters the queue when its edge respects the current limit. The optimization problem became a reachability problem with a knob.
The answer is monotonic, so you can search it
If limit T reaches the end, any larger limit also reaches it, because raising the limit only unlocks more edges. If T is too small, every smaller limit fails too. So feasibility flips exactly once as T grows:
T: 0 1 2 3 4 5 6
reachable? N N N Y Y Y YThe answer you want is that flip point: the smallest T that still says yes. A sequence that flips once is the textbook setup for binary search. This is "binary search on answer": you search the space of possible answers, not a sorted array.
Bolt them together
Binary search picks a candidate threshold. BFS checks whether it is feasible. The result tells binary search which half to keep. Reach the end with limit mid, move the right bound down. Fail, move the left bound up. Each guess costs one BFS. That is the whole binary search BFS pattern. This shortest path binary search combination shows up constantly once you learn to spot the monotonic threshold.
Putting it together with real numbers
![Binary search narrows the threshold range [0,7] to [2,2] while BFS checks whether the bottom-right cell of the height grid is reachable, giving answer 2](https://cdn.sanity.io/images/857x5uhs/production/4e23e67d9131d3a783d4b98a79bc2433c100fa92-1280x720.png?w=1600&q=80&fit=max&auto=format)
Take this height grid, starting top left, wanting bottom right:
1 3 5
2 8 3
3 3 5Thresholds run from 0 to 7. Binary search the range [0, 7].
Guess mid = 3: BFS crosses only where the height difference is 3 or less. You can snake down to the end without a jump over 3, so yes. Search [0, 3]. Guess mid = 1: the middle of the grid forces a bigger jump, BFS drains its queue, no. Search [2, 3]. Guess mid = 2: BFS reaches the end again, yes. Search [2, 2]. The bounds meet at 2. The smallest possible value for the largest jump is 2.
The template
from collections import deque
def min_effort(heights):
rows, cols = len(heights), len(heights[0])
def can_reach(limit):
# BFS: is bottom-right reachable if every step's
# height diff is <= limit? A neighboring node only
# gets queued when the edge respects the limit.
seen = [[False] * cols for _ in range(rows)]
q = deque([(0, 0)])
seen[0][0] = True
while q:
r, c = q.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 not seen[nr][nc]:
if abs(heights[nr][nc] - heights[r][c]) <= limit:
seen[nr][nc] = True
q.append((nr, nc))
return False
lo, hi = 0, max(max(row) for row in heights)
while lo < hi:
mid = (lo + hi) // 2
if can_reach(mid):
hi = mid # feasible, try a smaller limit
else:
lo = mid + 1 # infeasible, need a larger limit
return loThe BFS is boring on purpose. The intelligence is in the if that checks the limit and the binary search that narrows the range.
Mistakes I made first
I tried to make BFS carry the cost, pushing the running maximum jump into the queue like a weighted distance. That becomes a buggier Dijkstra and is overkill for a reachability check. Once BFS only answers yes or no, the bugs disappear.
I got the boundary wrong. When can_reach(mid) is true, mid might still be the answer, so set hi = mid, not hi = mid minus 1. Chop off mid and you skip the real answer. This is the classic off-by-one.
I forgot the lower bound could be zero. If the whole path walks across equal cells, the answer is 0, so start the range at 0, not 1.
Why this is fast
Let the grid have N cells and the answer span R threshold values. Each BFS is O(N) in the worst case, and binary search runs O(log R) times, so the total time complexity is O(N log R). That is far better than trying every threshold one at a time.
What to practice next
- Path With Minimum Effort (LeetCode 1631). The exact problem above. Start here.
- Swim in Rising Water (LeetCode 778). Binary search on time, ask if the end is reachable once water rises to level T.
- Path With Maximum Minimum Value (LeetCode 1102). Maximize the minimum cell, so feasibility flips direction.
- Minimize the maximum edge weight to reach a node. Any make the worst edge as small as possible problem is this pattern in disguise.
If the traversal side feels shaky, revisit advanced BFS techniques, and graph traversal on matrix problems shows how one grid hides different patterns.
Frequently asked questions
When should I use BFS with binary search instead of Dijkstra?
Use it when the cost is a maximum or minimum along the path, not a sum of edge weights. For minimum total weight, use Dijkstra. For the best threshold, binary search on answer plus a BFS feasibility check is simpler.
Can I use DFS or union-find instead of BFS?
Yes. The check only asks whether the destination is reachable under a limit, so depth first search dfs works, and union-find works if you process edges in sorted order. BFS is just easiest to get right.
How do I choose the low and high bounds?
Low is the smallest possible answer, often 0. High is the largest value the threshold could need, like the maximum height difference. As long as the true answer sits inside the range and feasibility is monotonic, the search converges.
Why set hi = mid instead of hi = mid minus 1?
Because when mid is feasible, mid itself is still a candidate for the smallest working threshold. This is the standard leftmost true binary search boundary.
Is this the same as binary search on a sorted array?
The mechanics are identical, but you search an imaginary sorted array of yes or no answers rather than stored values. That reframing is what makes finding the shortest path under a threshold click.
Sources and further reading
- LeetCode, Path With Minimum Effort (problem 1631), leetcode.com.
- Wikipedia, Breadth-first search, en.wikipedia.org.
- cp-algorithms, Binary search, cp-algorithms.com.
- Levelop, BFS vs DFS vs DP, three ways to explore a search space, levelop.dev/blog.
I have been working through the graph and search patterns on Levelop, and this cross-pattern problem is the one that made binary search on answer feel natural. The rest of the series lives on the Levelop blog.