{"id":2333,"date":"2024-03-11T13:00:00","date_gmt":"2024-03-11T13:00:00","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=2333"},"modified":"2024-03-13T07:04:02","modified_gmt":"2024-03-13T07:04:02","slug":"unique-path-problem","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/unique-path-problem\/","title":{"rendered":"Unique Path Problem Solved ( C++, Java, Python)"},"content":{"rendered":"\n

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.<\/p>\n\n\n\n

Unique Path Problem Explained<\/strong><\/h2>\n\n\n\n

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. <\/strong><\/p>\n\n\n\n

Let\u2019s examine this with an example:<\/p>\n\n\n\n

Input<\/strong>:  n = 3, m = 2<\/p>\n\n\n\n

\"Matrix<\/figure>\n\n\n\n

Output<\/strong>: 3<\/p>\n\n\n\n

\"All<\/figure>\n\n\n\n

Note:<\/strong> There is no obstacle present in between, so 1 path is always possible.<\/p>\n\n\n\n

The naive approach is to recursively<\/a> go to each cell and add the total number of paths possible. Let\u2019s examine this approach step by step.<\/p>\n\n\n\n

    \n
  1. First, create a function that will recursively traverse the array.<\/li>\n\n\n\n
  2. Then move from the top-left corner to the bottom-right corner by either moving right or done.<\/li>\n\n\n\n
  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.<\/li>\n\n\n\n
  4. Keep on adding the possibility each time.<\/li>\n\n\n\n
  5. Return the total number of possible paths.<\/li>\n\n\n\n
  6. <\/li>\n<\/ol>\n\n\n\n

    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)\u00a0 as we are not using any extra space.<\/p>\n\n\n\n

    Dynamic Programming Approach<\/strong><\/h2>\n\n\n\n

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

    To reduce this we can make use of dynamic programming<\/a>. 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.<\/p>\n\n\n\n

    Let\u2019s examine this approach.<\/p>\n\n\n\n

      \n
    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.<\/li>\n\n\n\n
    2. Initialize all the values in that array with -1.<\/li>\n\n\n\n
    3. Create the same function as we created in the recursive approach.<\/li>\n\n\n\n
    4. Check if the index goes out of the bound or not. If it goes out of the bound return 0.<\/li>\n\n\n\n
    5. Otherwise, check if the index is the same as the bottom-right cell. If it is returned 1.<\/li>\n\n\n\n
    6. If not check if you had previously calculated that value or not. If you had already calculated that value return that value.<\/li>\n\n\n\n
    7. Otherwise, call the function by either moving in a right or downward direction. Make sure to store these values in the created array.<\/li>\n\n\n\n
    8. Return the value of the array at last.<\/li>\n<\/ol>\n\n\n\n

      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.<\/p>\n\n\n\n

      Space Optimized Approach<\/strong><\/h2>\n\n\n\n

      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.<\/p>\n\n\n\n

      Let\u2019s examine this approach step by step.<\/p>\n\n\n\n

        \n
      1. First, create 2 arrays one is current, and the other is previous.<\/li>\n\n\n\n
      2. Initialize the prv array with 1 because if only one row is present there is only 1 way to reach the destination.<\/li>\n\n\n\n
      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).<\/li>\n\n\n\n
      4. Now make curr[i] = curr[i-1] + prv[i]. Here i is the column.<\/li>\n\n\n\n
      5. After the nested loop is over update the curr = prv.<\/li>\n\n\n\n
      6. After both loops are over return curr[m-1].<\/li>\n\n\n\n
      7. <\/li>\n<\/ol>\n\n\n\n

        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.<\/p>\n\n\n\n

        Optimized Math Approach<\/strong><\/h2>\n\n\n\n

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

        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)! ).<\/p>\n\n\n\n

        Let\u2019s examine the code for the above approach.<\/p>\n\n\n\n

        C++ Code<\/strong><\/h3>\n\n\n\n

        Here is the C++ solution to solve the Unique Path problem:<\/p>\n\n\n\n

        #include<bits\/stdc++.h>\nusing namespace std;\n\nint find_path(int n, int m){\n\n\u00a0\u00a0\u00a0\u00a0long long int ans = 1;\n\n\u00a0\u00a0\u00a0\u00a0\/\/We had already divided the (m+n-2)! with (n-1)!\n\n\u00a0\u00a0\u00a0\u00a0for(long int i = n; i<(m+n-1); i++){\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans = ans*i;\n\n\u00a0\u00a0\u00a0\u00a0\/\/ as we want to divide it with (m-1)! and we are moving live 1, 2, .... m-1\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans = ans\/(i-n+1);\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0return ans;\n\n}\n\nint main(){\n\n\u00a0\u00a0\u00a0\u00a0int n = 4, m = 5;\n\n\u00a0\u00a0\u00a0\u00a0int result = find_path(n,m);\n\n\u00a0\u00a0\u00a0\u00a0\/\/ output: 35\n\n\u00a0\u00a0\u00a0\u00a0cout<<result<<endl;\n\n\u00a0\u00a0\u00a0\u00a0return 0;\n\n}<\/pre><\/div>\n\n\n\n
        Java Code<\/strong><\/h3>\n\n\n\n
        We can implement it in Java also:<\/p>\n\n\n\n
        public class Main {\n\n\u00a0\u00a0\u00a0\u00a0public static long findPath(int n, int m) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0long ans = 1;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0for (long i = n; i < (m + n - 1); i++) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans = ans * i;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans = ans \/ (i - n + 1);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0return ans;\n\n\u00a0\u00a0\u00a0\u00a0}\n\n\u00a0\u00a0\u00a0\u00a0public static void main(String[] args) {\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0int n = 4, m = 5;\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0long result = findPath(n, m);\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\/\/ output: 35\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0System.out.println(result);\n\n\u00a0\u00a0\u00a0\u00a0}\n\n}<\/pre><\/div>\n\n\n\n
        Python Code<\/strong><\/h3>\n\n\n\n
        Below is the same code in Python:<\/p>\n\n\n\n
        def find_path(n, m):\n\n\u00a0\u00a0\u00a0\u00a0ans = 1\n\n\u00a0\u00a0\u00a0\u00a0for i in range(n, m + n - 1):\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans *= i\n\n\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0ans \/\/= (i - n + 1)\n\n\u00a0\u00a0\u00a0\u00a0return ans\n\ndef main():\n\n\u00a0\u00a0\u00a0\u00a0n, m = 4, 5\n\n\u00a0\u00a0\u00a0\u00a0result = find_path(n, m)\n\n\u00a0\u00a0\u00a0\u00a0# output: 35\n\n\u00a0\u00a0\u00a0\u00a0print(result)\n\nif __name__ == "__main__":\n\n\u00a0\u00a0\u00a0\u00a0main()<\/pre><\/div>\n\n\n\n
        Output:<\/strong> <\/p>\n\n\n\n
        35<\/code><\/pre>\n\n\n\n
        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.<\/p>\n\n\n\n
        You can compare all the three approaches below:<\/p>\n\n\n\n
        Approach<\/th>Time Complexity<\/th>Space Complexity<\/th>Description<\/th><\/tr><\/thead>
        Brute Force<\/td>O(2^N)<\/td>O(1)<\/td>We are recursively traversing all the possible paths in the matrix.<\/td><\/tr>
        Memoization<\/td>O(N*M)<\/td>O(N*M)<\/td>We are using a 2D- array to store the repeated values.<\/td><\/tr>
        Space Optimized<\/td>O(N*M)<\/td>O(M)<\/td>We are just using the previous and the current row values which had reduced our space complexity to O(M).<\/td><\/tr>
        Optimized Appr.<\/td>O(K)   K = max(N, M)<\/td>O(1)<\/td>We are using a combination formula to compute the total number of paths. <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
        Conclusion<\/strong><\/h2>\n\n\n\n
        Now you know the solution to the Unique Path problem from leetcode<\/a> 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. <\/p>\n","protected":false},"excerpt":{"rendered":"
        Understand the Unique Path problem from leetcode using dynamic programming with implementation in C++, Java, and Python.<\/p>\n","protected":false},"author":14,"featured_media":2335,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[14,8,15],"class_list":["post-2333","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dsa","tag-dynamic-programming","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/14"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=2333"}],"version-history":[{"count":2,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2333\/revisions"}],"predecessor-version":[{"id":2366,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/2333\/revisions\/2366"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/2335"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=2333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=2333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=2333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}