What is the brute force approach and complexity for Rat in a Maze?

Each call gets its own copy of the visited grid; sort the answers at the end with time complexity O(n² · 3^(n²)) and space complexity O(n⁴).

What is the optimal approach and complexity for Rat in a Maze?

One grid for the whole search: mark a cell on entry, unmark it on exit; try D, L, R, U with optimal time complexity O(3^(n²) + A · n²) and space complexity O(n²).

How do you identify the pattern for Rat in a Maze?

Look for key signals in the prompt: "from the top-left to the bottom-right" indicates A route from one cell to another in a grid. Each step is one move to a neighbouring cell.; "return every route" indicates We need every choice explored, not a yes or no. Each finished route is one answer.; "cannot step on a cell twice" indicates The rule is about one route. Many routes can use the same cell, one after another.; "in alphabetical order" indicates The routes are strings of letters. The order the moves are tried decides the order of the answers..

Rat in a Maze

Medium·GeeksforGeeksBasic Anchor

GeeksforGeeks

Jump:

30-Second Mental ModelBacktracking → Grid / path search (DFS with mark and unmark)

Complexity:O(n² · 3^(n²))→O(3^(n²) + A · n²)

Key Insight

Keep one grid for the whole search. When the rat enters a cell, mark it. When every move from that cell has been tried, unmark it on the way out. The marks then always show exactly the current route. Trying the moves in the order D, L, R, U makes the routes come out sorted.

Core Validity Invariant

At every call, a cell is marked exactly when the current route stands on it. Marks are added on the way in and removed on the way out, so the grid always matches the route.

Problem

A rat starts in the top-left cell of an n × n maze. It wants to reach the bottom-right cell.

Each cell is either open (1) or a wall (0). The rat moves one cell at a time: D (down), L (left), R (right) or U (up). It can only step on open cells, and it may not step on the same cell twice in one route.

Return every route as a string of move letters, in alphabetical order. If there is no route, return an empty list. A wall at the start or at the end means there is no route.

In the examples, (row, col) counts rows and columns from 0, starting at the top-left.

Input

maze, an n × n grid of 0s and 1s. The cell in row r and column c is maze[r][c].

Output

A list of strings. Each string is one route, written as its moves. The list is in alphabetical order. The list is empty if there is no route.

Example 1

Input: maze = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]

Output: ["DDRDRR", "DRDDRR"]

There are two routes. Both pass through (2,1), (3,1) and (3,2). DDRDRR goes through (2,0), and DRDDRR goes through (1,1) instead.

Example 2

Input: maze = [[1, 0], [0, 1]]

Output: []

Both first moves, D and R, lead into a wall, so the rat is stuck at the start.

Example 3

Input: maze = [[1, 1], [1, 1]]

Output: ["DR", "RD"]

Every cell is open. The rat can go down then right, or right then down.

Constraints

• The maze is n × n, with n at least 2.
• Each cell is 0 (wall) or 1 (open).

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
The rule says a route may not step on the same cell twice. Is that a rule about one route, or about the whole search?
2.
After one route fails, which cells should the rat be able to use again for the next route?
3.
Two routes can pass through the same cell. If that cell stays blocked after the first visit, what happens to the second route?
4.
In which order should the four moves be tried so the routes come out alphabetically, without a sort?
5.
Can a route walk past the end cell and come back to it?

Brute force approach

Idea

Pass the visited grid by value, so every call gets its own copy. A call marks its cell in its copy, and each child gets a fresh copy of that. Nothing has to be undone, but the answers come out in the wrong order, so they must be sorted at the end.

Thinking process

1
A route may not step on a cell twice, so the search needs to know which cells the route has used. The simplest way is a grid of true/false values, one for each cell.
2
Pass that grid down to each call. On the 4 × 4 example, the call at (0,0) marks only (0,0). Moving down gives the child a copy where (0,0) and (1,0) are both marked.
3
Every call copies all 16 cells, even though a child differs from its parent by one marked cell.
4
The moves are tried in the order U, R, D, L. The first route found is DRDDRR, then DDRDRR. Sorting gives DDRDRR, DRDDRR.

Visual

Each call gets its own copy of the grid (16 cells), so the copies are the repeated work. Moves are tried in the order U, R, D, L, so the answers are found out of order and must be sorted at the end.

Brute force copies the grid for every callmaze = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]step 1/15

▲rat

moves

Work

calls so far: 1
grid cells copied so far: 16
routes found (raw order): 0

Routes found (raw order)

none yet

Copy the grid (16 cells), mark (0,0)

Start at (0,0). The copy of the grid is made for this call. Brute force pays for 16 cells every call, even though only one cell changed.

Code & Implementation

brute.cpp

class Solution {
    // `seen` is passed BY VALUE: every call gets its own full copy of the visited grid.
    void go(vector<vector<int>>& maze, int n, int r, int c, string& path,
            vector<vector<bool>> seen, vector<string>& out) {
        seen[r][c] = true;
        if (r == n - 1 && c == n - 1) {          // reached the end: record the route
            out.push_back(path);
            return;
        }
        // Moves are tried in the order U, R, D, L. That is not alphabetical order,
        // so the answers must be sorted at the end.
        const int dr[] = {-1, 0, 1, 0};
        const int dc[] = {0, 1, 0, -1};
        const char mv[] = {'U', 'R', 'D', 'L'};
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
            if (maze[nr][nc] == 0 || seen[nr][nc]) continue;
            path.push_back(mv[d]);
            go(maze, n, nr, nc, path, seen, out);   // a full copy of `seen` goes down
            path.pop_back();
        }
    }

public:
    vector<string> ratInMaze(vector<vector<int>>& maze) {
        int n = maze.size();
        vector<string> out;
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return out;   // a wall at either end
        string path;
        go(maze, n, 0, 0, path, vector<vector<bool>>(n, vector<bool>(n, false)), out);
        sort(out.begin(), out.end());
        return out;
    }
};

Complexity

Time O(n² · 3^(n²))Space O(n⁴)

A call has at most three unvisited neighbours (its parent is already on the route), so there are at most 3^(n²) calls. Each call pays n² to copy the grid. The optimal makes the same calls and pays only a constant amount for each one. The space is one n × n copy of the grid per level of the call stack. The output list is not counted in the space.

Optimized approach

Idea

Start from brute force

Brute force gives every call a fresh copy of the grid, so nothing has to be undone. But a copy is only a way to avoid undoing one mark.

Find the repeated work

Each call copies all n² cells, even though the child differs from its parent in one cell. Almost all of that copying repeats what the parent already had.

Define the state — what variables do I need?

seen: One n × n grid. A cell is true exactly when the current route is standing on it.
path: The moves made so far. Push a letter when moving into a cell, and pop it when coming back.
r, c: The cell the rat is standing on in this call.
out: The finished routes. A route is copied the moment the end cell is reached.

Define validity

At every call, a cell is marked exactly when the current route stands on it. Marks are added on the way in and removed on the way out, so the grid always matches the route.

Define the transitions — when does each pointer move, and why is it safe?

Enter an open cell (r, c)

seen[r][c] = true

The route now stands here, so no later move on this route may come back to it.

Try a move to an open, unmarked neighbour

path.push_back(move); go(...); path.pop_back();

The move belongs to the route only while the child call runs. Popping it puts the route back to the state the caller expects.

All moves from (r, c) are tried

seen[r][c] = false

The route no longer stands here. A later route may pass through (r, c), and it must find the cell open.

Reach (n − 1, n − 1)

out.push_back(path); return

The route is complete. The end cell is never marked, and the call stops there, because a route ends at the end cell.

Before the search starts

Return an empty list if maze[0][0] or maze[n − 1][n − 1] is 0

A wall at either end means that no route can exist.

What does the current window add to the answer?

Each call that reaches the end cell adds one copy of path to the answers. A dead end adds nothing.

Code & Implementation

optimal.cpp

class Solution {
    vector<vector<bool>> seen;   // ONE grid shared by every call: true = on the current route
    string path;                 // the moves made so far
    vector<string> out;          // finished routes, in the order they are found

    void go(vector<vector<int>>& maze, int n, int r, int c) {
        // The end cell is never marked: a route stops there, so nothing goes on past it.
        if (r == n - 1 && c == n - 1) {
            out.push_back(path);
            return;
        }
        // Moves are tried in the order D, L, R, U. Those letters are in alphabetical
        // order, so the answers come out already sorted.
        const int dr[] = {1, 0, 0, -1};
        const int dc[] = {0, -1, 1, 0};
        const char mv[] = {'D', 'L', 'R', 'U'};
        seen[r][c] = true;                       // mark on the way in
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
            if (maze[nr][nc] == 0 || seen[nr][nc]) continue;
            path.push_back(mv[d]);
            go(maze, n, nr, nc);
            path.pop_back();                     // undo the move
        }
        seen[r][c] = false;                      // unmark on the way out, so other routes can use it
    }

public:
    vector<string> ratInMaze(vector<vector<int>>& maze) {
        int n = maze.size();
        out.clear();
        path.clear();
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return out;   // a wall at either end
        seen.assign(n, vector<bool>(n, false));
        go(maze, n, 0, 0);
        return out;
    }
};

Complexity

Time O(3^(n²) + A · n²)Space O(n²)

The search makes the same at most 3^(n²) calls as brute force. Each call does a constant amount of work, plus O(n²) to copy a finished route. Only one grid is ever used. A is the number of routes. O(n²) is the shared grid and the moves. The output list is not counted in the space.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Each call gets its own copy of the visited grid; sort the answers at the end	O(n² · 3^(n²))	O(n⁴)
Optimal	One grid for the whole search: mark a cell on entry, unmark it on exit; try D, L, R, U	O(3^(n²) + A · n²)	O(n²)

Why does this belong to this pattern?

Clues in the problem statement

“from the top-left to the bottom-right”A route from one cell to another in a grid. Each step is one move to a neighbouring cell.
“return every route”We need every choice explored, not a yes or no. Each finished route is one answer.
“cannot step on a cell twice”The rule is about one route. Many routes can use the same cell, one after another.
“in alphabetical order”The routes are strings of letters. The order the moves are tried decides the order of the answers.

Grid cell to cell+all routes+mark on entry, unmark on exit+fixed move order→Backtracking → Grid / path search (DFS with mark and unmark)

The mark belongs to the route, not to the search. Mark the cell on the way in, and unmark it on the way out, so each route sees exactly the cells it has used. This differs from the graph-traversal habit of one permanent visited set, which hides every route that shares a cell. Word Search uses the same mark and unmark on a letter board, but it stops at the first match.

Don't make this mistake

Pattern confusion: a permanent visited set from graph traversal

✗ seen[r][c] = true; // marked on the way in, and never cleared

✓ seen[r][c] = true; // ... moves ... seen[r][c] = false; // unmarked on the way out

In graph traversal a visited node is never visited again. Here a cell can be used by many routes. Trace the example: the first route DDRDRR marks (2,1), (3,1) and (3,2). The search also goes up to (1,1), finds a dead end, and never clears (1,1). When it returns to (1,0) and tries R, the cell (1,1) is still marked, so the second route DRDDRR is lost. The output is only ["DDRDRR"].

Trusting the order the moves were tried in

✗ const char mv[] = {'U', 'R', 'D', 'L'}; // and return the answers without sorting

✓ const char mv[] = {'D', 'L', 'R', 'U'}; // alphabetical order, so no sort is needed

Trying U, R, D, L first finds DRDDRR before DDRDRR. If the answers are returned as they are, the output is ["DRDDRR", "DDRDRR"], which is the wrong order. The routes only come out sorted when the moves are tried in alphabetical order, or when the answers are sorted.

Forgetting to check the start and end cells

✗ // no check: the search starts at (0,0) even when it is a wall

✓ if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) return {};

On the maze [[0, 1], [1, 1]] the start is a wall. The search would still enter (0,0), move D to (1,0), then R to (1,1), and return ["DR"]. The correct answer is an empty list, because the rat cannot start in a wall.

Want to implement this?

Write it yourself on GeeksforGeeks, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Backtracking translate into production architectures and low-level memory mechanics.

LLD Architecture