Binary Matrix Top-to-Bottom Reachability
Reported by candidates from Google's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Example 3 in this Google OA is the one that trips people: a single-row grid where the top row is also the bottom row, so one open cell is already a win. That's the kind of edge case this question hides. Google reported it in July 2025. It's a grid reachability problem with multiple start cells and any bottom-row open cell as the goal. BFS or DFS solves it cleanly. If you blank on the setup during the live OA, StealthCoder runs invisibly as a safety net and hands you the approach. Know the multi-source trick first and you probably won't need it.
The problem
You are given a rectangular binary matrix grid. A cell with value 0 is open, and a cell with value 1 is blocked. You may start at any open cell in the top row. From an open cell, you may move one cell up, down, left, or right, staying inside the matrix and never entering a blocked cell. Return true if at least one open cell in the bottom row is reachable from an open cell in the top row. Otherwise, return false. Function canReachBottom(grid: int[][]) → boolean Examples Example 1 grid = [[0,1,1],[0,0,1],[1,0,0]] return = true One valid route is (0,0) -> (1,0) -> (1,1) -> (2,1). It reaches an open bottom-row cell. Example 2 grid = [[0,1,0],[1,1,1],[0,0,0]] return = false The blocked middle row separates every open top-row cell from the bottom row. Example 3 grid = [[1,0,1]] return = true The only row is both the top and bottom row. Its open cell is already a valid destination. Constraints 1 <= grid.length <= 500 1 <= grid[i].length <= 500 Every row has the same length. Every cell is either 0 or 1. A move changes the row or column by exactly 1, but not both.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick is multi-source search. Don't run a separate search from each open top-row cell. Push every open top-row cell into one queue at the start, mark them visited, then run a standard BFS in four directions. The moment you pop or push a cell in the last row, return true. If the queue empties, return false. That's O(rows * cols) time and space, fine for 500 x 500. The common pitfalls: forgetting the single-row case, where any open cell in row 0 means true immediately. Marking visited on pop instead of on push, which bloats the queue with duplicates. And using recursive DFS on a 250,000-cell grid, which can overflow the stack. Use an iterative queue. If you freeze on the live OA, StealthCoder can supply the multi-source BFS skeleton so you spend your time on edge cases instead.
If this hits your live OA and you blank, StealthCoder solves it in seconds, invisible to the proctor.
You can drill Binary Matrix Top-to-Bottom Reachability cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Google's OA.
Google reuses patterns across OAs. Built by an Amazon engineer who would have shipped this the night before his JPMorgan OA if he'd had it. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Binary Matrix Top-to-Bottom Reachability FAQ
How hard is this Google OA question really?+
Easy to medium. It's a flood-fill with a twist: many starting cells and a goal row. If you've written BFS on a grid before, it's about 20 lines. The difficulty is in the edge cases, not the algorithm.
What's the trick to solve it fast?+
Seed the queue with every open cell in the top row at once, then run one BFS. Return true as soon as you touch an open cell in the last row. That avoids rerunning searches and keeps it linear in grid size.
BFS or DFS, which should I use?+
Either works for reachability. BFS with an explicit queue is safer because a 500 x 500 grid can make recursive DFS blow the stack in some languages. If you do DFS, write it iteratively with a stack.
What edge cases should I test?+
A single-row grid with an open cell, which returns true. A single-row grid fully blocked, which returns false. A fully blocked top row. A single column. And a blocked middle row like Example 2 that cuts off every path.
How do I prepare for this in 48 hours?+
Write grid BFS from scratch twice, once single-source and once multi-source. Practice direction arrays and bounds checks, and mark visited when you enqueue. Then run all three examples by hand, especially the one-row case.