Unique Paths III Hard 0 attempts
LeetCode ↗

Unique Paths III

Hard BacktrackingRecursion LeetCode

You're given an m x n grid of integers where each cell grid[i][j] means one of four things: 1 marks the single starting square, 2 marks the single ending square, 0 marks an empty square you're free to cross, and -1 marks a blocked square. Count how many distinct routes — moving up, down, left, or right — get from start to end while stepping on every open (non-obstacle) square exactly once.

Input Format
Implement uniquePathsIII(grid). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
grid = [[1,2]]
Output
1
Constraints
  • 1 <= m, n <= 20
  • m * n <= 20
Test Cases (2)
Case 1
Args: [[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]] Expected: 2
Case 2
Args: [[[1,2]]] Expected: 1
Topics
BacktrackingRecursion

Count total non-obstacle squares. Start DFS from the starting cell, tracking visited squares. When we reach the ending cell having visited all non-obstacle squares, increment the path count.

javascript
function uniquePathsIII(grid) {
  const rows = grid.length, cols = grid[0].length;
  let startR, startC, empty = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== -1) empty++;
      if (grid[r][c] === 1) { startR = r; startC = c; }
    }
  }

  let count = 0;
  function dfs(r, c, remaining) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === -1) return;
    if (grid[r][c] === 2) {
      if (remaining === 1) count++;
      return;
    }
    grid[r][c] = -1;
    for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      dfs(r + dr, c + dc, remaining - 1);
    }
    grid[r][c] = 0;
  }

  dfs(startR, startC, empty);
  return count;
}

Time: O(3^(m·n)) — at most 3 choices per cell due to backtracking Space: O(m·n)

Saved in this browser only. Private to you.

JavaScript