Day X - Rat in a Maze | Backtracking
Problem Statement
A rat starts at:
(0,0)
and wants to reach:
(n-1,n-1)
The rat can move:
D → Down
L → Left
R → Right
U → Up
Cells containing:
1 → Open
0 → Blocked
Return all possible paths.
Brute Force Intuition
From every cell:
Try all four directions
Keep moving until:
Destination reached
or
Invalid path
Without tracking visited cells, infinite loops can occur.
Moving Towards the Optimal Approach
For every cell:
Mark Visited
Explore All Directions
Unmark Visited
This prevents revisiting the same cell in the current path.
Pattern Recognition
Whenever you see:
- Grid traversal
- Find all paths
- Obstacles present
Think:
Backtracking + DFS
Key Observation
From one cell:
D
L
R
U
Each move creates a new branch.
Only valid cells are explored.
Optimal Java Solution
class Solution {
public ArrayList<String> ratInMaze(int[][] maze) {
ArrayList<String> ans = new ArrayList<>();
int n = maze.length;
if (maze[0][0] == 0)
return ans;
boolean[][] visited = new boolean[n][n];
solve(0, 0, maze, visited, "", ans);
return ans;
}
private void solve(int row,
int col,
int[][] maze,
boolean[][] visited,
String path,
ArrayList<String> ans) {
int n = maze.length;
if (row == n - 1 && col == n - 1) {
ans.add(path);
return;
}
visited[row][col] = true;
if (isSafe(row + 1, col, maze, visited))
solve(row + 1, col, maze, visited, path + "D", ans);
if (isSafe(row, col - 1, maze, visited))
solve(row, col - 1, maze, visited, path + "L", ans);
if (isSafe(row, col + 1, maze, visited))
solve(row, col + 1, maze, visited, path + "R", ans);
if (isSafe(row - 1, col, maze, visited))
solve(row - 1, col, maze, visited, path + "U", ans);
visited[row][col] = false;
}
private boolean isSafe(int row,
int col,
int[][] maze,
boolean[][] visited) {
int n = maze.length;
return row >= 0 &&
col >= 0 &&
row < n &&
col < n &&
maze[row][col] == 1 &&
!visited[row][col];
}
}
Dry Run
Input
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
Start:
(0,0)
Possible path:
Down
Down
Right
Down
Right
Right
Result:
DDRDRR
Why Backtracking Works?
At every cell:
Explore all valid directions
After exploring:
Undo visited mark
so other paths can reuse the cell.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(4^(N²)) |
| Space Complexity | O(N²) |
Interview One-Liner
Perform DFS from the source cell, exploring all four directions while maintaining a visited matrix to avoid cycles.
Pattern Learned
Find All Paths
+
Grid
+
Obstacles
=> DFS + Backtracking
Similar Problems
- Rat in a Maze
- Word Search
- Number of Islands
- Flood Fill
- Maze Problems
- Path Finding
Memory Trick
Current Cell
↓
Try D L R U
↓
Valid ?
↓
Move
↓
Backtrack
Backtracking Cheat Sheet
Subsets
→ Pick / Not Pick
Combination Sum
→ Target Based
Palindrome Partitioning
→ Try Every Cut
Permutations
→ Try Every Unused Element
N Queens
→ Try Every Safe Position
Sudoku
→ Try Every Valid Digit
Graph Coloring
→ Try Every Valid Color
Rat In Maze
→ Try Every Valid Direction
These are the core Striver Backtracking patterns that appear repeatedly in interviews. 🚀