Log inSign up
mediumGeeksforGeeksNot Started

Rat in a Maze

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination.

The directions in which the rat can move are 'U'(up), 'D'(down), 'L'(left), 'R'(right). Value 0 in the cell indicates blocked cell and 1 indicates open cell.

No cell can be visited more than once in the same path. Return all paths in lexicographical sorted order.

Example 1:

Input: mat = [ [1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1] ]
Output: ["DDRDRR", "DRDDRR"]
Explanation: Two distinct paths lead from (0,0) to (3,3): DDRDRR and DRDDRR in lexicographical order.

Example 2:

Input: mat = [ [1, 0], [1, 0] ]
Output: ["-1"]
Explanation: No path exists to destination cell (1, 1).

Constraints:

  • 2 <= N <= 5
  • 0 <= mat[i][j] <= 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master 4-directional grid offsets and lexicographical ordering (D, L, R, U).
  • Understand in-place visited state marking to save auxiliary memory.
  • Formulate grid backtracking invariants with boundary and obstacle checks.

1. DFS with 2D Visited Matrix

Intuition

From (r, c), check boundaries, obstacle value, and !visited[r][c]. Recurse into valid neighbors in D, L, R, U order.

When to apply: Explicit 4-branch recursion with auxiliary 2D visited array.

Algorithm

  1. Step 1: Check if start (0,0) or destination (n-1, n-1) is 0; if so, return empty list.
  2. Step 2: Maintain a 2D boolean array visited of size N x N.
  3. Step 3: At cell (r, c), mark visited[r][c] = true.
  4. Step 4: Explicitly try moving Down (D), Left (L), Right (R), Up (U) if neighbor is within bounds, open (1), and unvisited.
  5. Step 5: When reaching (n-1, n-1), append path string to result.
  6. Step 6: Backtrack by resetting visited[r][c] = false.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 void backtrack(int r, int c, int n, std::vector<std::vector<int>>& mat, std::vector<std::vector<bool>>& visited, std::string& path, std::vector<std::string>& result) {
8 if (r == n - 1 && c == n - 1) {
9 result.push_back(path);
10 return;
11 }
12
13 visited[r][c] = true;
14
15 // Down
16 if (r + 1 < n && mat[r + 1][c] == 1 && !visited[r + 1][c]) {
17 path.push_back('D');
18 backtrack(r + 1, c, n, mat, visited, path, result);
19 path.pop_back();
20 }
21 // Left
22 if (c - 1 >= 0 && mat[r][c - 1] == 1 && !visited[r][c - 1]) {
23 path.push_back('L');
24 backtrack(r, c - 1, n, mat, visited, path, result);
25 path.pop_back();
26 }
27 // Right
28 if (c + 1 < n && mat[r][c + 1] == 1 && !visited[r][c + 1]) {
29 path.push_back('R');
30 backtrack(r, c + 1, n, mat, visited, path, result);
31 path.pop_back();
32 }
33 // Up
34 if (r - 1 >= 0 && mat[r - 1][c] == 1 && !visited[r - 1][c]) {
35 path.push_back('U');
36 backtrack(r - 1, c, n, mat, visited, path, result);
37 path.pop_back();
38 }
39
40 visited[r][c] = false;
41 }
42
43 std::vector<std::string> findPath(std::vector<std::vector<int>>& mat) {
44 int n = mat.size();
45 std::vector<std::string> result;
46 if (mat[0][0] == 0 || mat[n - 1][n - 1] == 0) return result;
47
48 std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
49 std::string path = "";
50 backtrack(0, 0, n, mat, visited, path, result);
51 return result;
52 }
53};
54
55int main() {
56 Solution solver;
57 std::vector<std::vector<int>> mat = {
58 {1, 0, 0, 0},
59 {1, 1, 0, 1},
60 {1, 1, 0, 0},
61 {0, 1, 1, 1}
62 };
63 std::vector<std::string> paths = solver.findPath(mat);
64 std::cout << "Paths:\n";
65 for (const auto& p : paths) std::cout << p << "\n";
66 return 0;
67}

Time & Space Complexity

  • Time complexity: O(4^(N^2)) — Each cell can branch in up to 4 directions.
  • Space complexity: O(N^2) — O(N2) for the visited boolean array and recursion call stack.

2. Compact 4-Directional Delta Offset Loop

Intuition

Using a single loop for (int i = 0; i < 4; i++) simplifies repetitive code while strictly preserving lexicographical traversal order.

Algorithm

  1. Step 1: Define directional offsets dRow = [1, 0, 0, -1], dCol = [0, -1, 1, 0], dir = [D, L, R, U].
  2. Step 2: Mark visited[r][c] = true upon entering cell (r, c).
  3. Step 3: Loop i = 0 to 3 to generate next cell (r + dRow[i], c + dCol[i]).
  4. Step 4: If neighbor is inside grid, mat[nr][nc] == 1, and !visited[nr][nc], append dir[i] and recurse.
  5. Step 5: Backtrack: pop last direction and set visited[r][c] = false.
  6. Step 6: When destination reached, record path.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 int dRow[4] = {1, 0, 0, -1};
8 int dCol[4] = {0, -1, 1, 0};
9 char dir[4] = {'D', 'L', 'R', 'U'};
10
11 void backtrack(int r, int c, int n, std::vector<std::vector<int>>& mat, std::vector<std::vector<bool>>& visited, std::string& path, std::vector<std::string>& result) {
12 if (r == n - 1 && c == n - 1) {
13 result.push_back(path);
14 return;
15 }
16
17 visited[r][c] = true;
18
19 for (int i = 0; i < 4; i++) {
20 int nr = r + dRow[i];
21 int nc = c + dCol[i];
22 if (nr >= 0 && nr < n && nc >= 0 && nc < n && mat[nr][nc] == 1 && !visited[nr][nc]) {
23 path.push_back(dir[i]);
24 backtrack(nr, nc, n, mat, visited, path, result);
25 path.pop_back();
26 }
27 }
28
29 visited[r][c] = false;
30 }
31
32 std::vector<std::string> findPath(std::vector<std::vector<int>>& mat) {
33 int n = mat.size();
34 std::vector<std::string> result;
35 if (mat[0][0] == 0 || mat[n - 1][n - 1] == 0) return result;
36
37 std::vector<std::vector<bool>> visited(n, std::vector<bool>(n, false));
38 std::string path = "";
39 backtrack(0, 0, n, mat, visited, path, result);
40 return result;
41 }
42};
43
44int main() {
45 Solution solver;
46 std::vector<std::vector<int>> mat = {
47 {1, 0, 0, 0},
48 {1, 1, 0, 1},
49 {1, 1, 0, 0},
50 {0, 1, 1, 1}
51 };
52 auto paths = solver.findPath(mat);
53 for (const auto& p : paths) std::cout << p << "\n";
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(4^(N^2)) — Compact loop over 4 directional vectors.
  • Space complexity: O(N^2) — O(N2) visited matrix and call stack.

3. In-Place Grid Modification Backtracking (Gold Standard)

Intuition

Since cells with value 0 are treated as blocked, mutating mat[r][c] = 0 automatically prevents revisiting the current cell in child calls. Restoring mat[r][c] = 1 preserves the maze state for sibling searches with 0 extra memory.

Algorithm

  1. Step 1: Handle base obstacle checks: if mat[0][0] == 0 or mat[n-1][n-1] == 0, return [].
  2. Step 2: Mark cell (r, c) as visited in-place by setting mat[r][c] = 0.
  3. Step 3: Iterate through 4 directions in DLRU order to maintain alphabetical result ordering.
  4. Step 4: If neighbor (nr, nc) is within bounds and mat[nr][nc] == 1, append direction letter and recurse.
  5. Step 5: Backtrack: restore cell state mat[r][c] = 1, requiring zero auxiliary visited memory.
  6. Step 6: Record completed paths when reaching (n-1, n-1).

4x4 Maze Navigation Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Start at (0,0)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
c3
c4
c5
c6
c7
c8
c9
c10
c11
c12
c13
c14
c15
r0
0*
↑ rat
0
0
0
1
1
0
1
1
1
0
0
0
1
1
1
Variables at this step
ratPos
[0,0]
path
Check / comparison
mat[1][0] == 1 -> OPEN -> Valid Down move
Decision / next transition
Move 'D' to (1,0), path = 'D'
Why this step matters

Start at (0,0). Mark cell (0,0) = 0 (visited in-place). Try Down move to (1,0).

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7 int dRow[4] = {1, 0, 0, -1};
8 int dCol[4] = {0, -1, 1, 0};
9 char dir[4] = {'D', 'L', 'R', 'U'};
10
11 void backtrack(int r, int c, int n, std::vector<std::vector<int>>& mat, std::string& path, std::vector<std::string>& result) {
12 if (r == n - 1 && c == n - 1) {
13 result.push_back(path);
14 return;
15 }
16
17 mat[r][c] = 0; // Mark in-place visited
18
19 for (int i = 0; i < 4; i++) {
20 int nr = r + dRow[i];
21 int nc = c + dCol[i];
22 if (nr >= 0 && nr < n && nc >= 0 && nc < n && mat[nr][nc] == 1) {
23 path.push_back(dir[i]);
24 backtrack(nr, nc, n, mat, path, result);
25 path.pop_back();
26 }
27 }
28
29 mat[r][c] = 1; // Restore state
30 }
31
32 std::vector<std::string> findPath(std::vector<std::vector<int>>& mat) {
33 int n = mat.size();
34 std::vector<std::string> result;
35 if (mat[0][0] == 0 || mat[n - 1][n - 1] == 0) return result;
36
37 std::string path = "";
38 backtrack(0, 0, n, mat, path, result);
39 return result;
40 }
41};
42
43int main() {
44 Solution solver;
45 std::vector<std::vector<int>> mat = {
46 {1, 0, 0, 0},
47 {1, 1, 0, 1},
48 {1, 1, 0, 0},
49 {0, 1, 1, 1}
50 };
51 auto paths = solver.findPath(mat);
52 std::cout << "In-Place Optimal Paths:\n";
53 for (const auto& p : paths) std::cout << p << "\n";
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O(4^(N^2)) — Optimal DFS traversal directly on the input array.
  • Space complexity: O(N^2) call stack, 0 auxiliary visited memory — Zero auxiliary matrix allocated.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS with 2D Visited Boolean MatrixO(4^(N^2))O(N^2)Use a separate visited[N][N] boolean matrix to prevent visiting the same cell twice.Direction exploration
2.Direction Arrays D, L, R, U (Better)O(4^(N^2))O(N^2)Use compact delta offsets dRow = {1, 0, 0, -1}, dCol = {0, -1, 1, 0}, dir = "DLRU".Recursion depth
3.In-Place Grid Modification Backtracking (Optimal)OptimalO(4^(N^2))O(N^2)Mark current cell mat[r][c] = 0 on entry and restore mat[r][c] = 1 on exit.Graph branching factor

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Traversing directions in non-lexicographical order (e.g. URDL instead of DLRU) and forgetting to sort the output.

Pitfall 2:

Forgetting to restore mat[r][c] = 1 on backtrack, causing future paths to falsely treat visited cells as permanent obstacles.

Crucial Edge Cases to Validate:

  • Start cell mat[0][0] is 0 -> immediately return [].
  • Destination cell mat[n-1][n-1] is 0 -> immediately return [].
  • No open path to destination -> returns empty list.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention both direction arrays and in-place grid marking to demonstrate clean, idiomatic coding.
  2. Highlight how starting cell mat[0][0] == 0 and ending cell mat[N-1][N-1] == 0 edge cases can be handled in O(1) before any recursion.
  3. Discuss how BFS can find the single shortest path in O(V + E) whereas Backtracking is required for finding *all* paths.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does traversing in the exact order [D, L, R, U] guarantee that results are generated in lexicographically sorted order?

Back to DSA Sheet