Grid Unique Paths InterviewBit Solution

Problem: Grid Unique Paths

Problem Description:

A robot is located at the top-left corner of an A x B grid.

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, from the upper-left corner.

How many possible unique paths are there?

Note: A and B will be such that the resulting answer fits in a 32 bit signed integer.

Example :

Input : A = 2, B = 2
Output : 2

2 possible routes : (0, 0) -> (0, 1) -> (1, 1) 
              OR  : (0, 0) -> (1, 0) -> (1, 1)

Approach

Method 1:

We can solve it using dynamic programming, as we can see that for any position, in the first row and the first column, the only answer is 1.

Say, dp[0][j] = dp[i][0] = 1, where, 0<=i<A & 0<=j<B

And for every other position say (i,j), the answer would be,

dp[i][j] = dp[i-1][j] + dp[i][j-1]

Because we can only move either down or right, so number of possible ways to reach a any given position, would be the sum of ways to rich its upper and left position.

Method 2:

You can see that to reach bottom-right from top-left, you have to take N + M - 2 steps.

Where N is the number of rows & M is the number of columns.

The above statement is true because you can move only down and right, so to reach the last column you must take M - 1 steps, and to reach the last row you must take N - 1 steps. So you have to take total of N + M - 2 steps.

Since you have to take M - 1 steps of right move, in total of N + M - 2 steps. Therefore, we have to choose the M - 1 from N + M - 2.

(N+M-2)C(M-1) = (N+M-2)! / (N-1)! (M-1)!

Time & Space Complexity:

Method 1:

Time Complexity: O(N^2)
Space Complexity: O(N^2)

Method 2:

Time Complexity: O(N)
Space Complexity: O(1)

Solution:

Method 1: Code in C++

Method 2: Code in C++