Skip to main content

980. Unique Paths III

hard

Count distinct walks that start at the source, end at the target, and visit every non-obstacle cell exactly once. Backtracking — not classic DP — but routinely lumped into 2D-grid practice sets.

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

Problem

You are given an m x n integer array grid where grid[i][j] could be: 1 representing the starting square (there is exactly one), 2 representing the ending square (there is exactly one), 0 representing empty squares we can walk over, -1 representing 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). (Each lists the cells visited in order.)

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 anywhere in the grid.

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

m * n <= 20 — that small ceiling is the hint that exponential backtracking is fine.

Hint 2

DFS from the start. Track which non-obstacle cells remain unvisited.

Hint 3

When you arrive at the target, you can count the walk only if zero non-obstacle cells remain unvisited.

Hint 4

Bitmask the visited set (up to 20 cells fits in an int) and memoize on (position, visited mask) if you want polynomial speedup over plain backtracking.

Solution approach

Reveal approach

Backtracking. Count the number of cells that must be visited (non-obstacle cells, including start and end). DFS from the start cell, marking cells as visited as you enter them and unmarking on exit. At each step, try the four directions. When you land on the target cell, increment the answer only if the number of cells visited equals the required total. Otherwise keep exploring. For a tighter solution use a bitmask of visited cells and memoize on (currentIndex, mask) — works because m * n <= 20.

Complexity

Time
O(4^(m*n))
Space
O(m*n)

Related patterns

  • backtracking
  • bitmask-dp
  • grid-dp

Related problems

Asked at

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

  • Google

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →