#980

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Unique Paths III

Solve the Unique Paths III problem using backtracking search with pruning to count 4-directional paths covering all empty squares.

array backtracking bit manipulation matrix

Problem Statement

Given an m x n grid, you need to return the number of 4-directional paths from the starting square to the ending square. Each path must cover every non-obstacle square exactly once. The grid contains integers representing obstacles (-1), empty squares (0), a starting square (1), and an ending square (2).

You can move in 4 directions (up, down, left, right). Your task is to find the number of unique paths from the starting square to the ending square while ensuring that every non-obstacle square is visited exactly once.

Examples

Example 1

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

Output: 2

We have the following two paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]

Output: 4

We have the following four paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
(0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3

Input: grid = [[0,1],[2,0]]

Output: 0

There is no path that walks over every empty square exactly once. Note that the starting and ending square can be anywhere in the grid.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 20
1 <= m * n <= 20
-1 <= grid[i][j] <= 2
There is exactly one starting cell and one ending cell.

Solution Approach

Backtracking Search with Pruning

Use a backtracking approach to explore all possible paths. As you move, mark each visited square to ensure it is visited exactly once. Prune any path that revisits a square or reaches an invalid state. This helps avoid unnecessary computations.

Bit Masking for Efficient State Tracking

Represent the visited squares using a bitmask, where each bit corresponds to a square. This allows for efficient tracking of which squares have been visited without needing to modify the grid directly, reducing memory usage and increasing speed.

Recursive DFS with Base and Edge Cases

Implement a depth-first search (DFS) that recursively explores all 4 directions. Define base cases such as when the end square is reached with all squares visited. Handle edge cases such as grids with isolated empty squares that cannot be visited.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexity of the solution depend on the specific approach. In the worst case, the backtracking approach explores all possible paths, resulting in an exponential time complexity. Using bit masking reduces space complexity and speeds up state tracking.

What Interviewers Usually Probe

Evaluate the candidate's ability to implement a backtracking solution efficiently.
Assess whether the candidate can use bit manipulation to optimize the solution.
Check if the candidate handles base and edge cases effectively in the DFS.

Common Pitfalls or Variants

Common pitfalls

Failing to prune invalid paths early, leading to excessive backtracking and inefficient computation.
Not correctly tracking visited squares, either revisiting squares or missing some.
Overcomplicating the solution by not using bit masking for efficient state tracking.

Follow-up variants

Implementing a non-recursive version of the backtracking approach using an explicit stack.
Extending the problem to grids with multiple starting and ending points.
Considering non-square grids with arbitrary shapes and obstacles.

FAQ

How can I optimize the solution for Unique Paths III?

Use backtracking with pruning to eliminate invalid paths early. Bit masking can also help efficiently track visited squares, improving both time and space complexity.

What is the main challenge in solving Unique Paths III?

The main challenge is ensuring that every non-obstacle square is visited exactly once, while efficiently pruning invalid paths to avoid excessive backtracking.

Can the Unique Paths III problem be solved with dynamic programming?

While dynamic programming can be useful in some pathfinding problems, this one requires a more flexible approach, such as backtracking with pruning, to handle all the constraints.

How does pruning improve performance in this problem?

Pruning helps by eliminating paths that are guaranteed to fail early in the search process, reducing unnecessary computations and improving overall efficiency.

What is the purpose of bit masking in Unique Paths III?

Bit masking allows efficient tracking of visited squares without modifying the grid, reducing memory usage and speeding up the process of checking if all squares are visited.

terminal

Solution

Solution 1: Backtracking

We can first traverse the entire grid, find the starting point $(x, y)$, and count the number of blank spaces $cnt$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        def dfs(i: int, j: int, k: int) -> int:
            if grid[i][j] == 2:
                return int(k == cnt + 1)
            ans = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and (x, y) not in vis and grid[x][y] != -1:
                    vis.add((x, y))
                    ans += dfs(x, y, k + 1)
                    vis.remove((x, y))
            return ans

        m, n = len(grid), len(grid[0])
        start = next((i, j) for i in range(m) for j in range(n) if grid[i][j] == 1)
        dirs = (-1, 0, 1, 0, -1)
        cnt = sum(row.count(0) for row in grid)
        vis = {start}
        return dfs(*start, 0)

Continue Practicing

#996 number of squareful arrays #864 shortest path to get all keys #861 score after flipping matrix