Unique Paths III

Hard
922.

Unique Paths III

Unique Paths III is a hard coding problem on arrays, matrix and bit manipulation, asked in Amazon, Google, Microsoft and Databricks interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var uniquePathsIII = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Unique Paths III — Solution in Python, Java & C++

Unique Paths III solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and matrix.

Unique Paths III is a hard coding problem on arrays, matrix and bit manipulation, asked in Amazon, Google, Microsoft and Databricks interviews.

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.

Hints for Unique Paths III

  1. Hint 1

    There are at most 20 cells, so an exhaustive search is affordable.

  2. Hint 2

    Backtrack: mark a cell on the way in and unmark it on the way out.

  3. Hint 3

    Count how many 0 cells remain, and only accept a route that reaches 2 with that count at zero.

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

  1. Count the 0 cells and locate the start.
  2. Recurse from the start, carrying how many 0 cells are still unvisited.
  3. On entering a 0 cell, decrement that counter; on entering the 2 cell, accept the walk if the counter is zero and stop.
  4. 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

Java

private static int upCount;
private static boolean[][] upSeen;
private static int[][] upGrid;

public static int uniquePathsIII(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int empty = 0, sr = 0, sc = 0, ends = 0;
    for (int i = 0; i < m; i++) {
        for (int 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;
    upCount = 0;
    upSeen = new boolean[m][n];
    upGrid = grid;
    upWalk(sr, sc, empty);
    return upCount;
}

private static void upWalk(int r, int c, int remaining) {
    int m = upGrid.length, n = upGrid[0].length;
    if (upGrid[r][c] == 2) {
        if (remaining == 0) upCount++;
        return;
    }
    upSeen[r][c] = true;
    int rem = upGrid[r][c] == 0 ? remaining - 1 : remaining;
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
        if (upSeen[nr][nc] || upGrid[nr][nc] == -1) continue;
        upWalk(nr, nc, rem);
    }
    upSeen[r][c] = false;
}

C++

static int upCount;
static vector<vector<char>> upSeen;

static void upWalk(vector<vector<int>>& grid, int r, int c, int remaining) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    if (grid[r][c] == 2) {
        if (remaining == 0) upCount++;
        return;
    }
    upSeen[r][c] = 1;
    int rem = grid[r][c] == 0 ? remaining - 1 : remaining;
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    for (int d = 0; d < 4; d++) {
        int nr = r + dr[d], nc = c + dc[d];
        if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
        if (upSeen[nr][nc] || grid[nr][nc] == -1) continue;
        upWalk(grid, nr, nc, rem);
    }
    upSeen[r][c] = 0;
}

int uniquePathsIII(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    int empty = 0, sr = 0, sc = 0, ends = 0;
    for (int i = 0; i < m; i++) {
        for (int 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;
    upCount = 0;
    upSeen.assign(m, vector<char>(n, 0));
    upWalk(grid, sr, sc, empty);
    return upCount;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Matrix and Grid Traversal