Enumerate Top-to-Bottom Grid Paths
Updated
Problem statement
You are given a rectangular binary matrix grid. A cell with value 0 is open, and a cell with value 1 is blocked.
A path may start at any open cell in the top row. At each step, it may move one cell down, right, left, or up, staying inside the matrix and entering only open cells. A path is simple: it may not visit the same cell more than once. The path ends immediately when it first reaches the bottom row.
Return every distinct valid path. Represent a cell as [row, column] and a path as its ordered list of cells.
Return the paths in the order a depth-first search finds them:
- Consider top-row starting cells from left to right.
- From each cell, try neighbors in the order down, right, left, then up.
Function
enumerateTopToBottomPaths(grid: int[][]) → int[][][]Examples
Example 1
grid = [[0,0],[0,0]]return = [[[0,0],[1,0]],[[0,0],[0,1],[1,1]],[[0,1],[1,1]],[[0,1],[0,0],[1,0]]]Both top-row cells are valid starts. Depth-first search uses down, right, left, then up, and stops each path as soon as it reaches row 1.
Example 2
grid = [[0,1],[1,1]]return = []The only open top-row cell has no open route to the bottom row, so there are no valid paths.
Example 3
grid = [[0,1,0]]return = [[[0,0]],[[0,2]]]In a one-row matrix, every open top-row cell is already in the bottom row. Starts are returned from left to right.
Constraints
1 <= grid.length <= 61 <= grid[i].length <= 6- Every row has the same length.
- Every cell is either
0or1. - There are at most
16open cells. - The input has at most
10000valid paths. - A path may not repeat a cell and ends on its first bottom-row cell.
More Google Onsite Interview questions
- Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
- Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Filesystem Entity Total SizeONSITE INTERVIEW · Seen Nov 2026
- Longest Subarray Within an Absolute-Difference LimitONSITE INTERVIEW · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Word Search IIAmazon · ONSITE INTERVIEW
- Longest Decreasing Matrix Path with Limited RelaxationsDuolingo · ONSITE INTERVIEWDuolingo interview questions
- Making a Large IslandMeta · ONSITE INTERVIEWMeta interview questions
- Four-Direction Unique Grid PathsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Park Train Cars by PreferenceMercor · ONSITE INTERVIEWMercor interview questions
- Word SearchMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Number of IslandsTripjack · ONSITE INTERVIEWTripjack interview questions
- Number of IslandsTekion · ONSITE INTERVIEWTekion interview questions
Google interview experiences
- Google L4 SWE Phone Screen: 1 Experience
- Google ML Engineering Manager Onsite: 1 Experience
- Google Experienced SWE First Round and Onsite: 1 Experience
- Google AI Coding Interview and AI OA: 2 Experiences
- Google SWE Intern Interview Results Timeline: 13 Experiences
- Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience