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
- 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.
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
class Solution: def uniquePathsIII(self, grid: List[List[int]]) -> int: # SETUP m, n = len(grid), len(grid) 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 = [*n for _ in range(m)] ans = 0 dfs(start, start, 1) return ans
2.1. Complexity Analysis
- Time: O(3MN). 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.
June 13, 2022