# 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++

## Comments