62. Unique Paths
https://leetcode.com/problems/unique-paths/
Above is a 7 x 3 grid. How many possible unique paths are there?
Related problems
63-unique-paths-ii
980-unique-paths-iii
---
Intuition
Starting at 0, 0
Unique paths to reach 0, 1 = 1
Unique paths to reach 1, 0 = 1
Unique paths to reach 1, 1 = Unique paths to reach 0, 1 + Unique paths to reach 1, 0
---
Time - O(r * c)
Space - O(r * c)
---
---
Follow up
We only need access to previous row to compute the current row.
We can reduce the space requirement to O(r)
Also we can pre fill 1st row to 1, and hard code first column to 1 for each row
So nested loops can run from 1 to r - 1, and 1 to c - 1
* We can further reduce memory requirement to smaller of the two dimensions, same approach will work
---
Time - O(r * c)
Space - O(r)
---
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?
Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3 Output: 28----
Related problems
63-unique-paths-ii
980-unique-paths-iii
---
Intuition
Starting at 0, 0
Unique paths to reach 0, 1 = 1
Unique paths to reach 1, 0 = 1
Unique paths to reach 1, 1 = Unique paths to reach 0, 1 + Unique paths to reach 1, 0
---
Time - O(r * c)
Space - O(r * c)
---
---
Follow up
We only need access to previous row to compute the current row.
We can reduce the space requirement to O(r)
Also we can pre fill 1st row to 1, and hard code first column to 1 for each row
So nested loops can run from 1 to r - 1, and 1 to c - 1
* We can further reduce memory requirement to smaller of the two dimensions, same approach will work
---
Time - O(r * c)
Space - O(r)
---
