62. Finding Unique Path

Problem

Unique Paths - LeetCodeLeetCode

Intuition

Since we are supposed to find all the unique paths, it means we need to explore all the paths that are available. As we are using a top down approach, we try to move from end to the start exploring all the possible moves.

Recursive solution

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

    private int helper(int i, int j, int[][] grid) {
        // 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;
        }

        // 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);

        // Return the computed result.
        return up + left;
    }
}

Recursive Tree

                          (3, 3)
                       /           \
                  (2, 3)           (3, 2)
               /         \        /         \
          (1, 3)       (2, 2)   (2, 2)     (3, 1)
         /       \    /       \  /       \   /       \
     (0, 3)  (1, 2) (1, 2)  (2, 1)(1, 2) (2, 1)(2, 1)  (3, 0)
     /      \   /      \   /      \   /      \   /      \
   (0, 2) (0, 2)(0, 2) (1, 1)(0, 2)(1, 1)(1, 1)(2, 0)(1, 1)(2, 0)
   /      \   /       \  /       \   /      \   /      \   /      \
 (0, 1) (0, 1) (0, 1)(0, 1)(0, 1)(0, 1)(0, 1)(0, 1)(0, 1)(1, 0)(0, 1)(1, 0)(1, 0)(2, 0)(2, 0)(2, 0)(3, 0)
   /      \   /       \  /       \   /      \   /      \   /      \
 (0, 0) (0, 0) (0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)(0, 0)

Here we can see the recursive tree gets big quickly. So we need to optimise it

Memoization

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

    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];
    }
}

We are using grid as the cache to store the computation results. Then the recursive call graph looks like this

                 (3, 3)
                /      \
           (2, 3)     (3, 2)
          /     \     /     \
     (1, 3) (2, 2) (2, 2)  (3, 1)
    /    \    /    \    /    \
(0, 3) (1, 2) (1, 2) (2, 1) (1, 2) (2, 1) (3, 0)

Tabulation

In the population method we try to build the solution from bottom to top that is from start to the end period.

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];
    }