Skip to main content

980. Unique Paths III

hard

Count the number of grid paths from start to end that visit every walkable cell exactly once. Hamiltonian-style enumeration where backtracking with the mark-and-restore pattern is the only feasible approach.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

On a 2-dimensional grid, there are 4 types of squares: 1 represents the starting square. There is exactly one starting square. 2 represents the ending square. There is exactly one ending square. 0 represents empty squares we can walk over. -1 represents obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

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

Examples

Example 1

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

Explanation: We have the following two paths: 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2). 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(1,2),(2,2).

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: There is no path that walks over every empty square exactly once. Note that the starting and ending square can be visited but they cannot be part of the path.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count walkable squares (non-obstacle) — call this total. A valid path visits exactly total - 1 transitions and ends on cell 2.

Hint 2

DFS from the start with a 'remaining' counter that decrements on each step.

Hint 3

Mark visited by mutating grid[r][c] = -1 before recursing, restore after. The mark-and-restore is what makes backtracking memory-efficient.

Hint 4

Base case: cell is the ending square AND remaining == 0 -> path is valid, return 1.

Solution approach

Reveal approach

Scan the grid to count non-obstacle squares (call it remaining) and find the starting cell. DFS(r, c, remaining): if out of bounds or grid[r][c] == -1, return 0. If grid[r][c] == 2: return remaining == 0 ? 1 : 0. Decrement remaining (we're about to visit this cell). Mark grid[r][c] = -1. Sum DFS in 4 directions with remaining - 1. Restore grid[r][c] to its original value. Return the sum. The 'restore' is the backtracking step. Time is O(4^N) worst case where N is the number of walkable cells — but the grid is capped at 20 total cells so it's bounded. Space O(N) recursion.

Complexity

Time
O(4^N) where N = walkable cells
Space
O(N)

Related patterns

  • backtracking
  • dfs
  • hamiltonian-path

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Unique Paths III and Recursion problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →