Jaspreet singh

Posted on Jun 19

Rat in a Maze | Backtracking

#algorithms #coding #computerscience #tutorial

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

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

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

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. 🚀

DEV Community