03. Unique Paths

The problem can be found at the following link: Question Link

My Approach

The question is a simple problem of recursion/backtracking that can be optimised through Dynamic Programming using memoization and tabulation, to reduce the time complexity exponentially.

To put things into perspective, it takes about 0.0000006 seconds to finish 60 computations, but more than 360 YEARS for 2^60 computations, on most platforms.

We are given a matrix of M rows and N columns, where we have to reach the bottom-right corner (i.e the block with index [m-1][n-1]) from the top-left (i.e. the block with index [0][0]), moving only to the right or down from any given block.

Our first intuition would be to start from the first block and explore all possibilities on each iterations till we reach the destination, then repeat for every other possible combination along the way. Let's see how we do that while not aging beyond our generation.

Now that we've got a glamorous TLE error, let's try to optimise it by maintaining a M*N dp matrix that saves all computations for future reference. Every time we come across a cell whole value has already been found, we return that value without having to go down that road again.

Time and Auxiliary Space Complexity

• Time Complexity: O(m*n)

• Auxiliary Space Complexity: O(m*n) + O(m+n)

Code (C++)

class Solution {
public:
    int find(vector<vector<int>>& dp, int& m, int& n, int i, int j){
        if(i==m || j==n) return 0;  // Out of bounds
        if(i==m-1 && j==n-1) return 1;
        if(dp[i][j]!=-1) return dp[i][j];
        dp[i][j] = find(dp, m, n, i+1, j) + find(dp, m, n, i, j+1);
        return dp[i][j];
    }
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, -1));
        return find(dp, m, n, 0, 0);
    }
};

Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a ⭐ star to the rishabhv12/Daily-Leetcode-Solution repository.