Consider a rat placed at position (0, 0) in an n x n square matrix mat[][]. The rat’s goal is to reach the destination at position (n-1, n-1). The rat can move in four possible directions: ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).
The matrix contains only two possible values:
0: A blocked cell through which the rat cannot travel.1: A free cell that the rat can pass through.
Your task is to find all possible paths the rat can take to reach the destination, starting from (0, 0) and ending at (n-1, n-1), under the condition that the rat cannot revisit any cell along the same path. Furthermore, the rat can only move to adjacent cells that are within the bounds of the matrix and not blocked.
If no path exists, return an empty list.
Note: Return the final result vector in lexicographically smallest order.
Here’s the [Problem Link] to begin with.
Examples:
Input: mat[][] = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]] Output: ["DDRDRR", "DRDDRR"] Explanation: The rat can reach the destination at (3, 3) from (0, 0) by two paths - DRDDRR and DDRDRR, when printed in sorted order we get DDRDRR DRDDRR.
Input: mat[][] = [[1, 0], [1, 0]]
Output: []
Explanation: No path exists as the destination cell is blocked.
Input: mat = [[1, 1, 1], [1, 0, 1], [1, 1, 1]] Output: ["DDRR", "RRDD"] Explanation: The rat has two possible paths to reach the destination: 1. "DDRR" 2. "RRDD", These are returned in lexicographically sorted order.
Constraints:
2 ≤ mat.size() ≤ 5
0 ≤ mat[i][j] ≤ 1
Solution 1: Brute Force Approach (Explicit Direction Handling)
Intuition
Think of this like helping a rat navigate through a maze by trying every possible route! The brute force approach explicitly handles each of the four possible directions (Down, Left, Right, Up) with separate if-conditions. For each direction, we check if it’s valid (within bounds, not visited, and not blocked), then recursively explore that path. It’s like being a maze solver who methodically checks “Can I go down? Can I go left? Can I go right? Can I go up?” at every junction, trying each valid option one by one.
Detailed Approach
- Explicit Direction Checks: Use separate if-statements for each direction (D, L, R, U).
- Boundary & Validity Checks: For each direction, check:
- Within maze boundaries
- Cell not already visited (to avoid cycles)
- Cell is open (value = 1)
- Backtracking Pattern:
- Mark current cell as visited
- Recursively explore the direction
- Unmark cell (backtrack) when returning
- Path Building: Build path string by appending direction characters (“D”, “L”, “R”, “U”).
- Base Case: When rat reaches (N-1, N-1), add the complete path to results.
Code
def findPathHelper(
i: int, j: int, a: List[List[int]], n: int,
ans: List[str], move: str, vis: List[List[int]]
):
# Base case: reached destination
if i == n - 1 and j == n - 1:
ans.append(move)
return
# Try going downward (i+1, j)
if i + 1 < n and not vis[i + 1][j] and a[i + 1][j] == 1:
vis[i][j] = 1 # Mark current cell as visited
findPathHelper(i + 1, j, a, n, ans, move + "D", vis)
vis[i][j] = 0 # Backtrack: unmark current cell
# Try going left (i, j-1)
if j - 1 >= 0 and not vis[i][j - 1] and a[i][j - 1] == 1:
vis[i][j] = 1
findPathHelper(i, j - 1, a, n, ans, move + "L", vis)
vis[i][j] = 0
# Try going right (i, j+1)
if j + 1 < n and not vis[i][j + 1] and a[i][j + 1] == 1:
vis[i][j] = 1
findPathHelper(i, j + 1, a, n, ans, move + "R", vis)
vis[i][j] = 0
# Try going upward (i-1, j)
if i - 1 >= 0 and not vis[i - 1][j] and a[i - 1][j] == 1:
vis[i][j] = 1
findPathHelper(i - 1, j, a, n, ans, move + "U", vis)
vis[i][j] = 0
def ratMaze(matrix: List[List[int]]) -> List[str]:
n = len(matrix)
ans = []
vis = [[0 for _ in range(n)] for _ in range(n)] # Visited array
# Only start if source cell is open
if matrix[0][0] == 1:
findPathHelper(0, 0, matrix, n, ans, "", vis)
return ansCode Explanation
This brute force solution explicitly handles each direction with separate if-conditions. Each direction check follows the same pattern: validate boundaries, check if cell is unvisited and open, then mark current cell as visited, recursively explore, and backtrack by unmarking. The move string accumulates the path taken so far, and when we reach the destination, we add it to our results. The visited array prevents infinite loops by ensuring we don’t revisit cells in the current path.
Dry Run
Let’s trace through: matrix = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
graph TD
Root["findPathHelper(0,0, move='', vis=all 0)<br/>Matrix: [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]<br/>Start at (0,0), target (3,3)"]
%% Level 0: From (0,0), check 4 directions
Root --- A["Try Down to (1,0)<br/>Check: i+1=1 < 4 ✓, vis[1][0]=0 ✓, mat[1][0]=1 ✓<br/>Mark vis[0][0]=1, move='D'<br/>Recurse to (1,0)"]
Root --- B["Try Left: j-1=-1 < 0 ❌<br/>Out of bounds"]
Root --- C["Try Right to (0,1)<br/>Check: j+1=1 < 4 ✓, vis[0][1]=0 ✓, mat[0][1]=0 ❌<br/>Blocked cell"]
Root --- D["Try Up: i-1=-1 < 0 ❌<br/>Out of bounds"]
%% Level 1: From (1,0), check 4 directions
A --- A1["Try Down to (2,0)<br/>Check: mat[2][0]=1 ✓, not visited ✓<br/>Mark vis[1][0]=1, move='DD'<br/>Recurse to (2,0)"]
A --- A2["Try Left: j-1=-1 < 0 ❌<br/>Out of bounds"]
A --- A3["Try Right to (1,1)<br/>Check: mat[1][1]=1 ✓, not visited ✓<br/>Mark vis[1][0]=1, move='DR'<br/>Recurse to (1,1)"]
A --- A4["Try Up to (0,0)<br/>Check: mat[0][0]=1 ✓, but vis[0][0]=1 ❌<br/>Already visited"]
%% Level 2: From (2,0), check 4 directions
A1 --- A1a["Try Down: mat[3][0]=0 ❌<br/>Blocked cell"]
A1 --- A1b["Try Left: j-1=-1 < 0 ❌<br/>Out of bounds"]
A1 --- A1c["Try Right to (2,1)<br/>Check: mat[2][1]=1 ✓, not visited ✓<br/>Mark vis[2][0]=1, move='DDR'<br/>Recurse to (2,1)"]
A1 --- A1d["Try Up to (1,0)<br/>vis[1][0]=1 ❌<br/>Already visited"]
%% Level 2: From (1,1), check 4 directions
A3 --- A3a["Try Down to (2,1)<br/>Check: mat[2][1]=1 ✓, not visited ✓<br/>Mark vis[1][1]=1, move='DRD'<br/>Recurse to (2,1)"]
A3 --- A3b["Try Left to (1,0)<br/>vis[1][0]=1 ❌<br/>Already visited"]
A3 --- A3c["Try Right to (1,2)<br/>mat[1][2]=0 ❌<br/>Blocked cell"]
A3 --- A3d["Try Up to (0,1)<br/>mat[0][1]=0 ❌<br/>Blocked cell"]
%% Level 3: From (2,1) via path DD, check 4 directions
A1c --- A1c1["Try Down to (3,1)<br/>Check: mat[3][1]=1 ✓, not visited ✓<br/>Mark vis[2][1]=1, move='DDRD'<br/>Recurse to (3,1)"]
A1c --- A1c2["Try Left to (2,0)<br/>vis[2][0]=1 ❌<br/>Already visited"]
A1c --- A1c3["Try Right to (2,2)<br/>mat[2][2]=0 ❌<br/>Blocked cell"]
A1c --- A1c4["Try Up to (1,1)<br/>mat[1][1]=1 ✓, not visited ✓<br/>Mark vis[2][1]=1, move='DDRU'<br/>Recurse to (1,1)"]
%% Level 3: From (2,1) via path DR, check 4 directions
A3a --- A3a1["Try Down to (3,1)<br/>Check: mat[3][1]=1 ✓, not visited ✓<br/>Mark vis[2][1]=1, move='DRDD'<br/>Recurse to (3,1)"]
A3a --- A3a2["Try Left to (2,0)<br/>mat[2][0]=1 ✓, not visited ✓<br/>Mark vis[2][1]=1, move='DRDL'<br/>Recurse to (2,0)"]
A3a --- A3a3["Try Right to (2,2)<br/>mat[2][2]=0 ❌<br/>Blocked cell"]
A3a --- A3a4["Try Up to (1,1)<br/>vis[1][1]=1 ❌<br/>Already visited"]
%% Level 4: From (3,1) via path DDRD
A1c1 --- A1c1a["Try Down: i+1=4 >= 4 ❌<br/>Out of bounds"]
A1c1 --- A1c1b["Try Left to (3,0)<br/>mat[3][0]=0 ❌<br/>Blocked cell"]
A1c1 --- A1c1c["Try Right to (3,2)<br/>Check: mat[3][2]=1 ✓, not visited ✓<br/>Mark vis[3][1]=1, move='DDRDR'<br/>Recurse to (3,2)"]
A1c1 --- A1c1d["Try Up to (2,1)<br/>vis[2][1]=1 ❌<br/>Already visited"]
%% Level 4: From (3,1) via path DRDD
A3a1 --- A3a1a["Try Down: i+1=4 >= 4 ❌<br/>Out of bounds"]
A3a1 --- A3a1b["Try Left to (3,0)<br/>mat[3][0]=0 ❌<br/>Blocked cell"]
A3a1 --- A3a1c["Try Right to (3,2)<br/>Check: mat[3][2]=1 ✓, not visited ✓<br/>Mark vis[3][1]=1, move='DRDDR'<br/>Recurse to (3,2)"]
A3a1 --- A3a1d["Try Up to (2,1)<br/>vis[2][1]=1 ❌<br/>Already visited"]
%% Level 5: From (3,2) via path DDRDR
A1c1c --- A1c1c1["Try Down: i+1=4 >= 4 ❌<br/>Out of bounds"]
A1c1c --- A1c1c2["Try Left to (3,1)<br/>vis[3][1]=1 ❌<br/>Already visited"]
A1c1c --- A1c1c3["Try Right to (3,3)<br/>Check: mat[3][3]=1 ✓, not visited ✓<br/>i=3, j=3 == n-1=3 ✓<br/>Found destination!<br/>move='DDRDDR'"]
A1c1c --- A1c1c4["Try Up to (2,2)<br/>mat[2][2]=0 ❌<br/>Blocked cell"]
%% Level 5: From (3,2) via path DRDDR
A3a1c --- A3a1c1["Try Down: i+1=4 >= 4 ❌<br/>Out of bounds"]
A3a1c --- A3a1c2["Try Left to (3,1)<br/>vis[3][1]=1 ❌<br/>Already visited"]
A3a1c --- A3a1c3["Try Right to (3,3)<br/>Check: mat[3][3]=1 ✓, not visited ✓<br/>i=3, j=3 == n-1=3 ✓<br/>Found destination!<br/>move='DRDDRR'"]
A3a1c --- A3a1c4["Try Up to (2,2)<br/>mat[2][2]=0 ❌<br/>Blocked cell"]
%% Success cases
A1c1c3 --- Success1["✅ Add 'DDRDDR' to result<br/>Backtrack and unmark vis arrays"]
A3a1c3 --- Success2["✅ Add 'DRDDRR' to result<br/>Backtrack and unmark vis arrays"]
%% Final result
Success1 --- Final["Final Result: ['DDRDDR', 'DRDDRR']"]
Success2 --- Final
%% Styling
style Success1 fill:#90EE90
style Success2 fill:#90EE90
style Final fill:#90EE90
style B fill:#FFB6C1
style C fill:#FFB6C1
style D fill:#FFB6C1
style A2 fill:#FFB6C1
style A4 fill:#FFB6C1
style A1a fill:#FFB6C1
style A1b fill:#FFB6C1
style A1d fill:#FFB6C1
style A3b fill:#FFB6C1
style A3c fill:#FFB6C1
style A3d fill:#FFB6C1
style A1c1c3 fill:#87CEEB
style A3a1c fill:#87CEEB
style A1c1 fill:#87CEEB
style A3a1 fill:#87CEEB
style Root fill:#E6E6FA
For detailed dry run [Click here]
Time and Space Complexity
- Time Complexity: O(4^(N×N)) – In worst case, we explore 4 directions at each of N×N cells
- Space Complexity: O(N×N) – Visited array plus maximum recursion depth of N×N
Simplifying It
This approach is like having a very methodical rat that at every junction says “Let me try going down first, then left, then right, then up” and carefully explores each direction one by one. It’s straightforward but involves a lot of repetitive code for each direction.
Solution 2: Optimal Approach (Direction Arrays for Clean Code)
Intuition
Instead of writing separate code for each direction, why not be smart and use arrays to represent all directions uniformly? This is like having a compass that points to all four directions – we can loop through the directions instead of hardcoding each one. The key insight is that all four directions follow the same pattern: check validity, mark visited, recurse, backtrack. By using direction arrays (di, dj) and a direction string “DLRU”, we can handle all directions in a single loop, making the code much cleaner and more maintainable.
Detailed Approach
- Direction Arrays: Use
di = [+1, 0, 0, -1]anddj = [0, -1, +1, 0]to represent direction offsets. - Direction String: Use
"DLRU"to map array indices to direction characters. - Unified Loop: Single for-loop to try all 4 directions instead of 4 separate if-statements.
- Same Logic: Each iteration follows the same pattern: calculate next position, validate, recurse, backtrack.
- Cleaner Code: Eliminates code duplication while maintaining the same algorithmic approach.
Code
def solve(
i: int, j: int, a: List[List[int]], n: int,
ans: List[str], move: str, vis: List[List[int]],
di: List[int], dj: List[int]
):
# Base case: reached destination
if i == n - 1 and j == n - 1:
ans.append(move)
return
dir = "DLRU" # Direction characters corresponding to di, dj arrays
# Try all 4 directions in a loop
for ind in range(4):
nexti = i + di[ind] # Calculate next row
nextj = j + dj[ind] # Calculate next column
# Check if next position is valid
if (
nexti >= 0 and nextj >= 0 and # Within upper bounds
nexti < n and nextj < n and # Within lower bounds
not vis[nexti][nextj] and # Not visited
a[nexti][nextj] == 1 # Open cell
):
vis[i][j] = 1 # Mark current cell as visited
solve(nexti, nextj, a, n, ans, move + dir[ind], vis, di, dj)
vis[i][j] = 0 # Backtrack: unmark current cell
def ratMaze(matrix: List[List[int]]) -> List[str]:
n = len(matrix)
ans = []
vis = [[0 for _ in range(n)] for _ in range(n)]
# Direction arrays: Down, Left, Right, Up
di = [+1, 0, 0, -1] # Row offsets
dj = [0, -1, +1, 0] # Column offsets
# Only start if source cell is open
if matrix[0][0] == 1:
solve(0, 0, matrix, n, ans, "", vis, di, dj)
return ansCode Explanation
This optimal solution uses direction arrays to eliminate code duplication. The di and dj arrays represent row and column offsets for each direction: Down (+1,0), Left (0,-1), Right (0,+1), Up (-1,0). The string "DLRU" maps these array indices to their corresponding direction characters. Instead of four separate if-conditions, we use a single loop that tries each direction systematically. The validation logic remains the same, but now it’s centralized in one place, making the code more maintainable and less error-prone.
Dry Run
Let’s trace through: matrix = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
graph TD
Root["solve(0,0, move='', vis=all 0)<br/>Matrix: [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]<br/>di=[+1,0,0,-1], dj=[0,-1,+1,0], dir='DLRU'<br/>Start at (0,0), target (3,3)"]
%% Level 0: From (0,0), loop through 4 directions (ind=0,1,2,3)
Root --- A["ind=0: D (Down)<br/>nexti=0+1=1, nextj=0+0=0<br/>Check: (1,0) in bounds ✓, vis[1][0]=0 ✓, mat[1][0]=1 ✓<br/>Mark vis[0][0]=1, move='D'<br/>Recurse to (1,0)"]
Root --- B["ind=1: L (Left)<br/>nexti=0+0=0, nextj=0-1=-1<br/>Check: nextj=-1 < 0 ❌<br/>Out of bounds"]
Root --- C["ind=2: R (Right)<br/>nexti=0+0=0, nextj=0+1=1<br/>Check: (0,1) in bounds ✓, vis[0][1]=0 ✓, mat[0][1]=0 ❌<br/>Blocked cell"]
Root --- D["ind=3: U (Up)<br/>nexti=0-1=-1, nextj=0+0=0<br/>Check: nexti=-1 < 0 ❌<br/>Out of bounds"]
%% Level 1: From (1,0), loop through 4 directions
A --- A1["ind=0: D (Down)<br/>nexti=1+1=2, nextj=0+0=0<br/>Check: (2,0) valid, mat[2][0]=1 ✓<br/>Mark vis[1][0]=1, move='DD'<br/>Recurse to (2,0)"]
A --- A2["ind=1: L (Left)<br/>nexti=1+0=1, nextj=0-1=-1<br/>Check: nextj=-1 < 0 ❌<br/>Out of bounds"]
A --- A3["ind=2: R (Right)<br/>nexti=1+0=1, nextj=0+1=1<br/>Check: (1,1) valid, mat[1][1]=1 ✓<br/>Mark vis[1][0]=1, move='DR'<br/>Recurse to (1,1)"]
A --- A4["ind=3: U (Up)<br/>nexti=1-1=0, nextj=0+0=0<br/>Check: (0,0) valid but vis[0][0]=1 ❌<br/>Already visited"]
%% Level 2: From (2,0), loop through 4 directions
A1 --- A1a["ind=0: D (Down)<br/>nexti=2+1=3, nextj=0+0=0<br/>Check: (3,0) valid but mat[3][0]=0 ❌<br/>Blocked cell"]
A1 --- A1b["ind=1: L (Left)<br/>nexti=2+0=2, nextj=0-1=-1<br/>Check: nextj=-1 < 0 ❌<br/>Out of bounds"]
A1 --- A1c["ind=2: R (Right)<br/>nexti=2+0=2, nextj=0+1=1<br/>Check: (2,1) valid, mat[2][1]=1 ✓<br/>Mark vis[2][0]=1, move='DDR'<br/>Recurse to (2,1)"]
A1 --- A1d["ind=3: U (Up)<br/>nexti=2-1=1, nextj=0+0=0<br/>Check: (1,0) valid but vis[1][0]=1 ❌<br/>Already visited"]
%% Level 2: From (1,1), loop through 4 directions
A3 --- A3a["ind=0: D (Down)<br/>nexti=1+1=2, nextj=1+0=1<br/>Check: (2,1) valid, mat[2][1]=1 ✓<br/>Mark vis[1][1]=1, move='DRD'<br/>Recurse to (2,1)"]
A3 --- A3b["ind=1: L (Left)<br/>nexti=1+0=1, nextj=1-1=0<br/>Check: (1,0) valid but vis[1][0]=1 ❌<br/>Already visited"]
A3 --- A3c["ind=2: R (Right)<br/>nexti=1+0=1, nextj=1+1=2<br/>Check: (1,2) valid but mat[1][2]=0 ❌<br/>Blocked cell"]
A3 --- A3d["ind=3: U (Up)<br/>nexti=1-1=0, nextj=1+0=1<br/>Check: (0,1) valid but mat[0][1]=0 ❌<br/>Blocked cell"]
%% Level 3: From (2,1) via path DDR
A1c --- A1c1["ind=0: D (Down)<br/>nexti=2+1=3, nextj=1+0=1<br/>Check: (3,1) valid, mat[3][1]=1 ✓<br/>Mark vis[2][1]=1, move='DDRD'<br/>Recurse to (3,1)"]
A1c --- A1c2["ind=1: L (Left)<br/>nexti=2+0=2, nextj=1-1=0<br/>Check: (2,0) valid but vis[2][0]=1 ❌<br/>Already visited"]
A1c --- A1c3["ind=2: R (Right)<br/>nexti=2+0=2, nextj=1+1=2<br/>Check: (2,2) valid but mat[2][2]=0 ❌<br/>Blocked cell"]
A1c --- A1c4["ind=3: U (Up)<br/>nexti=2-1=1, nextj=1+0=1<br/>Check: (1,1) valid, mat[1][1]=1 ✓<br/>Mark vis[2][1]=1, move='DDRU'<br/>Recurse to (1,1)"]
%% Level 3: From (2,1) via path DRD
A3a --- A3a1["ind=0: D (Down)<br/>nexti=2+1=3, nextj=1+0=1<br/>Check: (3,1) valid, mat[3][1]=1 ✓<br/>Mark vis[2][1]=1, move='DRDD'<br/>Recurse to (3,1)"]
A3a --- A3a2["ind=1: L (Left)<br/>nexti=2+0=2, nextj=1-1=0<br/>Check: (2,0) valid, mat[2][0]=1 ✓<br/>Mark vis[2][1]=1, move='DRDL'<br/>Recurse to (2,0)"]
A3a --- A3a3["ind=2: R (Right)<br/>nexti=2+0=2, nextj=1+1=2<br/>Check: (2,2) valid but mat[2][2]=0 ❌<br/>Blocked cell"]
A3a --- A3a4["ind=3: U (Up)<br/>nexti=2-1=1, nextj=1+0=1<br/>Check: (1,1) valid but vis[1][1]=1 ❌<br/>Already visited"]
%% Level 4: From (3,1) via path DDRD, continue to find (3,3)
A1c1 --- A1c1c["ind=2: R (Right)<br/>nexti=3+0=3, nextj=1+1=2<br/>Check: (3,2) valid, mat[3][2]=1 ✓<br/>Mark vis[3][1]=1, move='DDRDR'<br/>Recurse to (3,2)"]
%% Level 4: From (3,1) via path DRDD, continue to find (3,3)
A3a1 --- A3a1c["ind=2: R (Right)<br/>nexti=3+0=3, nextj=1+1=2<br/>Check: (3,2) valid, mat[3][2]=1 ✓<br/>Mark vis[3][1]=1, move='DRDDR'<br/>Recurse to (3,2)"]
%% Level 5: From (3,2), reach destination (3,3)
A1c1c --- A1c1c3["ind=2: R (Right)<br/>nexti=3+0=3, nextj=2+1=3<br/>Check: (3,3) valid, mat[3][3]=1 ✓<br/>i=3, j=3 == n-1=3 ✓<br/>Found destination!<br/>move='DDRDDR'"]
A3a1c --- A3a1c3["ind=2: R (Right)<br/>nexti=3+0=3, nextj=2+1=3<br/>Check: (3,3) valid, mat[3][3]=1 ✓<br/>i=3, j=3 == n-1=3 ✓<br/>Found destination!<br/>move='DRDDRR'"]
%% Success cases
A1c1c3 --- Success1["✅ Add 'DDRDDR' to result<br/>Backtrack and unmark vis arrays"]
A3a1c3 --- Success2["✅ Add 'DRDDRR' to result<br/>Backtrack and unmark vis arrays"]
%% Final result
Success1 --- Final["Final Result: ['DDRDDR', 'DRDDRR']"]
Success2 --- Final
%% Styling
style Success1 fill:#90EE90
style Success2 fill:#90EE90
style Final fill:#90EE90
style B fill:#FFB6C1
style C fill:#FFB6C1
style D fill:#FFB6C1
style A2 fill:#FFB6C1
style A4 fill:#FFB6C1
style A1a fill:#FFB6C1
style A1b fill:#FFB6C1
style A1d fill:#FFB6C1
style A3b fill:#FFB6C1
style A3c fill:#FFB6C1
style A3d fill:#FFB6C1
style A1c1c fill:#87CEEB
style A3a1c fill:#87CEEB
style A1c1 fill:#87CEEB
style A3a1 fill:#87CEEB
style Root fill:#E6E6FA
For detailed dry run [Click here]
Same exploration pattern as brute force, but with cleaner code structure
Time and Space Complexity
- Time Complexity: O(4^(N×N)) – Same as brute force, no algorithmic improvement
- Space Complexity: O(N×N) – Same space requirements as brute force
Simplifying It
This approach is like giving the rat a smart compass that automatically points to all four directions, so instead of manually checking “down, left, right, up”, the rat just follows the compass directions in order. The exploration is identical, but the implementation is much more elegant and maintainable.
Summary
| Approach | Time | Space | Difficulty | Best For |
|---|---|---|---|---|
| Brute Force (Explicit Directions) | O(4^(N×N)) | O(N×N) | Medium | Understanding the concept |
| Optimal (Direction Arrays) | O(4^(N×N)) | O(N×N) | Medium | Production code |
The optimal approach doesn’t improve time complexity but provides significant benefits:
- Code Maintainability – Single loop instead of 4 separate if-statements
- Reduced Bugs – Less code duplication means fewer places for errors
- Scalability – Easy to extend to 8-direction movement (add more directions to arrays)
- Readability – Cleaner, more professional code structure
The key insight for Rat in a Maze is recognizing that backtracking problems often involve repetitive patterns that can be elegantly handled with arrays and loops. The direction array technique is widely used in grid-based problems like word search, number of islands, and shortest path algorithms!
Both solutions use the same core algorithm – backtracking with DFS – but the optimal solution demonstrates how thoughtful code organization can make algorithms more maintainable without sacrificing performance.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.
