- recursively check the right and bottom moves
- if they are in bounds
- or not being blocked by an obstacle
- helper function to count the number of paths that make it to the finish point
🤔What Did I Struggle With?
- only returning unique paths
- memorising already traversed paths to reduce time complexity
💡 Explanation of Solution
Recursive approach with memoization
1. Recursive traversal:
- start at the top-left corner (0,0) and recursively explore paths moving:
- right (row + col + 1) and down (row + 1 + col)
2. Base Cases:
- if the current cell is the bottom-right corner, return 1 becasue we've reached the destination
- if the current cell is blocked by an obstacle or out of bounds, return 0
3. Memoization:
- to avoid redundant calculations, store the results of subproblems in a memo table
- before calculating the paths from a given cell, check if the result is already stored in memo[row][col]
- if yes, return the stored value
4. Recursive Formula:
- the number of unique paths from a cell (row, col) is the sum of the paths from the cell to its right and the cell below
- memo[row][col]=countPaths(row,col+1)+countPaths(row+1,col)
⌛ Complexity Analysis
Time Complexity:
- recursive calls : each cell (row, col) is visited only once due to memoization
- for a grid of size m*n , the number of unique states is at most m*n
- complexity: O(m*n)
Space Complexity:
- memoization table : a m*n 2D vector is used to store results of subproblems, using O(n*n) auxilary space
💻 Implementation of Solution
class Solution {public: int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) { int rows = obstacleGrid.size(), cols = obstacleGrid[0].size(); vector<vector<int>> memo(rows,vector<int>(cols, -1)); return countPaths(obstacleGrid, 0, 0, memo); } int countPaths(vector<vector<int>>& grid, int row, int col, vector<vector<int>>& memo) { if(row >= grid.size() || col >= grid[0].size() || grid[row][col] == 1) return 0; // if at the destination, return 1 if(row == grid.size()-1 && col == grid[0].size()-1) return 1; // if already computed, return stored value if(memo[row][col] != -1) { return memo[row][col]; } // recursively call for right and down moves memo[row][col] = countPaths(grid, row, col+1, memo) + countPaths(grid, row+1, col, memo); return memo[row][col]; }};