algoadvance

Leetcode 62. Unique Paths

Problem Statement:

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Write a function uniquePaths(int m, int n) that returns the number of unique paths from the top-left corner to the bottom-right corner of the grid.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3

Constraints:

Clarifying Questions:

  1. Can we assume inputs are always valid (i.e., m and n are always greater than or equal to 1)?
  2. Is the grid always rectangular?
  3. Are there any obstacles in the grid, or is it an open grid?

Strategy:

To solve this problem, we can use dynamic programming. The idea is to create a 2D DP table where dp[i][j] represents the number of unique paths to reach the cell (i, j).

  1. Initialization:
    • The robot can only move right or down, so the first row and the first column will have only 1 unique path to any cell along them because to reach any cell in the first row, the robot must have come all the way from the left, and to reach any cell in the first column, the robot must have come all the way from the top.
  2. Transition:
    • For other cells, the robot can come either from the left cell (i, j-1) or from the top cell (i-1, j). So, the number of unique paths to dp[i][j] will be the sum of unique paths from these two cells:
      • dp[i][j] = dp[i-1][j] + dp[i][j-1]
  3. Result:
    • The value at dp[m-1][n-1] will give the number of unique paths to reach the bottom-right corner of the grid.

Code:

public class UniquePaths {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // Initialize the first row and first column
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }

        // Fill the rest of the dp array
        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];
    }

    public static void main(String[] args) {
        UniquePaths solution = new UniquePaths();
        System.out.println(solution.uniquePaths(3, 7)); // Output: 28
        System.out.println(solution.uniquePaths(3, 2)); // Output: 3
    }
}

Time Complexity:

The time complexity for filling the DP table is O(m * n) since we are iterating through each cell once. The space complexity is also O(m * n) due to the storage required for the DP table.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI