top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Grid Unique Paths InterviewBit Solution

Sep 5, 2020
2 min read

Updated: Sep 18, 2020


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



1 Comment


https://casinoappforuk.com the part about choosing M-1 right moves out of N+M-2 total steps is the bit that always gets me, since it turns what looks like a grid problem into plain combinatorics. I usually reach for the DP version first because it's easier to reason about, but seeing the O(N) factorial approach spelled out makes the tradeoff pretty clear. Small thing though, that space complexity for Method 1 should probably be O(N*M), not O(N^2), unless I'm missing something about the constraints.

Like
bottom of page