LeetCode 62: Unique Paths Solution

Problem Explanation

Explanation:

To solve this problem, we can use dynamic programming. We will create a 2D array to store the number of unique paths to reach each cell in the grid. The number of unique paths to reach a cell is the sum of the number of paths to reach the cell above it and the cell to the left of it.

Initialize a 2D array dp of size m x n where dp[i][j] represents the number of unique paths to reach cell (i, j).
Initialize the first row and first column of dp with 1 since there is only one way to reach any cell in the first row or first column.
Iterate through the grid starting from (1, 1) and update dp[i][j] as dp[i-1][j] + dp[i][j-1].
Return dp[m-1][n-1] which represents the number of unique paths to reach the bottom-right corner.

Time complexity: O(m x n) where m is the number of rows and n is the number of columns.
Space complexity: O(m x n) for the 2D array dp.

Solution Code

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        return dp[m-1][n-1];
    }
}

Frequently Asked Questions

How to solve LeetCode 62 (Unique Paths)?

This page provides optimized solutions for LeetCode problem 62 (Unique Paths) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 62 (Unique Paths)?

The time complexity for LeetCode 62 (Unique Paths) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 62 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 62 in Java, C++, or Python.