Unique Paths III

Unique Paths III

What is this problem about?

The Unique Paths III interview question is the most difficult version of the series. Unlike the previous versions where you only move right and down, here you can move in all four directions (up, down, left, right). Furthermore, you are required to visit every single non-obstacle cell exactly once before reaching the destination. This transforms a simple DP problem into a complex path-finding and Hamiltonian path challenge.

Why is this asked in interviews?

This Unique Paths III coding problem is used by high-bar companies like Databricks, Goldman Sachs, and Google to test a candidate's mastery of Backtracking. It requires exhaustive search with state management, which is significantly more complex than the previous versions. It tests your ability to manage "visited" states and your understanding of recursion depth.

Algorithmic pattern used

The primary Array, Matrix, Backtracking, Bit Manipulation interview pattern for this is Depth-First Search (DFS) with backtracking. You first count the number of empty cells that must be visited. Then, starting from the source, you explore all four neighbors. When you move to a cell, you mark it as visited (e.g., by changing its value to an obstacle temporarily). When you reach the destination, you check if the number of steps taken equals the total number of empty cells. If it does, you've found a valid path.

Example explanation

Imagine a small $2 \times 2$ grid: Start at (0, 0), End at (0, 1). There is one empty cell at (1, 1) and an obstacle at (1, 0).

1. Total cells to visit (including start): 3.
2. From (0, 0), go to (1, 1). Steps = 2.
3. From (1, 1), go to (0, 1). Steps = 3.
4. Destination reached and steps match! This is 1 valid path. If we had gone directly from (0, 0) to (0, 1), steps would be 2, which doesn't match the required 3.

Common mistakes candidates make

The most frequent mistake is not properly backtracking the state (failing to unmark a cell as visited after the recursive call). Another error is forgetting to count the starting cell as one of the cells that must be visited. Finally, without an efficient base case check, the recursion can become very slow on larger grids.

Interview preparation tip

Backtracking is all about the "Visit -> Recurse -> Unvisit" cycle. Practice this pattern until it is second nature. Also, remember that for problems involving visiting all nodes, the search space is large, so identifying early exit conditions (pruning) is key to passing harder test cases.