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

Time Complexity: Rat in a Maze Problem

O(2^{n^2})

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 for a path through the maze take longer when the maze gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function solveMaze(maze: number[][], x: number, y: number, solution: number[][]): boolean {
  const n = maze.length;
  if (x === n - 1 && y === n - 1) {
    solution[x][y] = 1;
    return true;
  }
  if (x >= 0 && y >= 0 && x < n && y < n && 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;
}
    

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

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls exploring each cell in the maze.
• How many times: Potentially, each cell is visited multiple times during backtracking.

How Execution Grows With Input

As the maze size grows, the number of possible paths grows very fast because the rat can move in multiple directions at each step.

Input Size (n)	Approx. Operations
2	Few recursive calls, easy to check all paths.
5	Many more paths to explore, operations increase quickly.
10	Huge number of possible paths, operations grow very fast.

Pattern observation: The time grows very fast, much faster than just doubling or squaring; it grows exponentially with maze size.

Final Time Complexity

Time Complexity: O(2^{n^2})

This means the time needed can grow extremely fast as the maze size increases, because the rat tries many possible paths.

Common Mistake

[X] Wrong: "The rat only moves forward, so time grows linearly with maze size."

[OK] Correct: The rat can move in multiple directions and backtrack, so many paths are checked, making the time grow much faster than linear.

Interview Connect

Understanding this problem helps you think about how exploring many options affects time, a skill useful for many search and path problems.

Self-Check

"What if we added a rule that the rat can only move right or down? How would the time complexity change?"