HardArrayBacktrackingBit ManipulationMatrix

Unique Paths III

1 approach, code in every language

You are given an `m x n` integer grid where each cell holds one of four values. A `1` marks the single starting square and a `2` marks the single ending square. A `0` is an empty square you are allowed to walk over, and a `-1` is an obstacle you can never enter.

Starting from the square marked `1`, you may move one step at a time up, down, left, or right to an adjacent in-bounds square that is not an obstacle. A path is considered valid only if it begins at the start, ends at the end, and walks over every non-obstacle square (the start, the end, and all empty squares) exactly once.

Return the number of distinct valid paths that satisfy this requirement.

Example 1

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

Output: 2

There are exactly two four-directional walks that visit every non-obstacle square once and finish on the ending square.

Example 2

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

Output: 0

No walk starting at the `1` can cover both remaining empty squares before landing on the `2`, so the answer is zero.

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 square and exactly one ending square.

Backtracking DFS with Remaining Counter

Count the walkable squares up front, then explore every path with depth-first search, only accepting a path that lands on the end after covering all of them.

Loading animation…

Intuition

The grid is tiny (at most 20 squares), so we can afford to explore every possible route exhaustively. The trick is knowing when a route is complete: a valid path must cover the start, the end, and every empty square exactly once. If we count the number of non-obstacle squares before we begin, we can carry a `remaining` counter that decreases by one every time we step onto a fresh square. When we finally arrive at the ending square, the path is valid precisely when `remaining` has reached zero, meaning nothing was skipped. To avoid revisiting squares within a single path, we temporarily mark each visited square as an obstacle and restore it when we backtrack.

Algorithm walkthrough

1Scan the whole grid once to count the empty squares (`0`) and remember the coordinates of the starting square (`1`).
2Set the initial `remaining` count to the number of empty squares plus one, so the start itself is included in the squares that must be covered.
3Run a DFS from the start. If the current cell is out of bounds or an obstacle, return immediately; that branch is dead.
4If the current cell is the ending square, add one to the answer only when `remaining` equals zero, then return without stepping further.
5Otherwise mark the current cell as an obstacle, recurse into all four neighbors with `remaining - 1`, and then restore the cell so sibling branches can reuse it.
6After the DFS finishes, the accumulated count is the number of valid paths.

Implementation

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        empty = 0
        start_r = start_c = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 0:
                    empty += 1
                elif grid[r][c] == 1:
                    start_r, start_c = r, c

        self.paths = 0

        def dfs(r: int, c: int, remaining: int) -> None:
            if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == -1:
                return
            if grid[r][c] == 2:
                if remaining == 0:
                    self.paths += 1
                return
            temp = grid[r][c]
            grid[r][c] = -1
            dfs(r + 1, c, remaining - 1)
            dfs(r - 1, c, remaining - 1)
            dfs(r, c + 1, remaining - 1)
            dfs(r, c - 1, remaining - 1)
            grid[r][c] = temp

        dfs(start_r, start_c, empty + 1)
        return self.paths

Time

O(3^(m*n)) in the worst case

Space

O(m*n)

Each step branches into at most three new directions (we never step back), and recursion depth is bounded by the number of squares. The grid constraint m*n <= 20 keeps this tractable.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Dynamic Programming

After the pattern

Now solve one you haven't seen.

Sweeping Every Open Bay Once is our own problem on the technique behind Unique Paths III: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free