Scale Engineer

Unique Paths III

Hard
#0934Time: O(3^(m*n)) - In the worst case, from each non-obstacle square, we can explore up to 3 new directions (we don't go back to the square we just came from). If there are `k` walkable squares, the complexity is roughly `O(3^k)`. Since `k` can be up to `m*n`, the complexity is `O(3^(m*n))`. This is an upper bound; the actual performance is faster due to pruning.Space: O(m * n) - The space complexity is determined by the maximum depth of the recursion stack. In the worst-case scenario, the path could cover all the squares in the grid, leading to a recursion depth of `m * n`.2 companies
Patterns
BacktrackingBit Manipulation
Data structures
ArrayMatrix
Companies
PinterestCruise

Prompt

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 starting square.
  • 2 representing the ending square. There is exactly one ending square.
  • 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.

 

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),(0,3),(1,3),(1,2),(2,2)

Example 2:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four 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,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

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.

 

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a standard backtracking algorithm, which is a form of Depth-First Search (DFS), to explore all possible paths from the starting square. The core idea is to try moving in all four directions from the current square. If a move leads to a valid, unvisited square, we recursively explore from there. To ensure we visit every non-obstacle square exactly once, we keep track of the number of squares visited. When we reach the ending square, we check if the number of visited squares matches the total number of non-obstacle squares. To avoid using a separate visited array and to handle backtracking efficiently, we can modify the grid in-place, marking a square as visited and then restoring its original value after exploring all paths from it.

Algorithm

  • Initialization:
    1. Iterate through the grid to find the starting coordinates (startX, startY).
    2. Count the total number of walkable squares. This includes the starting square and all empty squares (0). Let's call this walkableSquares.
  • Recursive Function (DFS):
    1. Define a recursive function, dfs(grid, x, y, count), where (x, y) is the current cell and count is the number of unique cells visited so far in the current path.
  • Base Cases:
    1. Out of Bounds / Obstacle: If the current cell (x, y) is outside the grid boundaries or is an obstacle (-1), the path is invalid. Stop this path by returning.
    2. End Square: If the current cell is the end square (2):
      • Check if count is equal to walkableSquares. If they match, it means we have traversed all required squares exactly once before reaching the end. This is a valid path, so we increment a global counter.
      • Return, as the path ends here.
  • Recursive Step:
    1. Mark as Visited: To avoid cycles and re-visiting squares in the same path, mark the current square (x, y) as visited. A common technique is to temporarily change its value to -1 (since obstacles are already handled).
    2. Explore Neighbors: Recursively call the dfs function for all four adjacent neighbors (up, down, left, right), incrementing the count by 1 for each call: dfs(grid, newX, newY, count + 1).
    3. Backtrack: After the recursive calls for all neighbors have returned, restore the original value of the cell (x, y). This is the crucial backtracking step, allowing the cell to be used in other potential paths.

Walkthrough

Algorithm

  1. Pre-computation: First, we scan the entire grid to find the starting coordinates (startX, startY) and to count the total number of squares we need to walk over. This count, let's call it walkableSquares, is the number of 0s plus the starting square 1. A valid path must visit exactly this many squares before hitting the end square.

  2. DFS Function: We define a recursive helper function, dfs(x, y, walkCount), which will perform the search. (x, y) are the current coordinates, and walkCount is the number of squares visited so far in the current path.

  3. DFS Logic:

    • Base Case 1 (Invalid Move): If (x, y) is out of the grid boundaries or if grid[x][y] is an obstacle (-1), the path is invalid, so we return.
    • Base Case 2 (End Square): If grid[x][y] is the end square (2), we check if we have visited all required squares. A valid path is found if walkCount equals walkableSquares. If so, we increment our global result counter. In either case, we return because a path cannot continue past the end square.
    • Recursive Step: a. Mark as Visited: Mark the current square (x, y) as visited to prevent cycles. A simple way is to change its value to -1. b. Explore Neighbors: Explore the four adjacent squares (up, down, left, right) by making a recursive call dfs(newX, newY, walkCount + 1) for each neighbor. c. Backtrack: After the recursive calls for all neighbors return, we must "un-visit" the current square by restoring its original value. This is crucial for allowing other paths to use this square.

Code Snippet

class Solution {    private int result = 0;    private int walkableSquares = 1; // Start with 1 for the starting square itself     public int uniquePathsIII(int[][] grid) {        int startX = 0, startY = 0;        int m = grid.length;        int n = grid[0].length;         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 0) {                    walkableSquares++;                } else if (grid[i][j] == 1) {                    startX = i;                    startY = j;                }            }        }         dfs(grid, startX, startY, 1);        return result;    }     private void dfs(int[][] grid, int x, int y, int count) {        // Base case: out of bounds or obstacle or already visited        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) {            return;        }         // Base case: reached the end        if (grid[x][y] == 2) {            if (count == walkableSquares) {                result++;            }            return;        }         // Mark the current cell as visited        int originalValue = grid[x][y];        grid[x][y] = -1;         // Explore neighbors        dfs(grid, x + 1, y, count + 1);        dfs(grid, x - 1, y, count + 1);        dfs(grid, x, y + 1, count + 1);        dfs(grid, x, y - 1, count + 1);         // Backtrack: un-mark the cell        grid[x][y] = originalValue;    }}

Complexity

Time

O(3^(m*n)) - In the worst case, from each non-obstacle square, we can explore up to 3 new directions (we don't go back to the square we just came from). If there are `k` walkable squares, the complexity is roughly `O(3^k)`. Since `k` can be up to `m*n`, the complexity is `O(3^(m*n))`. This is an upper bound; the actual performance is faster due to pruning.

Space

O(m * n) - The space complexity is determined by the maximum depth of the recursion stack. In the worst-case scenario, the path could cover all the squares in the grid, leading to a recursion depth of `m * n`.

Trade-offs

Pros

  • Relatively simple to understand and implement.

  • Low memory usage as it only uses the recursion stack for space.

Cons

  • The time complexity is exponential, making it inefficient for larger grids (though it passes with the given constraints).

  • It may re-explore the same sub-paths multiple times, as it doesn't store the results of subproblems.

Solutions

class Solution {private  int m;private  int n;private  int cnt;private  int[][] grid;private  boolean[][] vis;public  int uniquePathsIII(int[][] grid) {    m = grid.length;    n = grid[0].length;    this.grid = grid;    int x = 0, y = 0;    for (int i = 0; i < m; ++i) {      for (int j = 0; j < n; ++j) {        if (grid[i][j] == 0) {          ++cnt;        } else if (grid[i][j] == 1) {          x = i;          y = j;        }      }    }    vis = new boolean[m][n];    vis[x][y] = true;    return dfs(x, y, 0);  }private  int dfs(int i, int j, int k) {    if (grid[i][j] == 2) {      return k == cnt + 1 ? 1 : 0;    }    int ans = 0;    int[] dirs = {-1, 0, 1, 0, -1};    for (int h = 0; h < 4; ++h) {      int x = i + dirs[h], y = j + dirs[h + 1];      if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] &&          grid[x][y] != -1) {        vis[x][y] = true;        ans += dfs(x, y, k + 1);        vis[x][y] = false;      }    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem