LeetCode 980 - Unique Paths III

LeetCode Problem 980

Difficulty: 🔴 Hard
Topics: Array, Backtracking, Bit Manipulation, Matrix

Solution

Problem Understanding

This problem asks us to count the number of valid paths in a grid under very strict movement rules. We are given a matrix where each cell has a special meaning:

• 1 is the starting position
• 2 is the ending position
• 0 is an empty square we may walk on
• -1 is an obstacle that cannot be visited

We may move only in four directions: up, down, left, and right.

The important requirement is not simply reaching the ending square. A valid path must visit every non-obstacle square exactly once. This means the path behaves like a Hamiltonian path over all traversable cells in the grid.

The input size is relatively small in terms of total cells:

1 <= m * n <= 20

This constraint is extremely important. A grid with at most 20 cells suggests that exponential algorithms may still be feasible, especially with pruning or backtracking.

The output is a single integer representing the total number of valid paths from the start to the end that satisfy all conditions.

Several edge cases are important:

• The start and end may appear anywhere in the grid.
• Obstacles may isolate regions of the board.
• Some grids may have no valid path at all.
• A path that reaches the ending square too early is invalid because every empty square must still be visited.
• The start square also counts as a square that must be visited exactly once.
• The ending square must be visited exactly once, and only after all other valid cells have been covered.

A naive implementation can easily make mistakes by:

• revisiting cells,
• stopping as soon as the ending square is reached,
• forgetting to count the starting square,
• or failing to backtrack correctly.

Approaches

Brute Force Approach

The brute-force solution tries every possible path starting from the starting square. At each step, it recursively explores all four directions and tracks which cells have already been visited.

Whenever the recursion reaches the ending square, it checks whether every non-obstacle square has been visited exactly once. If yes, the path contributes 1 to the answer.

This approach is correct because it systematically enumerates every possible walk that obeys the movement rules.

However, the search space grows extremely quickly. In the worst case, every step branches into multiple directions, producing factorial-like growth. Since each cell may lead to several future possibilities, the total number of paths becomes enormous even for moderately sized grids.

The brute-force approach becomes too slow without careful pruning and efficient state management.

Optimal Approach, Backtracking with Remaining Cell Count

The key observation is that we only care about paths that visit every non-obstacle square exactly once.

Instead of checking the whole board repeatedly, we can maintain a count of how many valid squares still remain to be visited.

The algorithm works as follows:

• Count all non-obstacle squares.
• Start DFS from the starting cell.
• Mark cells as visited during traversal.
• Decrease the remaining-cell counter whenever we enter a new cell.
• When we reach the ending square, the path is valid only if the remaining count becomes zero.

This transforms the problem into a classic backtracking search.

The constraints are small enough that DFS with backtracking is efficient enough in practice. Since the grid contains at most 20 cells, exhaustive exploration with pruning is acceptable.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4^(m*n))	O(m*n)	Explores all possible walks without efficient pruning
Optimal	O(4^(m*n)) worst case	O(m*n)	Backtracking with visited-state pruning and remaining-cell tracking

Although both approaches share the same theoretical upper bound, the optimized backtracking solution performs dramatically better because invalid paths terminate early.

Algorithm Walkthrough

1. Traverse the grid once to locate:

• the starting position,
• and the total number of non-obstacle cells.

We count every cell that is not -1 because each of these cells must eventually be visited exactly once. 2. Define the four movement directions:

• up,
• down,
• left,
• right.

3. Start a depth-first search from the starting cell.
4. Inside the DFS:

• First verify that the current position is inside the grid.
• Reject the move if the cell is an obstacle or already visited.

5. If the current cell is the ending square:

• Check whether this is the final required cell.
• If the remaining count equals 1, this means every non-obstacle square has been visited exactly once.
• Return 1 for a valid path.
• Otherwise return 0.

6. Mark the current cell as visited.

• A common technique is temporarily replacing its value with -1.

7. Explore all four neighboring cells recursively.

• Each recursive call reduces the remaining-cell count by one.

8. Sum all valid paths returned by recursive calls.
9. Backtrack by restoring the original cell value.

• This is essential because other recursive branches still need to use the cell.

10. Return the total number of valid paths discovered from the current position.

Why it works

The algorithm maintains an important invariant:

Every recursive DFS call represents a path that has visited a unique set of cells exactly once.

Because cells are marked visited immediately upon entry and restored during backtracking, no path can revisit a cell. The remaining-cell counter guarantees that the ending square is accepted only when all valid squares have been covered. Since DFS explores every possible valid movement sequence, every legal path is counted exactly once.

Python Solution

from typing import List

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        start_row = 0
        start_col = 0
        non_obstacle_cells = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != -1:
                    non_obstacle_cells += 1

                if grid[r][c] == 1:
                    start_row = r
                    start_col = c

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        def dfs(row: int, col: int, remaining: int) -> int:
            if (
                row < 0
                or row >= rows
                or col < 0
                or col >= cols
                or grid[row][col] == -1
            ):
                return 0

            if grid[row][col] == 2:
                return 1 if remaining == 1 else 0

            original_value = grid[row][col]
            grid[row][col] = -1

            total_paths = 0

            for dr, dc in directions:
                next_row = row + dr
                next_col = col + dc

                total_paths += dfs(next_row, next_col, remaining - 1)

            grid[row][col] = original_value

            return total_paths

        return dfs(start_row, start_col, non_obstacle_cells)

The implementation begins by scanning the grid to count all non-obstacle cells and locate the starting position.

The non_obstacle_cells variable is critical because it represents how many cells must be visited before the path is considered complete.

The DFS function performs recursive backtracking. The first condition handles invalid moves such as:

• leaving the board,
• stepping onto obstacles,
• or revisiting previously visited cells.

When the algorithm reaches the ending square, it checks whether exactly one remaining cell exists. That remaining cell corresponds to the ending square itself. If so, the path is valid.

The current cell is then marked as visited by replacing its value with -1. This avoids needing a separate visited matrix.

The recursion explores all four directions and accumulates the number of successful paths.

Finally, the cell value is restored during backtracking so future recursive branches can reuse it correctly.

Go Solution

func uniquePathsIII(grid [][]int) int {
    rows := len(grid)
    cols := len(grid[0])

    startRow, startCol := 0, 0
    nonObstacleCells := 0

    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if grid[r][c] != -1 {
                nonObstacleCells++
            }

            if grid[r][c] == 1 {
                startRow = r
                startCol = c
            }
        }
    }

    directions := [][]int{
        {1, 0},
        {-1, 0},
        {0, 1},
        {0, -1},
    }

    var dfs func(int, int, int) int

    dfs = func(row int, col int, remaining int) int {
        if row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] == -1 {
            return 0
        }

        if grid[row][col] == 2 {
            if remaining == 1 {
                return 1
            }
            return 0
        }

        originalValue := grid[row][col]
        grid[row][col] = -1

        totalPaths := 0

        for _, dir := range directions {
            nextRow := row + dir[0]
            nextCol := col + dir[1]

            totalPaths += dfs(nextRow, nextCol, remaining-1)
        }

        grid[row][col] = originalValue

        return totalPaths
    }

    return dfs(startRow, startCol, nonObstacleCells)
}

The Go implementation follows the same algorithmic structure as the Python solution.

One difference is that Go requires explicit function variable declaration for recursive closures. The DFS function is declared using:

var dfs func(int, int, int) int

The grid itself is modified in place for visited marking, exactly like the Python version. Since Go slices are reference-based, the recursive calls all operate on the same underlying grid structure.

No integer overflow concerns exist because the number of valid paths remains small enough for Go's standard int type under the given constraints.

Worked Examples

Example 1

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

Total non-obstacle cells:

11

Initial DFS call:

Variable	Value
row	0
col	0
remaining	11

The algorithm marks (0,0) visited and recursively explores neighbors.

One successful traversal becomes:

Step	Position	Remaining
1	(0,0)	11
2	(0,1)	10
3	(0,2)	9
4	(0,3)	8
5	(1,3)	7
6	(1,2)	6
7	(1,1)	5
8	(1,0)	4
9	(2,0)	3
10	(2,1)	2
11	(2,2)	1

At the ending square (2,2), remaining == 1, so this path counts as valid.

The DFS eventually discovers two such valid paths.

Final answer:

2

Example 2

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

Total non-obstacle cells:

12

The search space is larger because there are no obstacles restricting movement.

The DFS explores every valid Hamiltonian-style traversal.

Several recursive branches terminate early because:

• they trap themselves,
• or they reach the ending square before covering all cells.

The algorithm ultimately counts four valid paths.

Final answer:

4

Example 3

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

Total non-obstacle cells:

4

Possible moves quickly fail because reaching the ending square always leaves at least one unvisited cell.

Example invalid traversal:

Step	Position	Remaining
1	(0,1)	4
2	(0,0)	3
3	(1,0)	2

The algorithm reaches the ending square while remaining != 1, so the path is rejected.

No valid path exists.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(4^(m*n))	Each cell may recursively branch in up to four directions
Space	O(m*n)	Recursion depth and visited state tracking

The worst-case runtime occurs when the board contains very few obstacles, allowing many branching possibilities. Although the theoretical upper bound is exponential, the constraint m * n <= 20 keeps the search manageable.

The space complexity comes primarily from recursion depth. At most, the DFS stack contains one frame per traversable cell.

Test Cases

from typing import List

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        start_row = 0
        start_col = 0
        non_obstacle_cells = 0

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] != -1:
                    non_obstacle_cells += 1

                if grid[r][c] == 1:
                    start_row = r
                    start_col = c

        directions = [
            (1, 0),
            (-1, 0),
            (0, 1),
            (0, -1),
        ]

        def dfs(row: int, col: int, remaining: int) -> int:
            if (
                row < 0
                or row >= rows
                or col < 0
                or col >= cols
                or grid[row][col] == -1
            ):
                return 0

            if grid[row][col] == 2:
                return 1 if remaining == 1 else 0

            original_value = grid[row][col]
            grid[row][col] = -1

            total_paths = 0

            for dr, dc in directions:
                total_paths += dfs(row + dr, col + dc, remaining - 1)

            grid[row][col] = original_value

            return total_paths

        return dfs(start_row, start_col, non_obstacle_cells)

solution = Solution()

assert solution.uniquePathsIII([
    [1,0,0,0],
    [0,0,0,0],
    [0,0,2,-1]
]) == 2  # Example 1

assert solution.uniquePathsIII([
    [1,0,0,0],
    [0,0,0,0],
    [0,0,0,2]
]) == 4  # Example 2

assert solution.uniquePathsIII([
    [0,1],
    [2,0]
]) == 0  # Example 3

assert solution.uniquePathsIII([
    [1,2]
]) == 1  # Smallest direct path

assert solution.uniquePathsIII([
    [1,-1],
    [0,2]
]) == 0  # Obstacle blocks traversal

assert solution.uniquePathsIII([
    [1,0,2]
]) == 1  # Single straight-line traversal

assert solution.uniquePathsIII([
    [1],
    [0],
    [2]
]) == 1  # Vertical traversal

assert solution.uniquePathsIII([
    [1,0],
    [0,2]
]) == 0  # Cannot visit all cells exactly once

assert solution.uniquePathsIII([
    [1,0,0],
    [0,-1,0],
    [0,0,2]
]) == 0  # Obstacle creates impossible traversal

Test	Why
Example 1	Validates multiple valid Hamiltonian paths
Example 2	Validates larger branching search
Example 3	Validates impossible traversal detection
[[1,2]]	Smallest valid grid
[[1,-1],[0,2]]	Obstacle blocking case
[[1,0,2]]	Simple linear traversal
Vertical single-column grid	Tests non-square grids
[[1,0],[0,2]]	Ensures incomplete coverage is rejected
Obstacle maze case	Tests pruning and dead-end handling

Edge Cases

One important edge case occurs when the ending square is reached too early. A naive solution might immediately count such a path as valid. However, the problem requires every non-obstacle square to be visited exactly once. The implementation handles this correctly by checking whether remaining == 1 before accepting the ending square.

Another tricky case involves isolated regions caused by obstacles. Some grids contain valid-looking paths near the start but eventually trap the traversal before all cells can be visited. Because the DFS explores every possible route and backtracks correctly, such dead-end branches naturally return 0.

A third subtle case is revisiting cells accidentally. Without proper visited tracking, recursive DFS can enter infinite loops or overcount paths. The implementation prevents this by temporarily marking visited cells as -1. Since the original value is restored during backtracking, each recursive branch sees the correct board state independently.

A final edge case involves very small grids, such as a single-row or single-column board. These layouts can expose indexing bugs or incorrect movement logic. The boundary checks inside DFS ensure that all out-of-bounds moves are safely rejected.