Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

Note: The grid above is 7×3, and is used to illustrate the problem.

This question appears originally from Google Treasure Hunt. This problem is interesting because it can be solved using multiple approaches.

Hint: Try to use the most direct way to solve it, and see if you can improve the efficiency.

Backtracking Solution:
The most direct way is to write code that traverses each possible path, which can be done using backtracking. When you reach row=m and col=n, you know you’ve reached the bottom-right corner, and there is one additional unique path to it. However, when you reach row>m or col>n, then it’s an invalid path and you should stop traversing. For any grid at row=r and col=c, you have two choices: Traverse to the right or traverse to the bottom. Therefore, the total unique paths at grid (r,c) is equal to the sum of total unique paths from the grid to the right and the grid below. Below is the backtracking code in 5 lines of code:

Improved Backtracking Solution using Memoization:
Although the above backtracking solution is easy to code, it is very inefficient in the sense that it recalculates the same solution for a grid over and over again. By caching the results, we prevent recalculation and only calculates when necessary. Here, we are using a dynamic programming (DP) technique called memoization.

Dynamic Programming Solution using Bottom-up Approach:
If you notice closely, the above DP solution is using a top-down approach. Now let’s try a bottom-up approach. Remember this important relationship that is necessary for this DP solution to work:

The total unique paths at grid (r,c) is equal to the sum of total unique paths from grid to the right (r,c+1) and the grid below (r+1,c).

How can this relationship help us solve the problem? We observe that all grids of the bottom edge and right edge must all have only one unique path to the bottom-right corner. Using this as the base case, we can build our way up to our solution at grid (1,1) using the relationship above.

The total unique paths at grid (r,c) is equal to the sum of total unique paths from grid to the right (r,c+1) and the grid below (r+1,c).

Combinatorial Solution:
It turns out this problem could be solved using combinatorics, which no doubt would be the most efficient solution. In order to see it as a combinatorial problem, there are some necessary observations. Look at the 7×3 sample grid in the picture above. Notice that no matter how you traverse the grids, you always traverse a total of 8 steps. To be more exact, you always have to choose 6 steps to the right (R) and 2 steps to the bottom (B). Therefore, the problem can be transformed to a question of how many ways can you choose 6R‘s and 2B‘s in these 8 steps. The answer is C(8,2) (or C(8,6)). Therefore, the general solution for a m x n grid is C(m+n-2, m-1).

Further Thoughts:

Now consider if some obstacles are added to the grids marked as ‘X’. How many unique paths would there be? A combinatorial solution is difficult to obtain (I don’t know myself, quite frankly), but the DP solution can be modified easily to accommodate this constraint.

VN:F [1.9.22_1171]
Rating: 4.9/5 (38 votes cast)
Unique Paths, 4.9 out of 5 based on 38 ratings

41 thoughts on “Unique Paths

  1. aNiceGuy

    The "mat[m][n+1] = 1;" in bottom up DP solution is a good trick to avoid special treatment in the for loop, good job!

    One suggestion: if we are using C/C++/Java etc., I'd rather to put first grid in [0,0] instead of [1,1] to save a little bit space, no big deal though.

    VA:F [1.9.22_1171]
    0
  2. 1337c0d3r

    Coding the lazy way is the way to go 🙂

    Yeah, I tried to use [0,0] but I think clarity is more important, so I decided on [1,1].

    VA:F [1.9.22_1171]
    0
  3. Yuan Jin

    this one actually reminds me a question – find if a string is interleaved by two other strings. 小尾羊from the mitbbs mentioned this could be done with d.p. Do you have time to elaborate it? Thanks!

    VA:F [1.9.22_1171]
    0
  4. Anonymous

    Couldn't the 1st backtrack code be reduced to only 3 lines like:

    if (r == m || c == n)
    return 1;
    return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);

    VA:F [1.9.22_1171]
    0
  5. 1337c0d3r

    @Yuan Jin:
    I think I know which question you are talking about. Just to be sure, could you elaborate the question more? A link to the question would be helpful too.

    VA:F [1.9.22_1171]
    0
  6. 1337c0d3r

    @Anonymous:
    Hmm… You might get the correct solution due to the edge row and columns on the bottom and the right has always exactly one way to reach the corner.

    However, if I change the question to add some obstacles to one of the grid in the edge column, your solution would no longer work, since your backtrack code did not traverse all the way to the corner of the grid.

    VA:F [1.9.22_1171]
    +1
  7. 1337c0d3r

    Sorry I messed up the formatting since I am experimenting with ads placement. I fixed it now and hopefully the ads do not interfere the content too much. Thanks for your comment as well, I would consider it.

    VA:F [1.9.22_1171]
    0
  8. Neeraj

    How are you assuming the bottom most row has just one choice. Shouldn't it have a choice to go up as well.
    For Grid
    A B C
    D E F
    G H I

    The path could ADGHEBCFI or ADGHI note that at position H you have two choices either go up or right (assuming the up node is not already visited)

    VA:F [1.9.22_1171]
    0
  9. Neeraj

    Never mind my previous comment I see it is a constraint that robot can either move down or right. I was considering a more general case where robot can move in any direction but cannot visit the already visited node.

    VA:F [1.9.22_1171]
    0
  10. pranay

    hi, what changes do we need to make in the bottom-up approach if the step size was equal to the value of the integer in the original grid?
    i.e instead of moving one step right or down , one would move by that many steps as the value of integer in the original grid.
    E.g
    for the following grid:
    2313
    1213
    1231
    3110
    the answer is 3

    VA:F [1.9.22_1171]
    0
  11. Jin

    Actually, us the followling way is simpler.

    int walks(int m, int n)
    {
    if (m==0 || n==0)
    return 1;
    else
    return walks(m-1, n) + walks(m, n-1);
    }

    VA:F [1.9.22_1171]
    0
  12. johny

    Hi, 1337:

    In your 2nd solution (Improved Backtracking Solution using Memoization), can’t understand why bt(int m, int n) calls backtrack(1, 1, m, n, mat), instead of backtrack(0, 0, m, n, mat)? Isn’t the top-left element indexed as (0, 0)?

    And, in your 3rd DP solution, why just set “mat[m][n+1] = 1”, and not “mat[m+1][n] = 1”? And, why the return value is mat[1][1], not mat[0][0]?

    Thanks,
    johny

    VA:F [1.9.22_1171]
    0
  13. slimboy

    Hey i1337,
    I couldn’t understand why you don’t use the mat[0][0] at all in ur implementation? Is there a specific reason why you do that?

    VA:F [1.9.22_1171]
    0
  14. Pingback: A Microsoft String Replacement Problem | 口├人人│의 Blog

  15. www

    can you explain the complexity of the backtracking algorithm? I read an interview question asking to compare complexity of all different algorithms. and i understand the DP one is O(m*n)

    Thanks!

    VA:F [1.9.22_1171]
    0
    1. 1337c0d3r Post author

      ahh… you are right, and thanks for pointing this out!
      Although memset accepts int as the second parameter, it is converted to an unsigned char, and this value is being used to fill each byte of the memory.

      However, the code works and I investigated a little to find out why. -1 is being converted to unsigned char, which is 255. That is, each bit is set to 1 for the entire byte. Therefore, with memset -1, each block of memory are being filled with 1’s. Since two complements of an -1 integer is all 4 bytes being filled with 1’s, it coincidentally becomes the value of -1 again, which explains why the above code works.

      Even though the code works, it is not my original intention. Thanks and I have modified the code to initialize the array using for loops.

      VN:F [1.9.22_1171]
      0
  16. akd

    hey..Why this +2 is added in dp bottom up solution.
    “int mat[M_MAX+2][N_MAX+2] = {0};”

    i did not get it. can you pl. explain this.

    thnx

    VA:F [1.9.22_1171]
    0
  17. UnderMonkey

    Hi i337, Is there a way to print all path AND use DP? It seems like by using DP, a node will be only traversed once. But if all path need to be printed, then some nodes will be traversed more than once, in order to reach the destination again and again, and get printed out. For example, in my code, if you don’t comment out DP, then only 1 path will be printed.

    VN:F [1.9.22_1171]
    0
  18. Qianqian

    Awesome website. I learned a lot in this forum.
    And just my two cents, to further simplify the code a little bit.
    There is no need to allocate a two dimensional array. We can reuse one array for a single row:

    int dp(int m, int n) {
    int paths[m]; // variable-sized array, allocated in stack.
    memset(paths, 0, sizeof(paths));
    paths[0] = 1;

    for (int i = 0; i < n; i++) {
    for (int j = 1; j < m; j++) {
    paths[j] += paths[j – 1];
    }
    }

    return paths[m – 1];
    }

    VA:F [1.9.22_1171]
    0
  19. Anonymous

    Very good post.
    Two minor things.
    1) the testing

    may not be necessary in this scenario (as mentioned by Anonymous in Nov 14th);

    2) the code for top-down DP approach can be simplified as follows

    VA:F [1.9.22_1171]
    0
  20. joey chow

    If the max of m and n is 100, it should be use double instead of int. (from my test, when m=n=99, C(98, 198) = 5.7165924488905366E57 ).
    And to avoid the multiplication and division on the big data, we can store and data as factor list, example: < 2, < >, < 6, <, >, < 100, <, >

    VN:F [1.9.22_1171]
    +1
  21. Rock

    VA:F [1.9.22_1171]
    0
  22. Yuan Zhang

    Could I simply say it is C_(m+n-2){m-1} (Choose m-1 out of m+n-2)? The robot needs to move n-1 steps rightward, and m-1 steps downward, so the total number of unique paths is choosing m-1 (or n-1) out from (m-1+n-1).

    VA:F [1.9.22_1171]
    +1
  23. Samueltheeng

    public class Solution {

    public int uniquePaths(int m, int n) {
    if (m == 1 || n == 1) return 1;
    double count = 1;
    for (int k = 0 ; k < n-1 ; k++){
    count *= (double)(m+n-2-k) / (double)(n-1-k);
    }

    return (int) (count+0.5);
    }
    }

    VN:F [1.9.22_1171]
    0
    1. Wolf

      I also used the same idea, since it more looks like a math problem to me. The only difference is that, I think you can use the BigInteger class to replace “double”, and hence guarantee the correctness in more general cases (when m and n are greater than 100).

      VN:F [1.9.22_1171]
      0
  24. Maxim

    We can calculate it using binomial koefficient.
    we have (m-1) + (n – 1) total steps. And only Math.min(m, n) – 1 possible turns.
    So if m > n result is (m + n – 2)!/((n – 1)!(m – 2)!)

    if m = 7 and n = 3 as in the example:
    8!/(2!*6!) = 28

    VA:F [1.9.22_1171]
    +2
  25. Shuai Zhao

    Calculate the combination number directly.

    VA:F [1.9.22_1171]
    0
  26. Pingback: LeetCode: Unique Paths | Jerry's Blog

  27. Gags

    public static int uniquePaths(int[][] matrix, int sx, int sy, int ex, int ey) {
    if (matrix == null) {
    return 0;
    }
    // set the row sx to 1
    for (int i = sx + 1; i <= ex; i++) {
    matrix[i][sy] = 1;
    }
    for (int i = sy + 1; i <= ey; i++) {
    matrix[sx][i] = 1;
    }
    for (int i = sx + 1; i <= ex; i++) {
    for (int j = sy + 1; j <= ey; j++) {
    matrix[i][j] = matrix[i – 1][j] + matrix[i][j – 1];
    }

    }
    return matrix[ex][ey];

    }

    VA:F [1.9.22_1171]
    0
  28. Gags

    VA:F [1.9.22_1171]
    0
  29. saransh

    In the case of combinatoric method, compiler is unable to deal with factorial of a big number (e.g. 100). what should I do ???

    VA:F [1.9.22_1171]
    0
  30. aleksandra

    I can not agree with the following statement: “Although the above backtracking solution is easy to code, it is very inefficient in the sense that it recalculates the same solution for a grid over and over again. ” .

    The proposed backtracking solution does not recalculate the same solution/path, in fact it never traverses through the same path. The problem about proposed solution is that by traversing one path, it reaches another path, and then it traverses though the reached path again to reach the final node (instead of using the “concatenation”. )

    e.g. in grid 3×3, the first backtracking path is reached by RIGHT->RIGHT->DOWN->DOWN. In further iteration, when we are placed in RIGHT->RIGHT->DOWN, the path goes to ->RIGHT (which is the first path). So second path reaches the first, and instead of returning +1 as solution, we are traversing again to the final destination.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*