Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rat in a Maze

HARDProblemSolveExternal Links

Description

You are given a square binary matrix of size n × n that represents a maze. A rat is placed at the top-left corner, cell (0, 0), and needs to reach the bottom-right corner, cell (n−1, n−1).

Each cell in the matrix contains either a 1 or a 0:

  • 1 means the cell is open — the rat can step on it.
  • 0 means the cell is blocked — the rat cannot pass through it.

The rat can move in four directions from any open cell:

  • D (Down) — move one row down
  • L (Left) — move one column left
  • R (Right) — move one column right
  • U (Up) — move one row up

The rat cannot visit the same cell more than once within a single path.

Your task is to find all possible paths from (0, 0) to (n−1, n−1). Return the paths as a list of strings where each string is a sequence of direction characters. If multiple paths exist, return them in lexicographically sorted order. If no path exists (including when the start or end cell is blocked), return an empty list.

4×4 maze grid with open cells (1) in green and blocked cells (0) in gray, showing Start at (0,0) and End at (3,3)
4×4 maze grid with open cells (1) in green and blocked cells (0) in gray, showing Start at (0,0) and End at (3,3)

Examples

Example 1

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

Output: ["DDRDRR", "DRDDRR"]

Explanation: There are exactly two paths from (0,0) to (3,3) that only pass through open cells without revisiting any cell:

  • DDRDRR: (0,0) → D → (1,0) → D → (2,0) → R → (2,1) → D → (3,1) → R → (3,2) → R → (3,3)
  • DRDDRR: (0,0) → D → (1,0) → R → (1,1) → D → (2,1) → D → (3,1) → R → (3,2) → R → (3,3)

Both paths are returned in lexicographic order.

Example 2

Input: mat = [[1, 1], [1, 1]]

Output: ["DR", "RD"]

Explanation: In a 2×2 grid where every cell is open, two paths exist:

  • DR: (0,0) → Down → (1,0) → Right → (1,1)
  • RD: (0,0) → Right → (0,1) → Down → (1,1)

Both reach the destination through different routes.

Example 3

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

Output: []

Explanation: The starting cell (0,0) has value 0, meaning it is blocked. The rat cannot even begin its journey, so no path exists. An empty list is returned.

Constraints

  • 2 ≤ n ≤ 5
  • 0 ≤ mat[i][j] ≤ 1
  • The matrix is always square (n × n)

Editorial

Brute Force

Intuition

When faced with a maze, the most natural instinct is to try every possible route. Imagine you are standing at the entrance of a real maze. You pick a direction, walk until you hit a wall or a dead end, then go back and try a different turn.

That is exactly what a recursive approach does. Starting from (0, 0), we attempt to move in each of the four directions. If a move leads to a valid, unvisited cell, we continue exploring from that new cell. When we reach the destination (n−1, n−1), we record the path. If we reach a dead end — all four neighbors are either blocked, out of bounds, or already visited — we return to the previous cell and try the next direction.

To keep track of which cells the rat has already stepped on during the current path, we use a separate boolean matrix called visited. Before entering a cell, we mark it as visited. After finishing all explorations from that cell, we unmark it so that other paths can use it.

Since we try directions in an arbitrary order (Down, Right, Up, Left), the paths we collect may not be in lexicographic order. We sort the result at the end to satisfy the requirement.

Step-by-Step Explanation

Let us trace through Example 1: mat = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]].

We use a separate visited[][] matrix (all false initially). Directions are tried in order: D, R, U, L.

Step 1: Mark visited[0][0] = true. Call solve(0, 0, path="").

  • visited state: {(0,0)}

Step 2: At (0,0). Try D → (1,0): maze[1][0]=1, not visited → valid. Mark visited[1][0]=true. Call solve(1, 0, path="D").

  • visited state: {(0,0), (1,0)}

Step 3: At (1,0). Try D → (2,0): maze[2][0]=1, not visited → valid. Mark visited[2][0]=true. Call solve(2, 0, path="DD").

  • visited state: {(0,0), (1,0), (2,0)}

Step 4: At (2,0). Try D → (3,0): maze[3][0]=0 → blocked. Try R → (2,1): maze[2][1]=1, not visited → valid. Mark visited[2][1]=true. Call solve(2, 1, path="DDR").

  • visited state: {(0,0), (1,0), (2,0), (2,1)}

Step 5: At (2,1). Try D → (3,1): maze[3][1]=1, not visited → valid. Mark visited[3][1]=true. Call solve(3, 1, path="DDRD").

  • visited state: {(0,0), (1,0), (2,0), (2,1), (3,1)}

Step 6: At (3,1). Try D → (4,1): out of bounds. Try R → (3,2): maze[3][2]=1, not visited → valid. Mark visited[3][2]=true. Call solve(3, 2, path="DDRDR").

  • visited state: {(0,0), (1,0), (2,0), (2,1), (3,1), (3,2)}

Step 7: At (3,2). Try D → out of bounds. Try R → (3,3): maze[3][3]=1, not visited → valid. Call solve(3, 3, path="DDRDRR").

  • (3,3) is the destination! Add "DDRDRR" to result. Return.
  • result = ["DDRDRR"]

Step 8: Back at (3,2). Unmark visited[3][3]. Try U → (2,2): maze[2][2]=0 → blocked. Try L → (3,1): visited → skip. All directions exhausted. Unmark visited[3][2]. Return.

Step 9: Back at (3,1). Try U → (2,1): visited → skip. Try L → (3,0): blocked. All done. Unmark visited[3][1]. Return.

Step 10: Back at (2,1). Try R → (2,2): blocked. Try U → (1,1): maze[1][1]=1, not visited. Mark visited[1][1]=true. Call solve(1, 1, path="DDRU").

  • visited state: {(0,0), (1,0), (2,0), (2,1), (1,1)}

Step 11: At (1,1). Try D → (2,1): visited. Try R → (1,2): blocked. Try U → (0,1): blocked. Try L → (1,0): visited. Dead end! Unmark visited[1][1]. Return.

Step 12: Back at (2,1). Try L → (2,0): visited. All done. Unmark visited[2][1]. Return to (2,0). All directions from (2,0) exhausted. Unmark visited[2][0]. Return to (1,0).

Step 13: At (1,0). Already tried D. Try R → (1,1): maze[1][1]=1, not visited. Mark visited[1][1]=true. Call solve(1, 1, path="DR").

  • visited state: {(0,0), (1,0), (1,1)}

Step 14: At (1,1). Try D → (2,1): valid. Mark visited[2][1]=true. Call solve(2, 1, path="DRD").

  • visited state: {(0,0), (1,0), (1,1), (2,1)}

Step 15: At (2,1). Try D → (3,1): valid. Mark visited[3][1]=true. Call solve(3, 1, path="DRDD").

  • visited state: {(0,0), (1,0), (1,1), (2,1), (3,1)}

Step 16: At (3,1). Try R → (3,2): valid. Mark. Call solve(3, 2, path="DRDDR").

Step 17: At (3,2). Try R → (3,3): valid. Call solve(3, 3, path="DRDDRR").

  • (3,3) is the destination! Add "DRDDRR" to result.
  • result = ["DDRDRR", "DRDDRR"]

Step 18: Remaining backtracking finds no additional paths.

Step 19: Sort result: ["DDRDRR", "DRDDRR"] (already sorted in this case).

Final Result: ["DDRDRR", "DRDDRR"]

Algorithm

  1. If the start cell mat[0][0] or the end cell mat[n−1][n−1] is 0, return an empty list immediately.
  2. Create a boolean matrix visited of size n × n, initialized to all false.
  3. Mark visited[0][0] = true.
  4. Call the recursive function solve(row, col, path, result):
    • Base case: If row == n−1 and col == n−1, append path to result and return.
    • Recursive case: For each of the 4 directions (D, R, U, L):
      • Compute the new row and column.
      • If the new cell is within bounds, maze value is 1, and not visited:
        • Mark it as visited.
        • Recurse with the new position and the extended path.
        • Unmark it (backtrack).
  5. After the recursion completes, sort result lexicographically.
  6. Return result.

Code

#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    void solve(int r, int c, vector<vector<int>>& maze,
               vector<vector<bool>>& visited, string path,
               vector<string>& result) {
        int n = maze.size();
        if (r == n - 1 && c == n - 1) {
            result.push_back(path);
            return;
        }
        // Directions: D, R, U, L (not sorted)
        int dr[] = {1, 0, -1, 0};
        int dc[] = {0, 1, 0, -1};
        char dir[] = {'D', 'R', 'U', 'L'};

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n
                && maze[nr][nc] == 1 && !visited[nr][nc]) {
                visited[nr][nc] = true;
                solve(nr, nc, maze, visited, path + dir[i], result);
                visited[nr][nc] = false;
            }
        }
    }

    vector<string> findPath(vector<vector<int>>& maze) {
        int n = maze.size();
        vector<string> result;
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0)
            return result;

        vector<vector<bool>> visited(n, vector<bool>(n, false));
        visited[0][0] = true;
        solve(0, 0, maze, visited, "", result);
        sort(result.begin(), result.end());
        return result;
    }
};
class Solution:
    def findPath(self, maze):
        n = len(maze)
        if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
            return []

        result = []
        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True

        # Directions: D, R, U, L (not sorted)
        directions = [(1, 0, 'D'), (0, 1, 'R'), (-1, 0, 'U'), (0, -1, 'L')]

        def solve(r, c, path):
            if r == n - 1 and c == n - 1:
                result.append(path)
                return

            for dr, dc, d in directions:
                nr, nc = r + dr, c + dc
                if (0 <= nr < n and 0 <= nc < n
                        and maze[nr][nc] == 1 and not visited[nr][nc]):
                    visited[nr][nc] = True
                    solve(nr, nc, path + d)
                    visited[nr][nc] = False

        solve(0, 0, "")
        result.sort()
        return result
import java.util.*;

class Solution {
    private void solve(int r, int c, int[][] maze,
                       boolean[][] visited, String path,
                       List<String> result) {
        int n = maze.length;
        if (r == n - 1 && c == n - 1) {
            result.add(path);
            return;
        }
        // Directions: D, R, U, L (not sorted)
        int[] dr = {1, 0, -1, 0};
        int[] dc = {0, 1, 0, -1};
        char[] dir = {'D', 'R', 'U', 'L'};

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n
                && maze[nr][nc] == 1 && !visited[nr][nc]) {
                visited[nr][nc] = true;
                solve(nr, nc, maze, visited, path + dir[i], result);
                visited[nr][nc] = false;
            }
        }
    }

    public List<String> findPath(int[][] maze) {
        int n = maze.length;
        List<String> result = new ArrayList<>();
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0)
            return result;

        boolean[][] visited = new boolean[n][n];
        visited[0][0] = true;
        solve(0, 0, maze, visited, "", result);
        Collections.sort(result);
        return result;
    }
}

Complexity Analysis

Time Complexity: O(4^(n²))

In the worst case (a fully open grid), at each of the n² cells the rat may try up to 4 directions. This leads to a recursion tree with branching factor 4 and depth up to n². While the visited constraint prunes many branches in practice, the theoretical upper bound remains O(4^(n²)).

Space Complexity: O(n²)

The separate visited boolean matrix uses O(n²) space. The recursion stack can go as deep as n² in the worst case (visiting every cell in one path), adding another O(n²). The total auxiliary space is O(n²). Additionally, sorting the collected paths at the end takes O(k × L × log k) time, where k is the number of paths and L is the average path length.

Why This Approach Is Not Efficient

While the brute force recursive approach correctly finds all paths, it has two notable inefficiencies:

1. Extra Space for the Visited Matrix:
We allocate a separate n × n boolean matrix purely to track visited cells. For n = 5, this is 25 extra cells. The maze matrix itself already encodes open (1) and blocked (0) cells. If we could repurpose the maze to also track visited status — temporarily setting a cell to 0 when visiting and restoring it to 1 when backtracking — we would eliminate this extra space entirely.

2. Post-processing Sort:
Because we try directions in an arbitrary order (D, R, U, L), the paths we discover may not be in lexicographic order. We must sort all collected paths at the end, which costs O(k × L × log k) where k is the number of valid paths and L is the average path length. If we carefully choose the direction order to be D, L, R, U (the lexicographic order of the direction characters), paths would be generated in sorted order naturally, eliminating the sorting step.

Key Insight: By modifying the maze in-place instead of using a separate visited matrix, and by trying directions in lexicographic order, we can both reduce space usage and remove the need for post-processing — all without changing the core backtracking strategy.

Optimal Approach - DFS Backtracking with In-Place Marking

Intuition

The core algorithm remains the same — depth-first search with backtracking — but with two clever optimizations:

Optimization 1: Use the Maze Itself as the Visited Tracker

Instead of maintaining a separate visited matrix, we temporarily modify the maze. When the rat steps onto cell (r, c), we set maze[r][c] = 0. This makes the cell appear "blocked" to any future recursive calls on the same path, preventing revisits. When the rat backtracks from that cell, we restore maze[r][c] = 1, making it available for other paths.

Think of it like leaving footprints in sand. As you walk through the maze, your footprints block the path behind you. When you retrace your steps, the sand fills back in, leaving no trace for the next attempt.

Optimization 2: Try Directions in Lexicographic Order

The four direction characters are D, L, R, U. If we always try directions in this exact order, the recursion naturally explores paths in lexicographic order. The first complete path found will be lexicographically smallest, the second will be the next smallest, and so on. No sorting is needed.

This works because at every decision point in the recursion tree, the branches are explored from smallest (D) to largest (U). This guarantees the global ordering of complete paths.

Step-by-Step Explanation

Let us trace through Example 1: mat = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]].

Directions are tried in lexicographic order: D (Down), L (Left), R (Right), U (Up).

Step 1: Start at (0,0). Mark it visited by setting maze[0][0] = 0. Path = "". Begin exploring.

Step 2: From (0,0), try D → (1,0). maze[1][0] = 1, valid. Set maze[1][0] = 0. Move to (1,0). Path = "D".

Step 3: From (1,0), try D → (2,0). maze[2][0] = 1, valid. Set maze[2][0] = 0. Move to (2,0). Path = "DD".

Step 4: From (2,0), try D → (3,0): maze[3][0] = 0, blocked. Try L → (2,−1): out of bounds. Try R → (2,1): maze[2][1] = 1, valid. Set maze[2][1] = 0. Move to (2,1). Path = "DDR".

Step 5: From (2,1), try D → (3,1): maze[3][1] = 1, valid. Set maze[3][1] = 0. Move to (3,1). Path = "DDRD".

Step 6: From (3,1), try D → (4,1): out of bounds. Try L → (3,0): blocked. Try R → (3,2): maze[3][2] = 1, valid. Set maze[3][2] = 0. Move to (3,2). Path = "DDRDR".

Step 7: From (3,2), try D → out of bounds. Try L → (3,1): marked 0 (visited). Try R → (3,3): maze[3][3] = 1, valid. Move to (3,3). Path = "DDRDRR".

Step 8: (3,3) is the destination! Record path "DDRDRR". Result = ["DDRDRR"]. Return.

Step 9: Backtrack: restore maze[3][3]=1, maze[3][2]=1, maze[3][1]=1. Back at (2,1). Try remaining directions from (2,1).

Step 10: From (2,1), next untried: L → (2,0): marked 0 (visited). Try R → (2,2): maze[2][2] = 0, blocked. Try U → (1,1): maze[1][1] = 1, valid. Set maze[1][1] = 0. Move to (1,1). Path = "DDRU".

Step 11: From (1,1): D → (2,1): marked 0. L → (1,0): marked 0. R → (1,2): blocked. U → (0,1): blocked. Dead end! All four directions fail.

Step 12: Backtrack: restore maze[1][1]=1. All directions from (2,1) exhausted. Restore maze[2][1]=1. All from (2,0) exhausted. Restore maze[2][0]=1. Back at (1,0).

Step 13: From (1,0), D already explored. Try L → out of bounds. Try R → (1,1): maze[1][1] = 1, valid. Set maze[1][1] = 0. Move to (1,1). Path = "DR".

Step 14: From (1,1), try D → (2,1): maze[2][1] = 1, valid. Set maze[2][1] = 0. Move to (2,1). Path = "DRD".

Step 15: From (2,1), try D → (3,1): maze[3][1] = 1, valid. Set maze[3][1] = 0. Move to (3,1). Path = "DRDD".

Step 16: From (3,1), try R → (3,2): maze[3][2] = 1, valid. Set maze[3][2] = 0. Move to (3,2). Path = "DRDDR".

Step 17: From (3,2), try R → (3,3): maze[3][3] = 1, valid. Move to (3,3). Path = "DRDDRR".

Step 18: (3,3) is the destination! Record path "DRDDRR". Result = ["DDRDRR", "DRDDRR"].

Step 19: All remaining backtracking explores no new paths. Exploration complete.

Final Result: ["DDRDRR", "DRDDRR"] — already in lexicographic order thanks to the DLRU direction ordering.

DFS Backtracking — Finding All Paths in the Maze — Watch how the rat explores the maze depth-first, marks cells visited, backtracks from dead ends, and discovers both valid paths.

Algorithm

  1. If mat[0][0] == 0 or mat[n−1][n−1] == 0, return an empty list (no path possible).
  2. Mark the start cell: set mat[0][0] = 0.
  3. Call the recursive function solve(row, col, path, result):
    • Base case: If row == n−1 and col == n−1, append path to result and return.
    • Recursive case: For each direction in lexicographic order (D, L, R, U):
      • Compute new_row = row + dr[i], new_col = col + dc[i].
      • If the new cell is within bounds and mat[new_row][new_col] == 1:
        • Set mat[new_row][new_col] = 0 (mark visited in-place).
        • Append the direction character to path.
        • Recurse with the new position.
        • Remove the last character from path (backtrack path).
        • Set mat[new_row][new_col] = 1 (restore the cell).
  4. Restore mat[0][0] = 1.
  5. Return result (already sorted due to DLRU order).

Code

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    void solve(int r, int c, vector<vector<int>>& maze,
               string& path, vector<string>& result) {
        int n = maze.size();
        if (r == n - 1 && c == n - 1) {
            result.push_back(path);
            return;
        }
        // Directions in lexicographic order: D, L, R, U
        int dr[] = {1, 0, 0, -1};
        int dc[] = {0, -1, 1, 0};
        char dir[] = {'D', 'L', 'R', 'U'};

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n
                && maze[nr][nc] == 1) {
                maze[nr][nc] = 0;
                path.push_back(dir[i]);
                solve(nr, nc, maze, path, result);
                path.pop_back();
                maze[nr][nc] = 1;
            }
        }
    }

    vector<string> findPath(vector<vector<int>>& maze) {
        int n = maze.size();
        vector<string> result;
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0)
            return result;

        maze[0][0] = 0;
        string path = "";
        solve(0, 0, maze, path, result);
        maze[0][0] = 1;
        return result;
    }
};
class Solution:
    def findPath(self, maze):
        n = len(maze)
        if maze[0][0] == 0 or maze[n - 1][n - 1] == 0:
            return []

        result = []
        # Directions in lexicographic order: D, L, R, U
        directions = [(1, 0, 'D'), (0, -1, 'L'), (0, 1, 'R'), (-1, 0, 'U')]

        def solve(r, c, path):
            if r == n - 1 and c == n - 1:
                result.append(path)
                return

            for dr, dc, d in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and maze[nr][nc] == 1:
                    maze[nr][nc] = 0      # Mark visited
                    solve(nr, nc, path + d)
                    maze[nr][nc] = 1      # Restore

        maze[0][0] = 0
        solve(0, 0, "")
        maze[0][0] = 1
        return result
import java.util.*;

class Solution {
    private void solve(int r, int c, int[][] maze,
                       StringBuilder path, List<String> result) {
        int n = maze.length;
        if (r == n - 1 && c == n - 1) {
            result.add(path.toString());
            return;
        }
        // Directions in lexicographic order: D, L, R, U
        int[] dr = {1, 0, 0, -1};
        int[] dc = {0, -1, 1, 0};
        char[] dir = {'D', 'L', 'R', 'U'};

        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n
                && maze[nr][nc] == 1) {
                maze[nr][nc] = 0;
                path.append(dir[i]);
                solve(nr, nc, maze, path, result);
                path.deleteCharAt(path.length() - 1);
                maze[nr][nc] = 1;
            }
        }
    }

    public List<String> findPath(int[][] maze) {
        int n = maze.length;
        List<String> result = new ArrayList<>();
        if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0)
            return result;

        maze[0][0] = 0;
        StringBuilder path = new StringBuilder();
        solve(0, 0, maze, path, result);
        maze[0][0] = 1;
        return result;
    }
}

Complexity Analysis

Time Complexity: O(4^(n²))

In the worst case (a fully open n×n grid), at each cell the rat tries up to 4 directions. With up to n² cells in a single path, the recursion tree can have a branching factor of 4 at each of the n² levels. The visited-cell constraint significantly prunes this tree in practice, but the theoretical upper bound is O(4^(n²)). Given the constraint n ≤ 5, this is at most 4^25 ≈ 10^15 in the absolute worst case, though actual execution is far less due to blocking and visited cells.

Space Complexity: O(n²)

The primary space consumers are:

  1. Recursion stack: At most n² frames deep (one per cell on the longest path), each using O(1) space → O(n²) total.
  2. No separate visited matrix — the maze itself tracks visited state, saving O(n²) compared to the brute force.
  3. Path string: At most O(n²) characters long.

Total auxiliary space is O(n²), which is an improvement over the brute force approach that requires an additional O(n²) for the visited matrix.

The in-place marking also avoids the O(k × L × log k) sorting cost since paths are generated in lexicographic order by design.