Rat in a Maze Problem in DSA Go - 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 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.

func solveMaze(maze [][]int, x, y int, solution [][]int) bool {
    if x == len(maze)-1 && y == len(maze[0])-1 {
        solution[x][y] = 1
        return true
    }
    if x >= 0 && y >= 0 && x < len(maze) && y < len(maze[0]) && 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
}

This code tries to find a path from the top-left to the bottom-right of a maze by moving right or down recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls exploring possible paths in the maze.
• How many times: Potentially, each cell is visited multiple times as the function tries different paths.

How Execution Grows With Input

As the maze size increases, the number of possible paths grows very fast because the rat can try many routes.

Input Size (n x n)	Approx. Operations
2 x 2	About 2 to 4 tries
4 x 4	About 70 tries
10 x 10	Thousands of tries

Pattern observation: The number of tries grows very fast, much faster than the maze size itself.

Final Time Complexity

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

This means the time needed roughly quadruples for each unit increase in maze size n, making it very slow for big mazes.

Common Mistake

[X] Wrong: "The rat only tries one path, so time grows linearly with maze size."

[OK] Correct: The rat tries many paths by moving right or down, so the number of tries grows very fast, not just one path.

Interview Connect

Understanding this problem helps you think about how recursive searches explore many options and why some problems can be very slow without shortcuts.

Self-Check

"What if we added the ability to move up and left as well? How would the time complexity change?"

Practice

1. What is the main goal of the Rat in a Maze Problem in Data Structures & 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 context

   The Rat in a Maze problem involves navigating through a maze represented by 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 any valid path that the rat can take 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 C

4. Quick Check:

   Goal = Find path [OK]

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

Common Mistakes:

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

2. Which of the following Go function signatures correctly represents a recursive function to solve the Rat in a Maze problem?

easy

A. func solveMaze(maze [][]int, x, y int) bool

B. func solveMaze(maze []int, x int) int

C. func solveMaze(maze [][]int) string

D. func solveMaze(x, y int) [][]int

Solution

1. Step 1: Analyze function parameters for maze solving

   The function should accept the maze as a 2D slice and current coordinates (x, y) to explore recursively.

2. Step 2: Check return type for success indication

   The function returns a boolean indicating if a path exists from current position to destination.

3. Final Answer:

   func solveMaze(maze [][]int, x, y int) bool -> Option A

4. Quick Check:

   Correct signature = func solveMaze(maze [][]int, x, y int) bool [OK]

Hint: Look for 2D maze and bool return for path found [OK]

Common Mistakes:

• Using 1D slice instead of 2D for maze
• Wrong return type like int or string
• Missing current position parameters

3. What will be the output of the following Go code snippet for a 2x2 maze where all cells are open (1)?

package main
import "fmt"

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        (*path)[x][y] = 1
        return true
    }
    if x >= 0 && y >= 0 && x < n && y < n && maze[x][y] == 1 {
        (*path)[x][y] = 1
        if solveMaze(maze, x+1, y, path) {
            return true
        }
        if solveMaze(maze, x, y+1, path) {
            return true
        }
        (*path)[x][y] = 0
        return false
    }
    return false
}

func main() {
    maze := [][]int{{1,1},{1,1}}
    path := [][]int{{0,0},{0,0}}
    if solveMaze(maze, 0, 0, &path) {
        fmt.Println(path)
    } else {
        fmt.Println("No path found")
    }
}

medium

A. [[1 0] [1 1]]

B. [[1 1] [0 1]]

C. [[1 1] [1 1]]

D. No path found

Solution

1. Step 1: Trace the recursive calls on 2x2 maze

   Starting at (0,0), mark path[0][0]=1, try moving down (1,0), mark path[1][0]=1, then try moving right (1,1), mark path[1][1]=1 and reach destination.

2. Step 2: Backtrack if needed and finalize path matrix

   Right move from (0,0) to (0,1) is also possible but the code tries down first. The final path marks (0,0), (1,0), and (1,1) as 1, and (0,1) as 0.

3. Final Answer:

   [[1 0] [1 1]] -> Option A

4. Quick Check:

   Path matrix = [[1 0] [1 1]] [OK]

Hint: Follow recursion order: down first, then right [OK]

Common Mistakes:

• Assuming path includes (0,1) first
• Confusing path matrix with maze matrix
• Ignoring backtracking step

4. Identify the bug in this Go code snippet for the Rat in a Maze problem:

func solveMaze(maze [][]int, x, y int, path *[][]int) bool {
    n := len(maze)
    if x == n-1 && y == n-1 {
        (*path)[x][y] = 1
        return true
    }
    if x < 0 || y < 0 || x >= n || y >= n || maze[x][y] == 0 {
        return false
    }
    (*path)[x][y] = 1
    if solveMaze(maze, x+1, y, path) || solveMaze(maze, x, y+1, path) {
        return true
    }
    (*path)[x][y] = 0
    return false
}

medium

A. Using pointer for path is unnecessary

B. Missing backtracking step to reset path[x][y] to 0

C. Wrong maze boundary checks

D. Incorrect base case for destination cell

Solution

1. Step 1: Review path marking and backtracking logic

   The code marks path[x][y] = 1 when visiting but never resets it to 0 if path fails, causing incorrect path recording.

2. Step 2: Identify missing backtracking step

   Backtracking requires resetting path[x][y] = 0 before returning false to allow other paths to be explored correctly.

3. Final Answer:

   Missing backtracking step to reset path[x][y] to 0 -> Option B

4. Quick Check:

   Backtracking reset missing = Missing backtracking step to reset path[x][y] to 0 [OK]

Hint: Always reset path on failure to backtrack [OK]

Common Mistakes:

• Forgetting to reset path cell on dead end
• Misplacing base case condition
• Ignoring boundary checks

5. Given a 4x4 maze represented as:

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

Which path matrix will correctly represent a valid path from top-left (0,0) to bottom-right (3,3) using the Rat in a Maze algorithm?

hard

A. [[1 0 0 0] [1 1 0 0] [0 0 0 0] [0 1 1 1]]

B. [[1 0 0 0] [0 1 0 0] [0 1 0 0] [0 1 1 1]]

C. [[1 0 0 0] [1 0 0 0] [0 1 0 0] [1 1 1 1]]

D. [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]]

Solution

1. Step 1: Trace the valid path through the maze

   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), and right to (3,3).

2. Step 2: Mark path cells as 1 and others as 0

   Mark these cells in the path matrix as 1, others remain 0. This matches [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] exactly.

3. Final Answer:

   [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] -> Option D

4. Quick Check:

   Valid path marked = [[1 0 0 0] [1 1 0 0] [0 1 0 0] [0 1 1 1]] [OK]

Hint: Follow open cells from start to end marking path [OK]

Common Mistakes:

• Marking blocked cells as path
• Skipping valid moves down or right
• Confusing path matrix with maze layout