Rat in a Maze Problem in DSA Typescript

Mental Model

Find a path from start to finish in a grid by moving only through allowed cells.

Analogy: Imagine a mouse trying to find cheese in a maze by moving step-by-step through open paths without hitting walls.

S -> 1 0 0
1 -> 1 1 0
0 -> 0 1 E

S = Start, E = End, 1 = open path, 0 = blocked

Dry Run Walkthrough

Input: maze: [[1,0,0],[1,1,0],[0,1,1]], start at top-left (0,0), goal bottom-right (2,2)

Goal: Find one path from start to goal moving only on 1s

Step 1: Start at (0,0), mark path

[S] -> 0 0
1 -> 1 0
0 -> 1 E

Why: We begin from the start cell

Step 2: Move down to (1,0), path is open

S -> [1] 0
↑ -> 1 0
0 -> 1 E

Why: Down is open and closer to goal

Step 3: Move right to (1,1), path is open

S -> 0 0
1 -> [1] 0
0 -> 1 E

Why: Right is open and leads towards goal

Step 4: Move down to (2,1), path is open

S -> 0 0
1 -> 1 0
0 -> [1] E

Why: Down is open and closer to goal

Step 5: Move right to (2,2), goal reached

S -> 0 0
1 -> 1 0
0 -> 1 [E]

Why: Reached the destination

Result:

Path found: (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2)

Annotated Code

DSA Typescript

class MazeSolver {
  maze: number[][];
  n: number;
  path: number[][];

  constructor(maze: number[][]) {
    this.maze = maze;
    this.n = maze.length;
    this.path = Array.from({ length: this.n }, () => Array(this.n).fill(0));
  }

  isSafe(x: number, y: number): boolean {
    return x >= 0 && y >= 0 && x < this.n && y < this.n && this.maze[x][y] === 1;
  }

  solve(): boolean {
    if (this.solveUtil(0, 0)) {
      this.printPath();
      return true;
    } else {
      console.log('No path found');
      return false;
    }
  }

  solveUtil(x: number, y: number): boolean {
    if (x === this.n - 1 && y === this.n - 1 && this.maze[x][y] === 1) {
      this.path[x][y] = 1;
      return true;
    }

    if (this.isSafe(x, y)) {
      if (this.path[x][y] === 1) return false; // already visited

      this.path[x][y] = 1; // mark path

      if (this.solveUtil(x + 1, y)) return true; // move down

      if (this.solveUtil(x, y + 1)) return true; // move right

      this.path[x][y] = 0; // backtrack
      return false;
    }
    return false;
  }

  printPath(): void {
    let result = '';
    for (let i = 0; i < this.n; i++) {
      for (let j = 0; j < this.n; j++) {
        result += this.path[i][j] + ' ';
      }
      result += '\n';
    }
    console.log(result.trim());
  }
}

const maze = [
  [1, 0, 0],
  [1, 1, 0],
  [0, 1, 1]
];

const solver = new MazeSolver(maze);
solver.solve();

if (x === this.n - 1 && y === this.n - 1 && this.maze[x][y] === 1) {

check if current cell is goal and open

if (this.isSafe(x, y)) {

check if current cell is within bounds and open

if (this.path[x][y] === 1) return false;

avoid revisiting cells to prevent loops

this.path[x][y] = 1;

mark current cell as part of path

if (this.solveUtil(x + 1, y)) return true;

try moving down

if (this.solveUtil(x, y + 1)) return true;

try moving right

this.path[x][y] = 0;

backtrack if no path found from current cell

Output

1 0 0 

1 1 0 

0 1 1

Complexity Analysis

Time: O(2^(n*n)) because in worst case we explore all paths in the grid

Space: O(n*n) for the path matrix and recursion stack

vs Alternative: Compared to BFS which finds shortest path, this DFS approach finds one path but may be slower in large mazes

Edge Cases

Empty maze (no cells)

No path found, function returns false

DSA Typescript

if (this.isSafe(x, y)) {

Start or end cell blocked

No path found, function returns false

DSA Typescript

if (x === this.n - 1 && y === this.n - 1 && this.maze[x][y] === 1) {

Maze with no possible path

Backtracking exhausts all options, prints 'No path found'

DSA Typescript

this.path[x][y] = 0;

When to Use This Pattern

When you see a grid with blocked and open cells and need to find a path from start to end, use backtracking to explore possible routes.

Common Mistakes

Mistake: Not marking visited cells causing infinite loops
Fix: Mark cells as visited in path matrix before recursive calls

Mistake: Trying to move outside grid boundaries
Fix: Check boundaries with isSafe before moving

Summary

Finds a path through a maze from start to finish using backtracking.

Use when you need to explore all possible paths in a grid with obstacles.

The key is to try moves step-by-step and backtrack when stuck.

Practice

1. What is the main goal of the Rat in a Maze Problem in data structures and algorithms?

easy

A. Sort the cells of the maze in ascending order

B. Count the number of walls in the maze

C. Calculate the shortest distance between two points in a graph

D. Find a path from the start to the destination in a maze

Solution

1. Step 1: Understand the problem context

   The Rat in a Maze problem involves navigating through a maze represented as a grid to find a path from the start cell to the destination cell.

2. Step 2: Identify the goal

   The goal is to find a valid path that the rat can follow to reach the destination without crossing walls or blocked cells.

3. Final Answer:

   Find a path from the start to the destination in a maze -> Option D

4. Quick Check:

   Goal = Find path [OK]

Hint: Remember: Rat must find a path, not count or sort cells [OK]

Common Mistakes:

• Confusing path finding with counting walls
• Thinking the problem is about sorting cells
• Assuming shortest path is always required

2. Which of the following is the correct TypeScript syntax to declare a 2D maze array of size 4x4 filled with zeros?

easy

A. const maze: number[][] = Array.from({length: 4}, () => Array(4).fill(0));

B. const maze: number[][] = [[0]*4]*4;

C. const maze: number[][] = new Array(4, 4).fill(0);

D. const maze: number[][] = Array(4).fill(Array(4).fill(0));

Solution

1. Step 1: Understand array initialization in TypeScript

   Using Array.from with a mapping function creates independent inner arrays, avoiding reference issues.

2. Step 2: Analyze each option

   const maze: number[][] = Array(4).fill(Array(4).fill(0)); creates inner arrays by reference, causing all rows to point to the same array. const maze: number[][] = Array.from({length: 4}, () => Array(4).fill(0)); correctly creates separate arrays for each row. Options B and C use invalid syntax for 2D arrays.

3. Final Answer:

   const maze: number[][] = Array.from({length: 4}, () => Array(4).fill(0)); -> Option A

4. Quick Check:

   Correct 2D array init = const maze: number[][] = Array.from({length: 4}, () => Array(4).fill(0)); [OK]

Hint: Use Array.from with a function to avoid shared references [OK]

Common Mistakes:

• Using fill with nested arrays causing shared references
• Incorrect syntax for 2D array creation
• Confusing array size parameters

3. Given the following maze and code snippet, what will be the output?

const maze = [
  [1, 0, 0, 0],
  [1, 1, 0, 1],
  [0, 1, 0, 0],
  [1, 1, 1, 1]
];

function isSafe(x: number, y: number): boolean {
  return x >= 0 && y >= 0 && x < 4 && y < 4 && maze[x][y] === 1;
}

function solveMaze(x: number, y: number, path: string[]): boolean {
  if (x === 3 && y === 3) {
    path.push(`(${x},${y})`);
    return true;
  }
  if (isSafe(x, y)) {
    path.push(`(${x},${y})`);
    if (solveMaze(x + 1, y, path)) return true;
    if (solveMaze(x, y + 1, path)) return true;
    path.pop();
  }
  return false;
}

const path: string[] = [];
if (solveMaze(0, 0, path)) {
  console.log(path.join(' -> '));
} else {
  console.log('No path found');
}

medium

A. (0,0) -> (0,1) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)

B. (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3)

C. No path found

D. (0,0) -> (1,0) -> (2,0) -> (3,0) -> (3,1) -> (3,2) -> (3,3)

Solution

1. Step 1: Trace the recursive path from (0,0)

   Starting at (0,0), the rat moves down to (1,0) since maze[1][0] = 1. Then right to (1,1), down to (2,1), down to (3,1), right to (3,2), and right to (3,3).

2. Step 2: Verify path validity and output

   All these cells are safe (value 1). The path is recorded and printed as shown in (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3).

3. Final Answer:

   (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3) -> Option B

4. Quick Check:

   Path found = (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3) [OK]

Hint: Follow down then right moves recursively to find path [OK]

Common Mistakes:

• Assuming movement to blocked cells (0 values)
• Confusing row and column indices
• Ignoring backtracking when path fails

4. Identify the bug in the following TypeScript code snippet for the Rat in a Maze problem:

function solveMaze(x: number, y: number, path: string[]): boolean {
  if (x === 3 && y === 3) {
    path.push(`(${x},${y})`);
    return true;
  }
  if (isSafe(x, y)) {
    path.push(`(${x},${y})`);
    if (solveMaze(x + 1, y, path)) return true;
    if (solveMaze(x, y + 1, path)) return true;
    path.pop();
  }
  return false;
}

medium

A. isSafe function is not called before pushing to path

B. Incorrect base case coordinates for destination

C. Missing backtracking step to remove current cell from path when dead end is reached

D. The function should move left and up instead of right and down

Solution

1. Step 1: Analyze the recursion and path tracking

   The function adds the current cell to path but does not remove it if both recursive calls fail, causing incorrect path accumulation.

2. Step 2: Identify missing backtracking

   Backtracking requires removing the current cell from path when no path forward is found, which is missing here.

3. Final Answer:

   Missing backtracking step to remove current cell from path when dead end is reached -> Option C

4. Quick Check:

   Backtracking needed = Missing backtracking step to remove current cell from path when dead end is reached [OK]

Hint: Always pop path on dead ends to backtrack [OK]

Common Mistakes:

• Forgetting to remove cell from path on failure
• Incorrect base case coordinates
• Ignoring isSafe checks before path push

5. You want to modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to destination (N-1,N-1) in an NxN maze. Which approach should you use?

hard

A. Use backtracking to explore all safe moves, storing each complete path separately

B. Stop at the first found path and return immediately

C. Use a greedy approach to always move right or down only

D. Convert the maze to a graph and use Dijkstra's algorithm to find shortest path

Solution

1. Step 1: Understand the requirement to find all paths

   Finding all paths requires exploring every possible route without stopping at the first success.

2. Step 2: Choose backtracking to explore all safe moves

   Backtracking allows exploring all safe moves recursively, storing each complete path separately before backtracking to try other routes.

3. Final Answer:

   Use backtracking to explore all safe moves, storing each complete path separately -> Option A

4. Quick Check:

   All paths = Backtracking exploration [OK]

Hint: Backtrack fully to find all paths, not just one [OK]

Common Mistakes:

• Stopping after first path found
• Using greedy moves that miss paths
• Using shortest path algorithms instead of all paths