Striver's SDE Sheet Journey - #17 Grid Unique Paths

Problem Statement :-

Given a matrix m X n, count paths from left-top to the right bottom of a matrix with the constraints that from each cell you can either only move to the rightward direction or the downward direction.

Example

Input : m = 2, n= 2

Result : 2

Solution 1

by using recursive call for the downward and rightward direction. by doing that we can able to find out all the possible paths

step-1 in the 2D matrix, we first start at (0,0), and then we make two recursive calls in the direction of the bottom & right to reach the destination.

      (0,0)
     /     \
  (1,0)   (0,1)

step-2 when the recursive call goes out of the boundary of the matrix, we will simply return 0.

in the 2x2 matrix, path (2,0) is out of boundary.

      (0,0)
     /     \
  (1,0)   (0,1)
  /
(2,0) -> return 0

step-3 when the recursive call reaches the destination or end of the matrix, we will return 1.

          (0,0)
         /     \
      (1,0)   (0,1)
     /   \
 (2,0)   (1,1) -> return 1

step-4 we will sum the result from left & right recursive call and return the ans.

step-5 to avoid recomputing, we will use another matrix to store the result of the recursive call for future use.
whenever we found the same sub-problem, we simply return the result from the matrix instead of recomputing.

see the java implementation

Java

class Solution {
    public int uniquePaths(int m, int n) {

        int totalPaths = 0;
        int[][] dp = new int[m][n];

        for(int i=0; i<m; i++) Arrays.fill(dp[i],-1);

        totalPaths = findPaths(m,n,0,0,dp);

        return totalPaths;


    }

    private int findPaths(int m,int n,int i,int j,int[][] dp){

        if(i == m-1 && j == n-1) return 1;

        if(i >= m || j >= n) return 0;

        if(dp[i][j] != -1) return dp[i][j];

        return dp[i][j] = findPaths(m,n,i+1,j,dp) + findPaths(m,n,i,j+1,dp);

    }
}