algoadvance

Leetcode 62. Unique Paths

Problem Statement

A robot is located at the top-left corner of an m x n grid. 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.

How many possible unique paths are there?

Clarifying Questions

  1. Input Constraints:
    • Minimum value for m and n: 1
    • Maximum value for m and n: 100
  2. Types of movement:
    • Can only move down or right.
  3. Output:
    • Single integer representing the number of unique paths.

Strategy

This problem can be solved using dynamic programming. We’ll create a 2D DP array where dp[i][j] represents the number of unique paths to reach cell (i, j).

  1. Initialization:
    • There’s only one way to reach any cell in the first row — by moving right.
    • There’s only one way to reach any cell in the first column — by moving down.
  2. Transition:
    • For each cell (i, j), the number of ways to get there is the sum of the number of ways to get to the cell directly above (dp[i-1][j]) and the number of ways to get to the cell directly to the left (dp[i][j-1]).
  3. Final Value:
    • The value in dp[m-1][n-1] will be our answer.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int uniquePaths(int m, int n) {
        // Initialize the DP table with size m x n filled with 0
        vector<vector<int>> dp(m, vector<int>(n, 0));
        
        // Set the first row cells to 1
        for(int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        
        // Set the first column cells to 1
        for(int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        
        // Fill the rest of the DP table
        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];
            }
        }
        
        // The bottom-right cell contains the number of unique paths
        return dp[m-1][n-1];
    }
};

Time Complexity

The time complexity of this solution is (O(m \times n)) because we need to fill in an m x n table.

Space Complexity

The space complexity of this solution is (O(m \times n)) due to the use of a 2D DP array to keep track of the number of paths to each cell.

This approach ensures that we efficiently calculate the number of unique paths using dynamic programming, considering the constraints provided in the problem.

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