Unique Paths III
Asked at Databricks
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | HARD | View all Databricks questions → |
How to Think About It
Count the total number of non-obstacle cells first to know the required path length
Use DFS with backtracking to explore all paths from start to end
Mark visited cells and unmark them when backtracking
Only count a path when you reach the end cell and have visited all non-obstacle cells
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.
What Trips People Up in Real Interviews
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
Solution Code
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]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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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