Rat in a Maze: All Simple Paths
Updated
Problem statement
A rat starts at the top-left cell of a square binary matrix maze and wants to reach the bottom-right cell. A value of 1 means open and 0 means blocked. It may move down, left, right or up between adjacent open cells.
Return every path that never visits a cell twice. Encode moves using D, L, R and U, and sort the path strings in alphabetical order. Return an empty array if either endpoint is blocked or no path exists.
For this exercise, assume a one-cell open maze has one path, represented by the empty string. Do not change the input matrix.
Function
mazePaths(maze: int[][]) → String[]Examples
Example 1
maze = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]return = ["DDRDRR","DRDDRR"]Exactly two simple paths reach the destination. They are listed in lexicographic order.
Example 2
maze = [[1,0],[0,1]]return = []The open endpoints are separated by blocked cells.
Constraints
- For this exercise, assume the square side length is from 1 through 5.
- Every cell is 0 or 1.
- A path may revisit a cell used by another path, but may not repeat a cell within itself.
- For this exercise, assume at most 500 valid simple paths reach the destination.
More PeopleStrong interview questions
- Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
- Unique Paths Through a GridOA · Seen Mar 2026
- Aggressive CowsOA · Seen Oct 2021
- Shortest Path in an Unweighted GraphOA · Seen Oct 2021
- Total Set Bits from 1 to NOA · Seen Oct 2021
- Swap Two Array ElementsOA · Seen Sep 2021
- Minimum Travel Time with Flashing Traffic LightsOA · Seen Aug 2021
- Permutation in a StringOA · Seen Aug 2021
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
Similar questions at other companies
- Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Find a Word Path Moving Right or DownIntuit · OAIntuit interview questions
- Cave AdvantureMeta · OAMeta interview questions
- Word SearchAmazon · ONSITE INTERVIEW
- Word SearchMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Word SearchCognitiv · PHONE SCREEN
- Find a Word in a Letter GridAdobe · PHONE SCREENAdobe interview questions
- Word SearchWhatNot · PHONE SCREENWhatNot interview questions
- Trace a Word Through a Letter GridExpedia · ONSITE INTERVIEWExpedia interview questions