InterviewCrunch

Beta

Unique Paths

Medium

Question

There is a robot in a grid that can move only rightward or downward at any point in time.

Given the dimensions of the grid, return the number of possible unique paths that the robot can take to travel from the top-left corner to bottom-right corner of the grid.

Unique Paths Example 1

Input: rows = 3, cols = 2

Output: 3

From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:

  1. Right -> Down -> Down
  2. Down -> Down -> Right
  3. Down -> Right -> Down
Unique Paths Example 2

Input: rows = 3, cols = 7

Output: 28

There are 28 ways to reach from the top-left to bottom-right corner.

Unique Paths Example 3

Input: row = 1, cols = 5

Output: 1

There is only one way to go from the top-left corner to bottom-right corner.

Clarify the problem

What are some questions you'd ask an interviewer?

Understand the problem

What should we use for our base case? Assume we use rows and cols as the memoization state.
f(0, 0) = 1
f(0, col) = 1 and f(row, 0) = 1
f(0, 0) = 0
f(0, y) = 0 and f(x, 0) = 0

Login or signup to save your code.

Notes

PrevCoin Change
NextCoding Pattern: Backtracking