Shortest Paths & Dijkstra

Uber routes cars over a road network where every street has a travel time, so its graph questions rarely stay unweighted for long. The problems here start like the breadth-first search in the Graphs lesson, then change what a step costs, and sometimes what a node is. In Bus Routes a node is a whole route, and one hop means one more bus. The safest-path grid prices each cell by its distance to the nearest thief before any path search starts. Minimum Path Sum opens as a grid DP and stops being one once the walker can move up or left.

Before you choose a search, say what a single step costs and whether that cost can ever go down along a path. Equal costs mean BFS. Costs of zero or one mean a deque, and any other non-negative cost means Dijkstra with a heap. A negative cost rules Dijkstra out entirely, and that's the turn Minimum Path Sum likes to take.

Matching the search to the cost of a step

Breadth-first search finds the fewest hops because it finishes every state at distance d before it touches distance d + 1. Weights break that. A two-hop route through cheap streets can beat a one-hop route along an expensive one, so the ring order no longer matches the cost order. Dijkstra restores it with a min-heap keyed on cost so far. Each pop is the cheapest state not yet settled, and because no edge is negative, nothing found later can undercut it.

import heapq
def cheapest(start, goal, neighbors):      # neighbors(node) -> [(next, cost)]
    best = {start: 0}
    heap = [(0, start)]
    while heap:
        cost, node = heapq.heappop(heap)
        if node == goal:
            return cost                    # the first pop of the goal is final
        if cost > best[node]:
            continue                       # stale entry: a cheaper one already won
        for nxt, w in neighbors(node):
            c = cost + w
            if c < best.get(nxt, float('inf')):
                best[nxt] = c
                heapq.heappush(heap, (c, nxt))
    return -1                              # goal unreachable

Two lines in that code carry the proof. The stale-entry check skips a heap entry once a cheaper copy of the same node has already been processed, which keeps the run at O(E log V) without a decrease-key operation. Returning early on the goal is safe only because costs never go negative. A bottleneck score, where a path is worth its weakest cell, fits the same code. Flip the heap to a max-heap, replace the sum with a min, and every pop is still final, since a path's minimum can only fall as it grows. When every step costs zero or one, drop the heap for a deque: push zero-cost moves to the front and one-cost moves to the back, and the deque stays sorted by cost on its own.

The Uber angle

Uber's dispatch and ETA work runs on weighted road graphs, and its coding rounds reflect that. A grid question that starts with unit steps often grows costs, a scoring rule or a fourth direction before the hour is up. When that happens, go back to what your search depends on: BFS needs every step to cost the same, and Dijkstra needs costs that never go negative. If the new rule breaks that, say so and switch searches before you edit code, because patching a BFS into a weighted search tends to leave a visited check that fires too early. For the base traversals, the free BFS fundamentals lesson goes slower.

Asked at Uber

Three problems, from equal-cost hops to real weights. Bus Routes keeps BFS but searches over routes instead of stops. The safest path runs a multi-source BFS to price every cell, then a max-heap Dijkstra over those prices. Minimum Path Sum starts on the familiar DP and finishes on Dijkstra, with a 0-1 deque in the follow-up. Code each one in the editor and name its search before you open the walkthrough.

1

Bus Routes: BFS Over Routes

HardFrequently asked

Problem

You're given an array routes where routes[i] lists the stops bus i visits, looping through them forever. You begin at stop source on foot and want to reach stop target riding only buses. A transfer happens when you step off one bus at a stop and board another route that also serves it. Return the fewest buses you must board to get from source to target, or -1 if no sequence of buses gets you there.

If source equals target you are already there, so the answer is 0 even when no route serves that stop. The stops within one route are distinct, and two routes may share any number of stops.

Input encoding. Each test case is a JSON array of three arguments: routes (a list of integer lists, which may have different lengths), then source and target as integers. For example: [[[1,2,7],[3,6,7]], 1, 6].

Inputroutes = [[1,2,7],[3,6,7]]source = 1target = 6Output2

Board bus 0 at stop 1, ride to stop 7, transfer to bus 1, and ride to stop 6. That is two buses boarded.

Inputroutes = [[1,2,3,4,5,6],[1,7],[7,6]]source = 1target = 6Output1

Bus 0 reaches stop 6 directly after five stops. The route through stop 7 covers fewer stops but needs two buses, so the answer is 1.

How this uses the pattern

Breadth-first search where each node is a whole route. A map from every stop to the routes that serve it supplies the neighbors, so one BFS level equals one more bus boarded and the first route that touches the target gives the answer.

Bus Routes: BFS Over Routes

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (8)

Need a hint? (3 available)

The Uber angle

Bus Routes is the transfers question among Uber's graph problems, a city transit map on top of a breadth-first search. It comes up as a straight phone screen and as an onsite round, L4 interviews included, and passing every test isn't always enough: an onsite can still mark a correct solution as not optimal. The likely slow part is building a route-to-route graph by comparing every pair of routes before the search starts. Index each stop to its routes once, then let BFS search routes through that map. Say out loud that the answer counts buses boarded and that source equal to target costs zero.

Take it further

Return the boarding plan, the route indices to ride in order, alongside the count. The search doesn't change. For each route you enqueue, record the route you transferred from, and that parent map doubles as the visited-route set. When a scanned route reaches the target, walk the parents back to the first bus and reverse the list. A verbal part 3 might ask about many source and target pairs on one network, where the stop index is built once and reused. The walkthrough codes the plan.

Show solution & walkthrough

2

Find the Safest Path in a Grid: Multi-Source BFS That Turns Into Dijkstra

HardFrequently asked

Problem

You're given an n x n grid where each cell is 0 (empty) or 1 (a thief). You start at (0, 0) and want to reach (n - 1, n - 1), moving up, down, left, or right one cell at a time. Any cell may be stepped on, thieves included.

A cell's safeness is its Manhattan distance to the nearest thief, |r1 - r2| + |c1 - c2|. A path's safeness factor is the smallest safeness of any cell on it, both endpoints included. Return the largest safeness factor over all paths from (0, 0) to (n - 1, n - 1).

The grid always holds at least one thief, and 1 <= n <= 400.

Input encoding. The grid arrives as a JSON array of rows, each cell the number 0 or 1. For example: [[0,0,1],[0,0,0],[0,0,0]].

Inputgrid = [[1,0,0],[0,0,0],[0,0,1]]Output0

Thieves sit on both the start and the finish, so every path touches a cell at distance 0.

Inputgrid = [[0,0,1],[0,0,0],[0,0,0]]Output2

Down the left column and along the bottom row visits safeness 2, 3, 4, 3, 2, so the weakest cell scores 2. The start itself scores 2, so no route beats it.

How this uses the pattern

Two passes. A multi-source BFS seeded with every thief gives each cell its safeness, because the first wave to reach a cell came from its nearest thief. Then run Dijkstra with a max-heap where a path scores the minimum safeness along it; the first time the far corner leaves the heap, its score is final.

Find the Safest Path in a Grid: Multi-Source BFS That Turns Into Dijkstra

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (7)

Need a hint? (3 available)

The Uber angle

Find the Safest Path is one of the most-reported graph problems in Uber interviews, and it has been framed as a thief slipping past police patrols to reach a bank. It tends to grow in stages, something like the safeness grid first, then a route that keeps its worst cell as safe as possible, then a patrol radius that differs per station. The usual mistake is a separate BFS from each thief, the per-source approach that gets marked non-optimal on Uber's closest-driver variant. Seed every thief into one queue, then explain why a max-heap stays correct when a path's score is its minimum cell.

Take it further

Now each police station patrols its own radius k, and you report whether the thief can reach the bank without entering a watched cell. One shared BFS breaks here, since a short-radius station can claim a cell first and stop a wider patrol from passing through it. Seed a max-heap with every station at its radius, spread outward losing one per step, and keep the largest leftover radius per cell. The coverage pass becomes Dijkstra, and a plain BFS over unwatched cells answers the question. The walkthrough runs both passes.

Show solution & walkthrough

3

Minimum Path Sum: From Grid DP to Dijkstra

MediumSometimes asked

Problem

You're given an m x n grid of non-negative integers. Read it as a city map where each value is the cost of driving into that block. Start at the top-left cell (0, 0) and finish at the bottom-right cell (m-1, n-1). From any cell you may move up, down, left, or right to a neighbor. A route's cost is the sum of every cell it enters, counting the start. Return the minimum route cost. An empty grid returns 0.

The classic version allows only moves right and down. This one lifts that limit, and the row-by-row DP stops being correct.

Input encoding. Each test case is a JSON array of rows of integers, for example [[1,3,1],[1,5,1],[4,2,1]]. The empty grid is [].

Inputgrid = [[1,3,1],[1,5,1],[4,2,1]]Output7

Right, right, down, down: 1 + 3 + 1 + 1 + 1 = 7. On this grid the right-and-down route is already the cheapest.

Inputgrid = [[1,9,1,1,1],[1,1,1,9,1],[1,1,2,9,1],[9,2,1,9,1]]Output10

Down, right, right, up to the top row, across it and down the last column. All ten blocks on that route cost 1. Every right-and-down route hits a 9, so the classic DP returns 16.

How this uses the pattern

Use Dijkstra on a grid. Each block is a node, each move is an edge weighted by the block you enter, and a min-heap keyed on cost so far hands you the cheapest block reached next. The first time the bottom-right block comes off the heap, its cost is final.

Minimum Path Sum: From Grid DP to Dijkstra

Python

Focus Mode

Loading...

OutputSubmissions

Run

Submit

Click "Run" to execute your code

Show test cases (7)

Need a hint? (3 available)

The Uber angle

Minimum Path Sum is a mid-frequency Uber screen question, and Uber rarely leaves a medium as written. An L4 phone screen can start on the right-and-down DP, then lift two limits at once, something like negative values plus moves in all four directions. Separate those before you code. Four-way movement breaks the table, because a block's cheapest route can now arrive from below or from the right, and with non-negative costs that means Dijkstra. Negative values leave the right-and-down DP correct and break Dijkstra instead. Put both together and any two neighbors summing below zero make the minimum unbounded, so ask whether a route may revisit a block.

Take it further

Each block now holds an arrow (U, D, L or R); moving the way it points costs 0 and any other move costs 1. Find the cheapest trip from corner to corner. A senior Uber screen has used this shape, which is LeetCode 1368. With only two edge weights the heap is more than you need. A deque does the same job in O(m·n): zero-cost moves go to the front, one-cost moves to the back. The walkthrough covers it, plus what negative values do to each version.

Show solution & walkthrough