Rat in a Maze Problem in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal in the Rat in a Maze problem?

To find a path from the start point (usually top-left) to the destination (usually bottom-right) in a maze represented by a grid, moving only through allowed cells.

beginner

Which algorithmic technique is commonly used to solve the Rat in a Maze problem?

Backtracking is used to explore all possible paths and backtrack when a path leads to a dead end.

beginner

In the Rat in a Maze problem, what does a cell value of 0 usually represent?

A blocked or forbidden cell where the rat cannot move.

intermediate

Why do we mark cells as visited in the Rat in a Maze problem?

To avoid revisiting the same cell and getting stuck in infinite loops during the search.

advanced

What is the time complexity of the Rat in a Maze problem using backtracking on an N x N grid?

O(2^(N*N)) in the worst case, because each cell can be either visited or not, leading to exponential possibilities.

In the Rat in a Maze problem, which move directions are typically allowed?

A Only Diagonal moves

B Up, Down, Left, Right

C Up and Left only

D No moves allowed

The rat can usually move up, down, left, or right to adjacent cells.

What does a backtracking algorithm do when it hits a dead end in the maze?

A Moves diagonally

B Stops immediately

C Marks the maze as unsolvable

D Returns to previous cell and tries a different path

Backtracking returns to the previous cell to try other possible paths.

If the maze is represented by a 2D array, what does a '1' usually mean?

A Allowed path cell

B Start point only

C Blocked cell

D Destination only

A '1' indicates the cell is open and the rat can move through it.

Which data structure is most useful to implement the Rat in a Maze backtracking solution?

A Queue

B Hash Map

C Stack (implicit via recursion)

D Linked List

Backtracking uses recursion which implicitly uses a call stack.

What is the base case in the recursive Rat in a Maze solution?

A When the rat reaches the destination cell

B When the rat moves out of the maze

C When the rat visits a blocked cell

D When the maze is empty

The recursion stops when the rat reaches the destination cell.

Explain how backtracking helps solve the Rat in a Maze problem.

Think about exploring paths and undoing moves when stuck.

Describe how you would represent the maze and track the rat's path in code.

Consider how to know where the rat can go and where it has been.

Practice

1. What is the main goal of the Rat in a Maze problem in algorithms?

easy

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

B. Count the number of walls in the maze

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

D. Sort the maze cells in ascending order

Solution

1. Step 1: Understand the problem objective

   The Rat in a Maze problem requires finding a path from the start cell to the destination cell in a maze grid.

2. Step 2: Identify the correct goal

   The goal is not counting walls, sorting cells, or shortest distance in a graph, but specifically finding a valid path through the maze.

3. Final Answer:

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

4. Quick Check:

   Goal = Find path [OK]

Hint: Focus on pathfinding from start to end in the maze [OK]

Common Mistakes:

• Confusing pathfinding with counting or sorting
• Thinking it's about shortest path always
• Assuming maze cells need sorting

2. Which of the following is the correct way to check if a cell (x, y) is safe to move in a maze represented by a 2D array maze in JavaScript?

easy

A. if (x >= 0 && y >= 0 && x <= maze.length && y <= maze[0].length && maze[x][y] === 0)

B. if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1)

C. if (x > 0 && y > 0 && x <= maze.length && y <= maze[0].length && maze[x][y] === 1)

D. if (x > 0 && y > 0 && x < maze.length && y < maze[0].length && maze[x][y] === 0)

Solution

1. Step 1: Check boundary conditions correctly

   Valid indices in JavaScript arrays start at 0 and go up to length - 1, so conditions must use >= 0 and < length.

2. Step 2: Check cell value for path

   In the Rat in a Maze problem, 1 usually means path is open, so maze[x][y] === 1 is correct.

3. Final Answer:

   if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) -> Option B

4. Quick Check:

   Boundary + path check = if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) [OK]

Hint: Use >= 0 and < length for array bounds, check for 1 as path [OK]

Common Mistakes:

• Using > 0 excludes index 0
• Using <= length causes out-of-bound errors
• Checking for 0 instead of 1 as path

3. What will be the output of the following JavaScript code snippet for the Rat in a Maze problem?

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

function solveMaze(x, y, maze, path) {
  if (x === maze.length - 1 && y === maze[0].length - 1) {
    path.push([x, y]);
    return true;
  }
  if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) {
    path.push([x, y]);
    maze[x][y] = 0;
    if (solveMaze(x + 1, y, maze, path)) return true;
    if (solveMaze(x, y + 1, maze, path)) return true;
    path.pop();
    return false;
  }
  return false;
}

const path = [];
solveMaze(0, 0, maze, path);
console.log(path);

medium

A. [[0,0],[0,1],[1,1],[2,1],[3,1],[3,2],[3,3]]

B. []

C. [[0,0],[1,0],[1,1],[1,2],[2,2],[3,2],[3,3]]

D. [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]]

Solution

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

   Starting at (0,0), the function tries moving down (x+1,y) first, then right (x,y+1). It marks visited cells as 0 to avoid revisiting.

2. Step 2: Follow the path found

   The path found is (0,0) -> (1,0) -> (1,1) -> (2,1) -> (3,1) -> (3,2) -> (3,3), which is a valid path to the destination.

3. Final Answer:

   [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]] -> Option D

4. Quick Check:

   Path traced matches [[0,0],[1,0],[1,1],[2,1],[3,1],[3,2],[3,3]] [OK]

Hint: Follow down moves first, then right moves recursively [OK]

Common Mistakes:

• Assuming right moves tried before down
• Not marking visited cells causing infinite loops
• Misreading maze cell values

4. Identify the bug in the following JavaScript code snippet for the Rat in a Maze problem and select the fix.

function solveMaze(x, y, maze, path) {
  if (x === maze.length - 1 && y === maze[0].length - 1) {
    path.push([x, y]);
    return true;
  }
  if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] === 1) {
    path.push([x, y]);
    if (solveMaze(x + 1, y, maze, path)) return true;
    if (solveMaze(x, y + 1, maze, path)) return true;
    path.pop();
    return false;
  }
  return false;
}

medium

A. Mark visited cells as 0 after pushing to path to avoid revisiting

B. Remove path.pop() to keep all visited cells in path

C. Change base case to check if x > maze.length and y > maze[0].length

D. Add a check to move diagonally (x+1, y+1) in recursion

Solution

1. Step 1: Identify missing visited marking

   The code does not mark visited cells as 0, so it may revisit the same cell causing infinite recursion.

2. Step 2: Fix by marking visited cells

   After pushing a cell to path, mark maze[x][y] = 0 to avoid revisiting and infinite loops.

3. Final Answer:

   Mark visited cells as 0 after pushing to path to avoid revisiting -> Option A

4. Quick Check:

   Visited marking fixes infinite recursion [OK]

Hint: Mark visited cells to prevent infinite loops [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Removing path.pop() causing wrong paths
• Changing base case incorrectly

5. Given a maze represented by a 2D array where 1 means open path and 0 means blocked, how would you modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to destination (n-1,n-1)?

hard

A. Use backtracking to explore all directions and store each complete path in a list

B. Stop recursion after finding the first path and return it immediately

C. Use a queue to perform breadth-first search and return the shortest path only

D. Mark all visited cells permanently to avoid revisiting any cell

Solution

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

   Finding all paths means exploring every possible route from start to destination without stopping at the first success.

2. Step 2: Use backtracking to explore all paths

   Backtracking allows exploring all directions, storing each valid path, and backtracking to try other routes.

3. Final Answer:

   Use backtracking to explore all directions and store each complete path in a list -> Option A

4. Quick Check:

   All paths require full backtracking exploration [OK]

Hint: Backtrack fully and save each path to find all solutions [OK]

Common Mistakes:

• Stopping after first path found
• Using BFS only for shortest path
• Marking visited cells permanently blocking other paths