HardArrayBacktrackingBit ManipulationMatrixHamiltonian PathUpdated Sep 2026

980. Unique Paths III

Asked at Databricks

Difficulty

Hard

Time

O(4^(m*n))

Space

O(m*n)

Pattern

Array

Companies

1

Problem

You get an m x n grid. Each cell is one of four things: 1 is the start cell, 2 is the end cell, 0 is an empty cell you may walk on, and -1 is an obstacle you may not walk on. There is exactly one start cell and exactly one end cell.

A walk starts at the start cell and moves one step at a time up, down, left or right (no diagonal moves). The walk must finish on the end cell, and it must step on every non-obstacle cell exactly once — no cell may be visited twice, and none may be skipped.

Return the number of different walks that satisfy all of these rules. If no such walk exists, return 0.

Walk every open cell once, end on 2

grid012301210000000002-1green = start (1), red = end (2), grey = obstacle (-1)
The grid has 11 open cells, so a valid walk must have exactly 11 cells and finish on the end cell.

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

Examples

Example 1
Inputgrid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output2
WhyThere are 11 non-obstacle cells, so a valid walk has 11 steps. Exactly two walks cover all of them and finish at the end cell: one goes right along the top row first, the other goes down the left column first.
Example 2
Inputgrid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output4
WhyHere all 12 cells are walkable, so the walk must visit all 12. Four different orderings manage to touch every cell once and end on the bottom-right cell.
Example 3
Inputgrid = [[0,1],[2,0]]
Output0
WhyThe start is at the top-right. Any single step lands on the end cell, but then the two remaining empty cells are never visited, so no valid walk exists.

Asked At

1 companies
CompanyDifficulty
DatabricksHardView all Databricks questions →

How to Think About It

1

Count the total number of non-obstacle cells first to know the required path length

2

Use DFS with backtracking to explore all paths from start to end

3

Mark visited cells and unmark them when backtracking

4

Only count a path when you reach the end cell and have visited all non-obstacle cells

5

Use bitmask to represent visited state for memoization on larger grids

Optimal Approach

Count all non-obstacle cells to determine the required path length. Start DFS from the starting cell (1, 1) with visited count 1. At each step, mark the current cell as visited and explore all four directions. If a neighbor is within bounds, not an obstacle, and not visited, recurse. When reaching the end cell, check if all non-obstacle cells were visited; if so, increment the result count. Backtrack by unmarking the visited cell. Use a bitmask on flat indices for more efficient state representation if needed.

DFS with backtracking

step 1012301210000000002-1From the start, move right to (0,1) and mark itvisitedstep 2012301210000000002-1Keep going right and then down — every visited cell ismarkedfinish012301210000000002-1Reach the end cell with count == total open cells →count this walkif cell == 2: count += (visited == total)else: mark, try 4 dirs, unmark
Try each direction, mark the cell, recurse, then unmark when you come back.
ComplexityTime O(4^(m*n))Space O(m*n)The DFS branches up to 4 ways at each of the m*n cells, and the recursion stack plus the visited grid hold at most m*n entries.

What Trips People Up in Real Interviews

1

Clarify that obstacles are represented as -1 and you cannot step on them

2

Ask whether the start and end cells count as visited (they do)

3

Mention the path must visit every free cell, not just reach the end

4

Discuss that this is essentially finding Hamiltonian paths in a grid graph

5

Talk about pruning: if remaining steps cannot cover remaining cells, stop early

Solution Code

O(4^(m*n)) time
class Solution:
    def uniquePathsIII(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        total = 0
        start_r = start_c = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != -1:
                    total += 1
                if grid[i][j] == 1:
                    start_r, start_c = i, j

        result = [0]
        visited = [[False] * n for _ in range(m)]

        def dfs(r, c, count):
            if grid[r][c] == 2:
                if count == total:
                    result[0] += 1
                return
            visited[r][c] = True
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != -1 and not visited[nr][nc]:
                    dfs(nr, nc, count + 1)
            visited[r][c] = False

        dfs(start_r, start_c, 1)
        return result[0]

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Unique Paths III problem?

Given an m x n grid with obstacles, find the number of unique paths from the top-left to bottom-right cell that visit every non-obstacle cell exactly once. You can only move up, down, left, or right. Return the count of all such Hamiltonian paths through the grid.

How do you solve Unique Paths III?

The optimal approach runs in O(4^(m*n)) time and O(m*n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Unique Paths III?

Unique Paths III is asked at Databricks. It is a hard difficulty problem.

What are common mistakes on Unique Paths III?
  • Clarify that obstacles are represented as -1 and you cannot step on them
  • Ask whether the start and end cells count as visited (they do)
  • Mention the path must visit every free cell, not just reach the end
  • Discuss that this is essentially finding Hamiltonian paths in a grid graph
  • Talk about pruning: if remaining steps cannot cover remaining cells, stop early