LeetCode #62: Unique Paths

LeetCode Solutions

https://leetcode.com/problems/unique-paths/description/

To solve this problem, we can use dynamic programming. We create a 2D array path where path[i][j] represents the number of unique paths from the starting point (0, 0) to the point (i, j). Since we can only move right or down, the number of unique paths to (i, j) is the sum of the number of unique paths to (i-1, j) and (i, j-1).

Here are the steps to solve the problem:

  1. Create a 2D array path of size m x n, where m is the number of rows and n is the number of columns in the grid.
  2. Initialize the first row and column of the path array to 1, since there is only one way to reach any point in the first row or column.
  3. Loop through the path array starting from the second row and column, and calculate the number of unique paths to each point using the formula path[i][j] = path[i-1][j] + path[i][j-1].
  4. Return the last element of the path array, which represents the number of unique paths to the bottom-right corner of the grid.

Here’s the Python code that implements the above steps:

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        path = [[1] * n for _ in range(m)]
        for row in range(1, m):
            for col in range(1, n):
                path[row][col] = path[row-1][col] + path[row][col-1]
        return path[m-1][n-1]

Time and Space Complexity

The time complexity of this solution is O(mn), since we need to loop through the path array once for each element. The space complexity is also O(mn), since we need to create a 2D array of size m x n.