Unique Paths III — Hard Problem & Solution

A grid holds four kinds of cell: 1 the starting square (exactly one), 2 the ending square (exactly one), 0 a square you may walk over, and -1 an obstacle…

Difficulty: Hard
Topics: Arrays, Matrix, Bit Manipulation, Backtracking
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A grid holds four kinds of cell: 1 the starting square (exactly one), 2 the ending square (exactly one), 0 a square you may walk over, and -1 an obstacle you may not.

Return the number of 4-directional walks from start to end that visit every non-obstacle square exactly once.

Example 1

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: Two ways to cover all ten walkable squares.

Example 2

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

Example 3

Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: Any route from the start to the end must skip one of the two empty squares.

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.

How to solve Unique Paths III

With at most 20 cells, enumerate every self-avoiding walk from the start. A walk counts only if it arrives at the end having consumed every walkable square.

Approach

Count the 0 cells and locate the start.
Recurse from the start, carrying how many 0 cells are still unvisited.
On entering a 0 cell, decrement that counter; on entering the 2 cell, accept the walk if the counter is zero and stop.
Mark cells visited on the way down and clear the mark on the way back up.

Why it works

The counter is the whole correctness argument: because a walk never revisits a cell, "remaining reaches zero" is exactly "every walkable square has been used once". Clearing the mark on the way out is what lets different branches reuse a cell — without it the search would find only the first route through each square.

Complexity

Time — O(3^(m · n)) in the worst case, but tiny at m · n <= 20``
Space — O(m · n) for the recursion and the visited grid

Pitfalls

Forgetting to unmark a cell on the way out under-counts badly.
The end square is not a 0, so it must not be counted among the cells to consume.
A walk that reaches the end early must stop there rather than pass through it.

Reference solution

Python

from typing import List

def uniquePathsIII(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    empty = 0
    sr = sc = 0
    ends = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 0:
                empty += 1
            elif grid[i][j] == 1:
                sr, sc = i, j
            elif grid[i][j] == 2:
                ends += 1
    if ends == 0:
        return 0
    seen = [[False] * n for _ in range(m)]
    count = 0

    def walk(r: int, c: int, remaining: int) -> None:
        nonlocal count
        if grid[r][c] == 2:
            if remaining == 0:
                count += 1
            return
        seen[r][c] = True
        rem = remaining - 1 if grid[r][c] == 0 else remaining
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] != -1:
                walk(nr, nc, rem)
        seen[r][c] = False

    walk(sr, sc, empty)
    return count

JavaScript

var uniquePathsIII = function(grid) {
    var m = grid.length, n = grid[0].length, i, j;
    var empty = 0, sr = 0, sc = 0, ends = 0;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (grid[i][j] === 0) empty++;
            else if (grid[i][j] === 1) { sr = i; sc = j; }
            else if (grid[i][j] === 2) ends++;
        }
    }
    if (ends === 0) return 0;
    var seen = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(false);
        seen.push(row);
    }
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var count = 0;
    var walk = function(r, c, remaining) {
        if (grid[r][c] === 2) {
            if (remaining === 0) count++;
            return;
        }
        seen[r][c] = true;
        var rem = grid[r][c] === 0 ? remaining - 1 : remaining;
        for (var d = 0; d < 4; d++) {
            var nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (seen[nr][nc] || grid[nr][nc] === -1) continue;
            walk(nr, nc, rem);
        }
        seen[r][c] = false;
    };
    walk(sr, sc, empty);
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue