Pick the fix
'Given a grid of rooms and walls, find the fewest moves from the entrance to the exit.' Which pattern fits best?
Choose an answer, then open Show answer below to check it.
Show answer
Answer: A BFS on the grid
Right: every move costs the same, so BFS finds the fewest moves.
Equal-cost moves on a grid are the classic cue for breadth-first search, which visits cells in order of distance.
Why not the others?
- B Dynamic programming over cells. Moves can go in any direction, so there is no fixed fill order.
- C Backtracking over all routes. It finds the answer but explores far more than needed.
Text version
Hash map:
- Does any pair in this list add up to the target? (list not sorted): One pass with a set of values seen so far gives O(n).
- Group words that use exactly the same letters: A key built from the letter counts collects each group in one pass.
Two pointers:
- Sorted prices: find two that add up to a budget: Sorted order lets one pointer move in from each end.
- Move all empty slots to the end in place: A write pointer trails a read pointer, O(1) memory.
Sliding window:
- Longest streak of days whose spending stays within a budget: Grow the window, shrink it when the total passes the budget.
- Best total over any k consecutive days: A fixed-size window adds one day and drops one each step.
Binary search:
- Slowest reading pace that still finishes in h hours: 'Finishes in time' flips once as the pace grows, so search the answer.
- Where does a new value go in a sorted list?: Lower-bound search on the sorted list, O(log n).
Heap:
- Keep the k highest scores from a stream: A min-heap of size k drops the smallest each time it overflows.
- Merge many sorted feeds into one: A heap holds the front of each feed, O(N log k).
BFS or DFS:
- Fewest moves between two stations on an unweighted map: BFS reaches nodes in order of distance when every edge counts the same.
- Count the separate land patches on a grid: Each search from an unvisited land cell floods one patch.
Dynamic programming:
- Fewest coins to make an amount: Each amount's best answer reuses smaller amounts' answers.
- Fewest edits to turn one word into another: A table over prefixes of both words, O(m × n).
Backtracking:
- List every order of a small playlist: Every answer must be written out, so choose, explore and undo.
- Place queens on a board so none attack: Try a column per row and undo when a later row has no safe square.