Rat In A Maze Problem SolvedJavaScript Backtracking

In this article we will solve Rat in a maze problem with backtracking. The rat start point is (0,0) and exit point is (n-1, n-1). The rat can move to 1 and 0 is blocked.

Diagram

Code

class Solution {
    //direction object
     direction = [
         {dir: "D", row:1, col:0},
         {dir: "L", row:0, col:-1},
         {dir: "R", row:0, col:1},
         {dir: "U", row:-1, col:0}
    ]
    isValid(r,c,maze, n){
        if(c>=0 && r>=0 && c<n && r<n && maze[r][c]!==0){
            return true
        }
        return false
    }
    
    findPath(maze, r,c,path, ans, n){
        //base condition
        if(r==n-1 && c==n-1){
            ans.push(path)
            return
        }
        //mark this cell as visited
        maze[r][c] = 0
        //move all the directions
        let d = this.direction
        for(let item of d){
            let newRow = r+item.row
            let newCol = c+item.col
            if(this.isValid(newRow, newCol, maze, n)){
               path = path + item.dir
               //find the further paths
                this.findPath(maze, newRow, newCol, path, ans, n)
               //backtrack the path
               path = path.slice(0,-1)
            }
        }
        //backtrack the visited cell
        maze[r][c] = 1
        
    }
    ratInMaze(maze) {
        // code here
        let n = maze.length
        if(maze[0][0]===0 && maze[n-1][n-1]===0){
            return []
        }
        let path = ""
        let ans = []
        let r=0
        let c=0
        this.findPath(maze, r, c, path, ans, n)
        return ans
    }
}

Time Complexity & Space Complexity

At every cell, we try 4 directions:

Down
Left
Right
Up

So from one cell → max 4 recursive calls.

Imagine the maze is:

1 1 1
1 1 1
1 1 1

No blocks at all.

From each cell you can move in up to 4 directions.

So branching factor ≈ 4.

Now how deep can recursion go?

Maximum path length = n × n

(because we cannot revisit cells)

So recursion depth ≤ n².

Worst case time complexity:

O(4(n2))O(4^{(n^2)})O(4(n2))

Why Exponential?

Because:

Each cell → 4 choices

Each next cell → 4 choices

Each next → 4 choices

So:

4×4×4×...(n2times)4 × 4 × 4 × ... (n^2 times)4×4×4×...(n2times)

That becomes:

4n24^{n^2}4n2

But Practically?

• We mark visited

• So many paths get cut early

• Real runtime much smaller

But worst case remains exponential.

Space Complexity

Now let’s calculate space usage.

Recursion Stack

Max depth = number of cells in path

=n2= n^2=n2

So stack space:

O(n2)O(n^2)O(n2)

Answer Array

If there are many valid paths, output itself can be huge.

Worst case number of paths is exponential.

So result storage =

O(number of paths×path length)O(number\ of\ paths × path\ length)O(number of paths×path length)

Worst case also exponential.

Final Answer

Time Complexity

O(4n2)O(4^{n^2})O(4n2)

(Exponential)

Space Complexity

Without counting result:

O(n2)O(n^2)O(n2)

Including result:

O(4n2)O(4^{n^2})O(4n2)

(because output itself may be exponential)