Rat in a Maze | Backtracking

Day X – Rat in a Maze | Backtracking

Problem Statement

A rat starts at:

(0,0)

Enter fullscreen mode Exit fullscreen mode

and wants to reach:

(n-1,n-1)

Enter fullscreen mode Exit fullscreen mode

The rat can move:

D → Down
L → Left
R → Right
U → Up

Enter fullscreen mode Exit fullscreen mode

Cells containing:

1 → Open
0 → Blocked

Enter fullscreen mode Exit fullscreen mode

Return all possible paths.

Brute Force Intuition

From every cell:

Try all four directions

Enter fullscreen mode Exit fullscreen mode

Keep moving until:

Destination reached

Enter fullscreen mode Exit fullscreen mode

or

Invalid path

Enter fullscreen mode Exit fullscreen mode

Without tracking visited cells, infinite loops can occur.

Moving Towards the Optimal Approach

For every cell:

Mark Visited
Explore All Directions
Unmark Visited

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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];
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1

Enter fullscreen mode Exit fullscreen mode

Start:

(0,0)

Enter fullscreen mode Exit fullscreen mode

Possible path:

Down
Down
Right
Down
Right
Right

Enter fullscreen mode Exit fullscreen mode

Result:

DDRDRR

Enter fullscreen mode Exit fullscreen mode

Why Backtracking Works?

At every cell:

Explore all valid directions

Enter fullscreen mode Exit fullscreen mode

After exploring:

Undo visited mark

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

These are the core Striver Backtracking patterns that appear repeatedly in interviews. 🚀