# Unique Paths III **Difficulty:** HARD [External](https://leetcode.com/problems/unique-paths-iii) Canonical: https://scaleengineer.com/dsa/problems/unique-paths-iii **Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation) **Data structures:** Array, Matrix **Companies:** [Pinterest](https://scaleengineer.com/companies/pinterest), [Cruise](https://scaleengineer.com/companies/cruise) --- ## 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 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:** ![](https://assets.glich.co/dsa/unique-paths-iii/image0.jpg) **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:** ![](https://assets.glich.co/dsa/unique-paths-iii/image1.jpg) **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:** ![](https://assets.glich.co/dsa/unique-paths-iii/image2.jpg) **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 ## Backtracking with Depth-First Search 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. **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`. **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. ### Explanation ### 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 `0`s 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 ```java 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; } } ``` ### 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. ## Dynamic Programming with Bitmasking This approach is a more optimized solution that uses dynamic programming combined with bitmasking to avoid re-computing results for the same subproblems. A subproblem is defined by the current position and the set of visited squares. Since the total number of squares (`m*n`) is small (<= 20), we can represent the set of visited squares using a bitmask, where the i-th bit is 1 if the i-th square has been visited, and 0 otherwise. This method effectively solves the Hamiltonian Path problem on the grid graph, which is feasible due to the small constraints. **Time:** O(2^(m*n) * (m*n)^2) - A more careful analysis shows the loops are over `mask` (2^N), `u` (N), and its neighbors (4), and for each valid transition, we update `dp[nextMask][v]`. A simpler upper bound is often stated as `O(2^N * N^2)`. For each of the `2^N * N` states, we iterate through `N` possible previous states. However, a tighter analysis considering transitions from a state gives `O(2^N * N)`. Let's consider the loops: `mask` (2^N), `u` (N), neighbors (4). This gives `O(2^N * N)`. The provided code implements this tighter complexity. · **Space:** O(2^(m*n) * (m*n)) - We need to store the DP table, which has `2^N` rows and `N` columns, where `N = m*n`. This can consume a significant amount of memory. **Pros:** Significantly faster than backtracking for the given constraints due to a better time complexity.; Avoids re-computation by memoizing results of subproblems (current location and set of visited cells). **Cons:** High memory consumption due to the large DP table, which might be an issue if the constraints were larger.; More complex to conceptualize and implement compared to the straightforward backtracking approach. ### Explanation ### Algorithm 1. **State Definition:** We define a DP table, `dp[mask][i]`, which stores the number of paths that visit the set of squares represented by `mask` and end at square `i`. We can flatten the 2D grid coordinates `(r, c)` into a single index `i = r * n + c`. 2. **Initialization:** * First, iterate through the grid to find the start `(sr, sc)` and end `(er, ec)` coordinates, and also to create a `targetMask`. The `targetMask` will have a bit set to 1 for every non-obstacle square (`0`, `1`, or `2`). * Convert the start coordinates to a start index `startIndex = sr * n + sc` and end coordinates to `endIndex`. * Initialize the DP table: `dp[1 << startIndex][startIndex] = 1`. This signifies that there is one path (of length 1) that has visited only the start square and ends at the start square. 3. **Transitions:** * Iterate through all possible masks from `1` to `(1 << (m*n)) - 1`. * For each `mask`, iterate through each square `u` from `0` to `m*n - 1`. * If `dp[mask][u] > 0` and square `u` is part of the current `mask`, it means we have valid paths ending at square `u`. * From square `u`, try to move to its 4-directional neighbors `v`. * If neighbor `v` is a valid, non-obstacle square and has not been visited yet in the current `mask` (i.e., `(mask & (1 << v)) == 0`), we can extend the path. Create a `newMask = mask | (1 << v)`. * Update the DP table for the new state: `dp[newMask][v] += dp[mask][u]`. 4. **Final Result:** After filling the DP table, the final answer is the number of paths that visit all non-obstacle squares (`targetMask`) and end at the end square (`endIndex`). The result is `dp[targetMask][endIndex]`. ### Code Snippet ```java class Solution { public int uniquePathsIII(int[][] grid) { int m = grid.length; int n = grid[0].length; int N = m * n; int startIdx = -1, endIdx = -1; int targetMask = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int idx = i * n + j; if (grid[i][j] != -1) { targetMask |= (1 << idx); } if (grid[i][j] == 1) { startIdx = idx; } else if (grid[i][j] == 2) { endIdx = idx; } } } int[][] dp = new int[1 << N][N]; dp[1 << startIdx][startIdx] = 1; for (int mask = 1; mask < (1 << N); mask++) { for (int u = 0; u < N; u++) { // Check if u is in the current path represented by mask if ((mask & (1 << u)) != 0) { if (dp[mask][u] > 0) { int r = u / n; int c = u % n; int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; for (int i = 0; i < 4; i++) { int nr = r + dr[i]; int nc = c + dc[i]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != -1) { int v = nr * n + nc; // If neighbor v is not yet visited in the current mask if ((mask & (1 << v)) == 0) { int nextMask = mask | (1 << v); dp[nextMask][v] += dp[mask][u]; } } } } } } } return dp[targetMask][endIdx]; } } ``` ### Algorithm * **State Definition:** * We define a DP table, `dp[mask][i]`, which stores the number of paths that visit the set of squares represented by `mask` and end at square `i`. * We flatten the 2D grid coordinates `(r, c)` into a single index `i = r * n + c`. * The `mask` is an integer where the `j`-th bit is 1 if square `j` has been visited, and 0 otherwise. * **Initialization:** 1. First, iterate through the grid to find the start `(sr, sc)` and end `(er, ec)` coordinates. Convert them to `startIndex` and `endIndex`. 2. Also, compute a `targetMask`. The `targetMask` will have a bit set to 1 for every non-obstacle square (`0`, `1`, or `2`). 3. Initialize the DP table: `dp[1 << startIndex][startIndex] = 1`. This signifies that there is one path (of length 1) that has visited only the start square and ends at the start square. * **Transitions:** 1. Iterate through all possible masks from `1` to `(1 << (m*n)) - 1`. 2. For each `mask`, iterate through each square `u` from `0` to `m*n - 1`. 3. If `dp[mask][u] > 0`, it means we have valid paths ending at square `u` with visited set `mask`. 4. From square `u`, try to move to its 4-directional neighbors `v`. 5. If neighbor `v` is a valid, non-obstacle square and has not been visited yet in the current `mask` (i.e., `(mask & (1 << v)) == 0`), we can extend the path. 6. Create a `newMask = mask | (1 << v)`. 7. Update the DP table for the new state: `dp[newMask][v] += dp[mask][u]`. * **Final Result:** 1. After filling the DP table, the final answer is the number of paths that visit all non-obstacle squares (`targetMask`) and end at the end square (`endIndex`). 2. The result is `dp[targetMask][endIndex]`. # Solutions ### Java ```java 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; } } ``` ### JavaScript ```javascript /** * @param {number[][]} grid * @return {number} */ var uniquePathsIII = function (grid) { const m = grid.length; const n = grid[0].length; let [x, y] = [0, 0]; let cnt = 0; for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { if (grid[i][j] === 0) { ++cnt; } else if (grid[i][j] === 1) { [x, y] = [i, j]; } } } const vis = Array.from({ length: m }, () => Array(n).fill(false)); vis[x][y] = true; const dirs = [-1, 0, 1, 0, -1]; const dfs = function (i, j, k) { if (grid[i][j] === 2) { return k === cnt + 1 ? 1 : 0; } let ans = 0; for (let d = 0; d < 4; ++d) { const x = i + dirs[d]; const y = j + dirs[d + 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; }; return dfs(x, y, 0); }; ``` ### CPP ```cpp class Solution { public: int uniquePathsIII(vector> &grid) { int m = grid.size(), n = grid[0].size(); int cnt = 0; for (auto &row : grid) { for (auto &x : row) { cnt += x == 0; } } int dirs[5] = {-1, 0, 1, 0, -1}; bool vis[m][n]; memset(vis, false, sizeof vis); function dfs = [&](int i, int j, int k) -> int { if (grid[i][j] == 2) { return k == cnt + 1 ? 1 : 0; } int ans = 0; 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; }; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { vis[i][j] = true; return dfs(i, j, 0); } } } return 0; } }; ``` ### Python ```python ''' >>> ( (i,j) for i in range(3) for j in range(3) if i == j ) at 0x104da5150> >>> list( (i,j) for i in range(3) for j in range(3) if i == j ) [(0, 0), (1, 1), (2, 2)] >>> next( (i,j) for i in range(3) for j in range(3) if i == j ) (0, 0) basically next() is same as list()[0] ''' class Solution : # dfs def uniquePathsIII ( self , grid : List [ List [ int ]]) -> int : def dfs ( i , j , k ): if grid [ i ][ j ] == 2 : return int ( k == cnt + 1 ) ans = 0 for a , b in pairwise ( dirs ): x , y = i + a , j + b if 0 <= x < m and 0 <= y < n and ( x , y ) not in vis and grid [ x ][ y ] != - 1 : vis . add (( x , y )) ans += dfs ( x , y , k + 1 ) vis . remove (( x , y )) # set() cannot pop(index) or pop(val), only pop() return ans m , n = len ( grid ), len ( grid [ 0 ]) start = next (( i , j ) for i in range ( m ) for j in range ( n ) if grid [ i ][ j ] == 1 ) dirs = ( - 1 , 0 , 1 , 0 , - 1 ) cnt = sum ( grid [ i ][ j ] == 0 for i in range ( m ) for j in range ( n )) vis = { start } # start here is a tuple (i,j) return dfs ( * start , 0 ) # '*start' means that the elements of the start iterable are being unpacked # and passed as separate arguments to the dfs function ######## ''' >>> visited = set([(1,1),(2,2)]) >>> visited {(1, 1), (2, 2)} >>> >>> visited | {(3,3), (4,4)} {(4, 4), (1, 1), (3, 3), (2, 2)} ''' # 980. Unique Paths III # https://leetcode.com/problems/unique-paths-iii/ class Solution : # bfs def uniquePathsIII ( self , grid : List [ List [ int ]]) -> int : rows , cols = len ( grid ), len ( grid [ 0 ]) available = 0 sx = sy = ex = ey = 0 # start x/y, end x/y res = 0 for x in range ( rows ): for y in range ( cols ): if grid [ x ][ y ] != - 1 : available += 1 if grid [ x ][ y ] == 1 : sx , sy = x , y elif grid [ x ][ y ] == 2 : ex , ey = x , y queue = deque ([( sx , sy , 1 , set ([( sx , sy )]))]) # x, y, count, visited while queue : x , y , count , visited = queue . popleft () if x == ex and y == ey and count == available : res += 1 continue for dx , dy in [( x + 1 , y ), ( x - 1 , y ), ( x , y + 1 ), ( x , y - 1 )]: if 0 <= dx < rows and 0 <= dy < cols and grid [ dx ][ dy ] != - 1 and count + 1 <= available and ( dx , dy ) not in visited : new_visited = visited | {( dx , dy )} # or just add() queue . append (( dx , dy , count + 1 , new_visited )) return res ```