All Paths for a Rat in a Maze
Updated
Problem statement
A rat starts at the top-left cell of an n x n maze and wants to reach the bottom-right cell. maze[i][j] is 1 if the cell is open and 0 if it is blocked.
In one move the rat goes one cell down (D), left (L), right (R) or up (U). It never leaves the maze, never enters a blocked cell, and never enters a cell that is already on its current path.
Return every path from the start to the goal as a string of moves, sorted in dictionary order. If the start or the goal is blocked, or no path exists, return an empty list. If n is 1 and the cell is open, the only path is the empty string.
Function
findPaths(maze: int[][]) → List<String>Examples
Example 1
maze = [[1,1,0],[1,1,0],[0,1,1]]return = ["DRDR","RDDR"]From the top-left the rat can go down then right (DR) or right then down (RD) to reach the middle cell, and then D and R to the corner. Sorted: DRDR, RDDR.
Example 2
maze = [[1,0],[0,1]]return = []Both neighbors of the start are blocked, so there is no path and the answer is empty.
Example 3
maze = [[1,0,0],[1,1,0],[0,1,1]]return = ["DRDR"]Only one way through: down, right, down, right, so the answer is ["DRDR"].
Constraints
1 <= n == maze.length == maze[i].length <= 4- Each
maze[i][j]is0or1
More Adobe Phone Screen questions
- Evaluate a Parenthesized Integer ExpressionPHONE SCREEN · Seen Oct 2026
- All Elements of Two BSTs in OrderPHONE SCREEN · Seen Aug 2026
- Rotate an Array In PlaceOA · PHONE SCREEN · Seen Aug 2026
- Binary Tree Level-Order Traversal by LevelsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Count Occurrences in a Sorted ArrayPHONE SCREEN · ONSITE INTERVIEW · Seen Jul 2026
- Count Pairs with Absolute Difference KPHONE SCREEN · Seen Jul 2026
- Count Subsets with Sum KPHONE SCREEN · Seen Jul 2026
- Numbers with Exactly Three DivisorsPHONE SCREEN · Seen Jul 2026
- Sum of Even Nodes on a Path in a Numbered Binary TreePHONE SCREEN · Seen Jul 2026
- Largest Value in Every Sliding WindowPHONE SCREEN · Seen Jul 2026
Similar questions at other companies
- Directional Tiles: Find a Valid Reconfiguration PathDuolingo · PHONE SCREENDuolingo interview questions
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Trace a Word Through a Letter GridExpedia · ONSITE INTERVIEWExpedia interview questions
- Word Search with Eight-Direction AdjacencyMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
- Max Area of Island Without Changing the GridFlexport · PHONE SCREENFlexport interview questions
- SubsetsTemu · PHONE SCREENTemu interview questions
- Delete and Compact a Forest SubtreePinterest · PHONE SCREEN · ONSITE INTERVIEWPinterest interview questions
- PermutationsEPAM · PHONE SCREENEPAM interview questions