62. Unique Paths

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

1. Create a 1D array arr of size n and initialize all elements to 1. This represents the number of ways to reach each cell in the first row.
2. Iterate from the second row to the last row (i from 1 to m-1).
3. For each row, iterate through each column starting from the second column (j from 1 to n-1).
4. Update 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.
5. 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);
};