🎨Now live: Try our Free AI Image Generation Feature

Description
Given two integers m
and n
, representing the number of rows and columns in a grid respectively, find the number of unique paths from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any point in time.
Intuition
The problem can be approached using dynamic programming. The number of unique paths to each cell is the sum of the unique paths to the cell directly above it and the cell directly to its left. This is because you can only move down or right.
Approach
- Create a 1D array
arr
of sizen
and initialize all elements to 1. This represents the number of ways to reach each cell in the first row. - Iterate from the second row to the last row (
i
from 1 tom-1
). - For each row, iterate through each column starting from the second column (
j
from 1 ton-1
). - Update
arr[j]
as the sum ofarr[j-1]
andarr[j]
, which represents the number of ways to reach the current cell from the left and the top cells. - Return the last element in the array
arr
, which represents the number of unique paths to the bottom-right corner of the grid.
Complexity
Time complexity:
O(m * n)
, where m
is the number of rows and n
is the number of columns. We iterate over each cell in the grid once.
Space complexity:
O(n)
, where n
is the number of columns. We use a 1D array to store the number of ways to reach each cell in the current row.
Code
C++
class Solution {
public:
int uniquePaths(int m, int n) {
vector arr(n, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
arr[j] = arr[j - 1] + arr[j];
}
}
return arr[n - 1];
}
};
Python
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
arr = [1] * n
for i in range(1, m):
for j in range(1, n):
arr[j] += arr[j - 1]
return arr[-1]
Java
class Solution {
public int uniquePaths(int m, int n) {
int[] arr = new int[n];
Arrays.fill(arr, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
arr[j] = arr[j - 1] + arr[j];
}
}
return arr[n - 1];
}
}
JavaScript
var uniquePaths = function (m, n)
{
const arr = Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
arr[j] = arr[j - 1] + arr[j];
};
};
return arr.at(-1);
};