Rat in a Maze Problem in DSA Java - Time & Space Complexity

Time Complexity: Rat in a Maze Problem

O(4^n)

Understanding Time Complexity

We want to understand how the time needed to solve the Rat in a Maze problem changes as the maze size grows.

Specifically, how does the search through the maze scale with its size?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public boolean solveMaze(int[][] maze, int x, int y, int n) {
    if (x == n - 1 && y == n - 1) return true;
    if (isSafe(maze, x, y, n)) {
        maze[x][y] = 1; // mark as part of path
        if (solveMaze(maze, x + 1, y, n)) return true;
        if (solveMaze(maze, x, y + 1, n)) return true;
        maze[x][y] = 0; // backtrack
    }
    return false;
}

This code tries to find a path from the top-left to the bottom-right of an n x n maze using backtracking.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls exploring possible moves (down and right) at each cell.
• How many times: Potentially, each cell can be visited multiple times during backtracking, exploring many paths.

How Execution Grows With Input

As the maze size n grows, the number of possible paths grows very fast because the rat can move down or right at each step.

Input Size (n)	Approx. Operations
2	Few (around 2 paths)
4	Many more (around 20 paths)
10	Very many (thousands of paths)

Pattern observation: The number of paths grows exponentially as n increases, making the search much longer.

Final Time Complexity

Time Complexity: O(2^{2n}) or equivalently O(4^n)

This means the time needed can grow extremely fast, roughly quadrupling for each increase in maze size n.

Common Mistake

[X] Wrong: "The algorithm only checks one path, so it runs in linear time."

[OK] Correct: The algorithm tries many possible paths using recursion and backtracking, which can explore an exponential number of routes before finding a solution or concluding none exists.

Interview Connect

Understanding this problem helps you think about how recursive backtracking explores many possibilities and why some problems can take a long time to solve as input grows.

Self-Check

"What if we allowed the rat to move in all four directions (up, down, left, right)? How would the time complexity change?"

Practice

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

easy

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

B. Count the number of walls in the maze

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

D. Sort the maze cells in ascending order

Solution

1. Step 1: Understand the problem goal

   The Rat in a Maze problem asks to find a path from the start cell (usually top-left) to the destination cell (usually bottom-right) in a maze represented by a grid.

2. Step 2: Identify the correct goal

   Among the options, only finding a path from start to destination matches the problem's main goal.

3. Final Answer:

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

4. Quick Check:

   Goal = Find path [OK]

Hint: Remember: Rat must find a path through the maze [OK]

Common Mistakes:

• Confusing path finding with counting walls
• Thinking it's about sorting or distances
• Ignoring the start and destination points

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 Java?

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] == 0)

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] == 1)

Solution

1. Step 1: Check valid indices in 2D array

   Indices must be >= 0 and less than maze.length and maze[0].length to avoid ArrayIndexOutOfBoundsException.

2. Step 2: Check if cell is open (usually 1 means open)

   We check if maze[x][y] == 1 to confirm the cell is safe to move.

3. Final Answer:

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

4. Quick Check:

   Bounds + open cell = if (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 1) [OK]

Hint: Check indices >=0 and < length, and cell == 1 [OK]

Common Mistakes:

• Using > 0 instead of >= 0 causes skipping first row/column
• Using <= length causes index out of bounds
• Checking for 0 instead of 1 for open path

3. What will be the output path for the following maze if the rat starts at (0,0) and destination is (1,2)?

int[][] maze = {
  {1, 0, 0},
  {1, 1, 1}
};

Assuming the rat moves only right or down and marks path cells with 2, what is the maze after the path is found?

medium

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

B. [[2, 0, 0], [2, 2, 2]]

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

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

Solution

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

   Start at (0,0) which is 1, move down to (1,0) = 1, then right to (1,1) = 1, then right to (1,2) = 1.

2. Step 2: Mark the path cells with 2

   Mark (0,0), (1,0), (1,1), (1,2) as 2. Other cells remain unchanged.

3. Final Answer:

   [[2, 0, 0], [2, 2, 2]] -> Option B

4. Quick Check:

   Path marked with 2 = [[2, 0, 0], [2, 2, 2]] [OK]

Hint: Follow path down then right, mark visited cells [OK]

Common Mistakes:

• Marking cells not in path
• Confusing 0 and 1 cells
• Not marking start cell

4. Given the following code snippet for the Rat in a Maze problem, what is the error?

boolean solveMaze(int[][] maze, int x, int y, int[][] solution) {
  if (x == maze.length - 1 && y == maze[0].length - 1) {
    solution[x][y] = 1;
    return true;
  }
  if (x < maze.length && y < maze[0].length && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return true;
    if (solveMaze(maze, x, y + 1, solution)) return true;
    solution[x][y] = 0;
    return false;
  }
  return false;
}

medium

A. No base case for destination cell

B. Solution array is not updated correctly

C. Missing check for x and y >= 0 before accessing maze[x][y]

D. Recursive calls do not explore all directions

Solution

1. Step 1: Analyze boundary checks before accessing maze

   The code checks if x < maze.length and y < maze[0].length but does not check if x >= 0 and y >= 0, which can cause ArrayIndexOutOfBoundsException if negative indices occur.

2. Step 2: Verify other parts of the code

   The base case for destination exists, solution array updates correctly, and recursive calls explore down and right directions as expected.

3. Final Answer:

   Missing check for x and y >= 0 before accessing maze[x][y] -> Option C

4. Quick Check:

   Bounds must include >= 0 [OK]

Hint: Always check indices >= 0 and < length before access [OK]

Common Mistakes:

• Ignoring negative index checks
• Assuming base case is missing
• Thinking solution array update is wrong

5. You have a 4x4 maze represented as:

int[][] maze = {
  {1, 0, 0, 0},
  {1, 1, 0, 1},
  {0, 1, 0, 0},
  {1, 1, 1, 1}
};

If the rat can move in all four directions (up, down, left, right) but cannot visit the same cell twice, which of the following is the correct path the rat can take from (0,0) to (3,3)?

hard

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

B. [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)]

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

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

Solution

1. Step 1: Trace possible path from (0,0) to (3,3) moving up/down/left/right

   Start at (0,0), move down to (1,0), right to (1,1), down to (2,1), down to (3,1), right to (3,2), right to (3,3). All cells are 1 and not visited twice.

2. Step 2: Verify other options for invalid moves or blocked cells

   [(0,0), (0,1), (1,1), (2,1), (3,1), (3,2), (3,3)] moves to (0,1) which is 0 (blocked). [(0,0), (1,0), (2,0), (3,0), (3,1), (3,2), (3,3)] moves to (2,0) which is 0. [(0,0), (1,0), (1,1), (1,2), (2,2), (3,2), (3,3)] moves to (1,2) which is 0. So only [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] is valid.

3. Final Answer:

   [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] -> Option A

4. Quick Check:

   Valid path with allowed moves = [(0,0), (1,0), (1,1), (2,1), (3,1), (3,2), (3,3)] [OK]

Hint: Check cell value 1 and no repeats in path [OK]

Common Mistakes:

• Choosing paths through blocked cells (0)
• Revisiting same cell twice
• Ignoring allowed movement directions