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

Time Complexity: Rat in a Maze Problem

O(2^(n*n))

Understanding Time Complexity

We want to know 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.

bool solveMaze(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N-1 && y == N-1) {
        sol[x][y] = 1;
        return true;
    }
    if (isSafe(maze, x, y)) {
        sol[x][y] = 1;
        if (solveMaze(maze, x+1, y, sol)) return true;
        if (solveMaze(maze, x, y+1, sol)) return true;
        sol[x][y] = 0; // backtrack
    }
    return false;
}
    

This code tries to find a path from the start to the end of the maze by moving right or down recursively.

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 every cell is visited multiple times due to backtracking.

How Execution Grows With Input

As the maze size (n x n) grows, the number of paths to explore grows very fast because the rat can move right or down at each step.

Input Size (n)	Approx. Operations
2	About 2 paths to check
4	About 20 paths to check
10	Thousands of paths to check

Pattern observation: The number of paths grows exponentially as the maze size increases.

Final Time Complexity

Time Complexity: O(2^(n*n))

This means the time needed grows very fast, roughly doubling with each increase in maze size.

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, so it explores many combinations, not just one.

Interview Connect

Understanding how recursive backtracking explores many possibilities helps you solve complex pathfinding problems and shows your grasp of algorithm growth.

Self-Check

"What if we allowed the rat to move in all four directions instead of just right and down? How would the time complexity change?"

Practice

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

easy

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

B. Count the number of walls in the maze

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

D. Fill the maze with numbers

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the goal

   The goal is to find any valid path through open cells (usually marked 1) avoiding blocked cells (usually marked 0).

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: Look for pathfinding from start to end in the maze [OK]

Common Mistakes:

• Thinking it's about counting walls
• Confusing with shortest path calculation
• Assuming maze filling is required

2. Which of the following is the correct way to declare the maze matrix in C for a 4x4 maze?

easy

A. int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}};

B. int maze[4] = {1,0,0,0,1,1,0,1,0,1,0,0,1,1,1,1};

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

D. int maze[4][4] = {1,0,0,0,1,1,0,1,0,1,0,0,1,1,1};

Solution

1. Step 1: Understand C array declaration syntax

   In C, a 2D array must have both dimensions specified except for the first dimension if initialized immediately. Here, both dimensions are specified as 4.

2. Step 2: Check initialization format

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; correctly declares a 4x4 int array with nested braces for each row.

3. Final Answer:

   int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; -> Option A

4. Quick Check:

   Correct 2D array syntax = int maze[4][4] = {{1,0,0,0},{1,1,0,1},{0,1,0,0},{1,1,1,1}}; [OK]

Hint: Use nested braces for each row in 2D array initialization [OK]

Common Mistakes:

• Omitting second dimension size
• Using single braces for all elements
• Declaring incomplete array sizes

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

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

int solution[4][4] = {0};

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    solution[x][y] = 0;
    return 0;
  }
  return 0;
}

int main() {
  if (solveMaze(maze, 0, 0, solution)) {
    for (int i = 0; i < 4; i++) {
      for (int j = 0; j < 4; j++) {
        printf("%d ", solution[i][j]);
      }
      printf("\n");
    }
  } else {
    printf("No path found\n");
  }
  return 0;
}

medium

A. 1 0 0 0
0 1 0 0
0 1 0 0
0 1 1 1

B. 1 0 0 0
1 1 0 1
0 1 0 0
1 1 1 1

C. No path found

D. 1 0 0 0
1 1 0 0
0 1 0 0
0 1 1 1

Solution

1. Step 1: Trace the recursive calls

   The function tries to move right (x+1, y) first, then down (x, y+1). It marks path cells in solution matrix if maze cell is 1.

2. Step 2: Follow the path found

   Starting at (0,0), path moves down to (1,0), then right to (1,1), down to (2,1), down to (3,1), right to (3,2), right to (3,3). This path is marked with 1s in solution.

3. Final Answer:

   1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 -> Option D

4. Quick Check:

   Path marked in solution matrix = 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 [OK]

Hint: Trace recursion path marking 1s in solution matrix [OK]

Common Mistakes:

• Confusing row and column indices
• Assuming path includes blocked cells
• Ignoring backtracking step

4. Identify the bug in the following solveMaze function and select the correct fix.

int solveMaze(int maze[4][4], int x, int y, int solution[4][4]) {
  if (x == 3 && y == 3 && maze[x][y] == 1) {
    solution[x][y] = 1;
    return 1;
  }
  if (x >= 0 && x < 4 && y >= 0 && y < 4 && maze[x][y] == 1) {
    solution[x][y] = 1;
    if (solveMaze(maze, x + 1, y, solution)) return 1;
    if (solveMaze(maze, x, y + 1, solution)) return 1;
    return 0;
  }
  return 0;
}

medium

A. Change base case to check (x == 4 && y == 4)

B. Add backtracking step: set solution[x][y] = 0 before returning 0

C. Remove the check maze[x][y] == 1

D. Change recursive calls order to (x, y + 1) then (x + 1, y)

Solution

1. Step 1: Identify missing backtracking

   The function marks solution[x][y] = 1 but does not reset it to 0 if path fails, causing incorrect path marking.

2. Step 2: Fix by adding backtracking

   Before returning 0, set solution[x][y] = 0 to unmark the cell and allow other paths to be explored.

3. Final Answer:

   Add backtracking step: set solution[x][y] = 0 before returning 0 -> Option B

4. Quick Check:

   Backtracking needed to unmark path [OK]

Hint: Always unmark path cell if dead end found [OK]

Common Mistakes:

• Forgetting to unmark solution cell
• Incorrect base case coordinates
• Changing recursion order without reason

5. Given a 5x5 maze where 0 represents blocked cells and 1 represents open cells, how would you modify the Rat in a Maze algorithm to find all possible paths from start (0,0) to end (4,4)?

hard

A. Modify the function to explore all directions and store each valid path in a list

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

C. Use a queue instead of recursion to find one path only

D. Change maze values from 1 to 2 to mark visited cells permanently

Solution

1. Step 1: Understand requirement to find all paths

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

2. Step 2: Modify algorithm to explore all directions and store paths

   Change recursion to continue after finding a path, store each valid path in a list or array, and backtrack properly to explore other routes.

3. Final Answer:

   Modify the function to explore all directions and store each valid path in a list -> Option A

4. Quick Check:

   All paths require full exploration [OK]

Hint: Explore all routes and save paths, don't stop at first success [OK]

Common Mistakes:

• Stopping after first path found
• Marking visited cells permanently blocking other paths
• Using BFS without path storage