Dare2Solve
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.
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.
arr
of size n
and initialize all elements to 1. This represents the number of ways to reach each cell in the first row.i
from 1 to m-1
).j
from 1 to n-1
).arr[j]
as the sum of arr[j-1]
and arr[j]
, which represents the number of ways to reach the current cell from the left and the top cells.arr
, which represents the number of unique paths to the bottom-right corner of the grid.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.
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.
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> 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];
}
};
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]
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];
}
}
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);
};