62.Unique Paths

#dp

Problem

Unique Paths - LeetCodeLeetCode

Intuition

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] grid = new int[m][n];
        // return helper(m-1, n-1, grid);
        return tabulationHelper(m, n, grid);
    }

    private int tabulationHelper(int m, int n, int[][] grid) {
        // Time Complexity: O(m*n), we traverse through all the cells once
        // Space Complexity: O(m*n), we need to create a grid to keep track of ways
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                // Base condition: If we are at the top-left cell, set it to 1 as there is only one way to reach this cell.
                if(i == 0 && j == 0) {
                    grid[i][j] = 1;
                    continue;
                }

                int up = 0;
                int left = 0;
      
                // Compute the number of paths from the cell above (up) and the cell to the left (left).
                if(i > 0) {
                    up = grid[i - 1][j];
                }
                if(j > 0) {
                    left = grid[i][j - 1];
                }
        
                // Set the current cell to the sum of paths from above and left, representing the number of unique paths to reach this cell.
                grid[i][j] = up + left;
            }
        }
    
        // Return the value in the bottom-right cell, which represents the total number of unique paths.
        return grid[m - 1][n - 1];
    }



    private int helper(int i, int j, int[][] grid) {
        // Time Complexity: O(m*n), we traverse through all the cells once
        // Space Complexity: O(m*n), we need to create a grid to keep track of ways

        // Base case: If we reach the top-left corner, return 1 as we have found a unique path.
        if (i == 0 && j == 0) {
            return 1;
        }

        // If we go out of bounds (i.e., i < 0 or j < 0), we cannot continue further, so return 0.
        if (i < 0 || j < 0) {
            return 0;
        }

        // Check if the result for the current position is already computed and stored in the grid.
        if (grid[i][j] != 0) {
            return grid[i][j];
        }

        // Compute the number of unique paths by recursively moving either up or left.
        int up = helper(i - 1, j, grid);
        int left = helper(i, j - 1, grid);

        // Store the result in the grid to avoid redundant computations.
        grid[i][j] = up + left;

        // Return the computed result.
        return grid[i][j];
    }
}