Unique Paths III | Backtracking Solution Explained

LeetCode 980. Unique Paths III. We are going to look at the backtracking approach in detail using visuals to aid in explanation. Problem Link.

0. Unique Paths III: Problem Discussion

We are given a m*n grid, with 4 kinds of cells:

• blue: normal cells
• yellow: starting cell (only 1)
• green: ending cell (only 1)
• red: obstacle cells

Our goal is to find the number of paths following the conditions:

• start: start from the yellow point
• end: end at the green point
• avoid all the obstacles
• all cells should be visited exactly once

For the example case above, there are two possible paths:

1. Unique Paths III: Logic

1.0. Intuitions

• Since we want to traverse a grid, we should start thinking in terms of a traversal algorithm. I prefer DFS, since it is quick and easy to type out, for a start.
• We thus start dfs from the given start point and set the base case, the end condition in this case, to be the end point.
• We also want to keep a track of all the cells we have visited, and for that, we can have a third parameter in the dfs.
• Formalization: dfs(x, y, count)

If you implement just this, you will get almost all of the code as the final solution (check in section 2). All, except for one line, visited[x][y] = 0.

And to understand the line, we have to dive into what backtracking means.

1.2. Backtracking Intuitions

From any point (dark blue in this case) we have 3 more directions we can explore in. At any point in time, we don’t know which direction will lead us to a path that reaches the end following all the conditions.
So what do we do?

Let’s say we pick the choice of going up. As we move again, we keep on marking the path we took as visited. This helps avoid loops.

What if we end up at a grid boundary? We can’t move from there. What do we do then?

It seems as if we need a way to go back. We want to say that you know what, I don’t want to take this route, and I want to go back at the point I made the last decision, and instead take right

To do that, in dfs, we can add one more line: visited[x][y] = 0 as:

        # BACKTRACKING LOGIC
        def dfs(x, y, count):
            # base case handling here
            
            visited[x][y] = 1
            dfs(x+1, y, count+1)
            dfs(x-1, y, count+1)
            dfs(x, y+1, count+1)
            dfs(x, y-1, count+1)
            visited[x][y] = 0 # Added line

Which unvisits the path that we just took. This way, when the dfs returns, it is as if we never took the path we just took! The grid is reset in those locations.

2. Unique Paths III: Code

2.0. Code

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        # SETUP
        m, n = len(grid), len(grid[0])
        cells = 0
        start = None
        end = None
        for x in range(m):
            for y in range(n):
                if grid[x][y] != -1: cells += 1
                if grid[x][y] == 1: start = (x, y)
                if grid[x][y] == 2: end = (x, y)
                    
        # BACKTRACKING LOGIC
        def dfs(x, y, count):
            nonlocal ans
            if (x, y) == end: 
                if count == cells: ans += 1
                return
            if not (0 <= x < m and 0 <= y < n) or visited[x][y] or grid[x][y] == -1: 
                return
            
            visited[x][y] = 1
            dfs(x+1, y, count+1)
            dfs(x-1, y, count+1)
            dfs(x, y+1, count+1)
            dfs(x, y-1, count+1)
            visited[x][y] = 0

        # PREP FOR BACKTRACKING 
        visited = [[0]*n for _ in range(m)]
        ans = 0
        dfs(start[0], start[1], 1)
        return ans

2.1. Complexity Analysis

• Time: O(3^MN). It may seem as if we are going in all the 4 directions from each point, but recall how we always have one path marked visited. Why? That’s the path we came from.
• Space: O(MN). We keep a track of visited array. Note that even if we do an in-place modification, we still would incur the cost of the recursion call stack height, which is O(MN). So we have O(MN) space complexity regardless of extra visited array or an in-place modification.

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.