Unique Path Problem Solved ( C++, Java, Python)

 

Dynamic Programming is one of the important topics in DSA because it helps us compute the values already calculated in minimum time by storing them in another array. In this article, we will discuss a Unique Paths problem which is also solved using dynamic programming.

Unique Path Problem Explained

In the Unique Path problem, you are given a 2-D matrix in which you are standing at the top-left corner. You have to reach the bottom-right corner. Print the total number of the unique paths that lay you from top-left to bottom-right.

Let’s examine this with an example:

Input:  n = 3, m = 2

Output: 3

Note: There is no obstacle present in between, so 1 path is always possible.

The naive approach is to recursively go to each cell and add the total number of paths possible. Let’s examine this approach step by step.

1. First, create a function that will recursively traverse the array.
2. Then move from the top-left corner to the bottom-right corner by either moving right or done.
3. We will check if at any point our index goes out of the matrix we will return 0. If the index becomes equal to the bottom-right cell we will return 1.
4. Keep on adding the possibility each time.
5. Return the total number of possible paths.

The time complexity here will be is O(2^n) as we are recursively traversing the matrix to find each possible path. Here n is the number of rows. The space complexity is O(1)  as we are not using any extra space.

Dynamic Programming Approach

In the above code, we are recursively traversing the whole array which lays to a huge time complexity of O(2^N).

To reduce this we can make use of dynamic programming. In this, we will store the previously computed values in an array. So that if they will repeat we do not have to compute it again instead we will use that stored value.

Let’s examine this approach.

1. First, create a 2D- array which will store the computed value. They should be of size n*m. Where n is the number of rows and m is the number of columns.
2. Initialize all the values in that array with -1.
3. Create the same function as we created in the recursive approach.
4. Check if the index goes out of the bound or not. If it goes out of the bound return 0.
5. Otherwise, check if the index is the same as the bottom-right cell. If it is returned 1.
6. If not check if you had previously calculated that value or not. If you had already calculated that value return that value.
7. Otherwise, call the function by either moving in a right or downward direction. Make sure to store these values in the created array.
8. Return the value of the array at last.

The time complexity now is O(N*M) where N is the number of rows and M is the number of columns. As we are storing values that had reduced our time complexity from O(2^N) to O(N*M). The space complexity is O(N*M) as we are using an extra space to store the repeated values.

Space Optimized Approach

In the above approach, we are using O(N*M) space complexity which is huge. We can also reduce this space complexity to O(N) if we use the previously computed values in the bottom-up approach in Dynamic Programming.

Let’s examine this approach step by step.

1. First, create 2 arrays one is current, and the other is previous.
2. Initialize the prv array with 1 because if only one row is present there is only 1 way to reach the destination.
3. Now create a loop that moves from each row starting from (1 to n-1) and a nested loop that moves from (1 to m-1).
4. Now make curr[i] = curr[i-1] + prv[i]. Here i is the column.
5. After the nested loop is over update the curr = prv.
6. After both loops are over return curr[m-1].

The time complexity for the space-optimized approach to solving the Unique Path problem is O(N*M) as we are running two loops. The space complexity of the above code is reduced to O(M) as we are just storing the previous and current row values.

Optimized Math Approach

In the above approach, we are still using too much time and space complexity. We can also overcome this by carefully observing the matrix.

As we do not have obstacles we can choose any (n-1) rows and (m-1) columns from (n+m-2) cells. So selecting n-1 rows and m-1 columns from the given n+m-2 cells we use factorial i.e. ( (n+m-2)! ) / ( (n-1)! ) *( (m-1)! ).

Let’s examine the code for the above approach.

C++ Code

Here is the C++ solution to solve the Unique Path problem:

#include<bits/stdc++.h>
using namespace std;

int find_path(int n, int m){

    long long int ans = 1;

    //We had already divided the (m+n-2)! with (n-1)!

    for(long int i = n; i<(m+n-1); i++){

        ans = ans*i;

    // as we want to divide it with (m-1)! and we are moving live 1, 2, .... m-1

        ans = ans/(i-n+1);

    }

    return ans;

}

int main(){

    int n = 4, m = 5;

    int result = find_path(n,m);

    // output: 35

    cout<<result<<endl;

    return 0;

}

Java Code

We can implement it in Java also:

public class Main {

    public static long findPath(int n, int m) {

        long ans = 1;

        for (long i = n; i < (m + n - 1); i++) {

            ans = ans * i;

            ans = ans / (i - n + 1);

        }

        return ans;

    }

    public static void main(String[] args) {

        int n = 4, m = 5;

        long result = findPath(n, m);

        // output: 35

        System.out.println(result);

    }

}

Python Code

Below is the same code in Python:

def find_path(n, m):

    ans = 1

    for i in range(n, m + n - 1):

        ans *= i

        ans //= (i - n + 1)

    return ans

def main():

    n, m = 4, 5

    result = find_path(n, m)

    # output: 35

    print(result)

if __name__ == "__main__":

    main()

Output: 

35

The time complexity for the above code is O(K) where K is the maximum of (N, M). As we are running just one loop. The space complexity is also reduced to O(1) as we are not using any extra space.

You can compare all the three approaches below:

Conclusion

Now you know the solution to the Unique Path problem from leetcode using different approaches. We can see that dynamic programming approach which had reduced our time complexity from O(2^N) to O(N*M). But the best way to solve this is a mathematical approach which reduces both our time and space complexity.