Rat in a Maze
A medium Backtracking problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Backtracking
- Sheets
- 3
- Core for
- 0 roles
- Platform
- GeeksforGeeks
The problem
Given an n×n grid (matrix) where 0 represents an open cell and 1 represents a blocked cell, find all possible paths for a rat to travel from the top-left corner (0,0) to the bottom-right corner (n-1,n-1). The rat can move only in the four directions: down, left, right, and up, and cannot visit blocked cells or cells outside the grid.
Example 1
- Input
- n = 3, maze = [[1,0,0],[1,1,0],[1,1,1]]
- Output
- ["DDRR", "DRDR"]
- Why
- Starting at (0,0) which is open (value 1). Path DDRR goes (0,0)->(1,0)->(2,0)->(2,1)->(2,2). Path DRDR goes (0,0)->(1,0)->(1,1)->(2,1)->(2,2). Both reach the destination without entering blocked cells (value 0).
Example 2
- Input
- n = 2, maze = [[1,1],[1,1]]
- Output
- ["DR", "RD"]
- Why
- All cells are open. The rat can go Down then Right, or Right then Down to reach (1,1).
Constraints
- 2 <= n <= 5
- maze[i][j] is 0 or 1
- maze[0][0] == 1 and maze[n-1][n-1] == 1
How to think about it
Updated 2026-09-09Unlike directed acyclic grids where the rat only moves down or right, four-directional movement allows cyclic wandering. Marking the current cell visited before stepping into neighbors and unmarking it upon return prevents infinite looping while allowing the cell to participate in alternative valid paths.
Approaches, worst first
Visited matrix tracking
time O(4^(n^2)) · space O(n^2)
Maintain an n x n boolean visited array. Try moves in alphabetical order ('D', 'L', 'R', 'U'). For each move, verify in-bounds, unblocked, and !visited[r][c]. Mark visited, append direction letter to path, recurse, and unmark on return.
In-place grid mutationWrite this one
time O(4^(n^2)) · space O(n^2)
Instead of a secondary visited array, temporarily flip maze[r][c] to 0 (or a sentinel like -1) while exploring descendants, and restore it to 1 when backtracking. Halves memory overhead and simplifies bounds checking.
Where people lose marks · 3
- Infinite recursion cycles caused by forgetting to unmark visited cells or failing to mark the current cell before branching into all four neighbors.
- Moving in arbitrary direction order instead of alphabetical order ('D', 'L', 'R', 'U') when lexicographical path order is required.
- Not returning empty list immediately if the starting cell or destination cell is blocked.
The theory behind it
Backtracking — the ground this problem stands on. All Backtracking problems
What Backtracking is
Backtracking is an organized trial-and-error search through a maze of possibilities. You make a tentative choice, move forward to explore where that path leads, and if you hit a dead end or finish finding an answer, you back up and undo that choice. By cleaning up your changes before trying the next option, a single shared board or list is explored thoroughly without needing to clone full copies of your data at every turn.
When to reach for it
Reach for backtracking when a problem asks to generate all possible solutions, like all subsets, permutations, valid parentheses combinations, or word search paths on a board. Signals include puzzles with strict constraint rules, like placing eight non-attacking queens on a chessboard or solving a Sudoku grid. Whenever you must construct combinations step by step and abandon dead-end branches early before wasting time exploring impossible paths, use backtracking.
How the pattern works
Follow a three-step rhythm inside a loop: choose, explore, and unchoose. First, check if the current state satisfies your goal; if so, save a copy of it and return. Next, prune illegal moves immediately using constraint checks so unpromising branches are skipped. For each valid candidate, apply the move to your shared path or board, call the recursive function to explore deeper, and finally undo the move right after the call returns. Undoing restores the shared state so sibling choices start from a clean slate.
What each operation costs
| Operation | Time |
|---|---|
| generate all subsets of n elements | O(2^n) |
| generate all permutations of n elements | O(n!) |
| auxiliary recursion stack memory depth | O(n) |
What usually goes wrong with Backtracking
- Adding a mutable path list directly to the final answers collection without creating a shallow copy, leaving every saved result empty once backtracking finishes.
- Forgetting to undo a state change after the recursive call returns, contaminating subsequent branches with leftover moves from earlier paths.
- Generating duplicate subsets or permutations by failing to sort the input array and skip adjacent identical elements during branch selection.
Companies that have asked it
Tags taken from the problem's own GeeksforGeeks page — not a copied list.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Backtracking problems
Problem set and role mapping as of .