C++: Unique Paths

Thought Process

The problem requires finding the number of unique paths from the top-left corner to the bottom-right corner of a grid. We use a dynamic programming to solve this. We create a 2D array grid where grid[i][j] represents the number of unique paths to reach cell (i, j). For the first row and first column, there is only one way to reach any cell (by moving only right or down). For other cells, the number of paths is the sum of paths from the top cell and the left cell. This ensures we build the solution incrementally. 

class Solution {
public:
    int uniquePaths(int m, int n) {
        
        int grid[n][m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){

                if(i==0 || j==0)
                    grid[i][j]=1;
                else // To reach (i,j)-> There are only two possible ways. Either from Top or from Left.
                    grid[i][j] = grid[i-1][j]+grid[i][j-1]; 
            }
        }
        return grid[n-1][m-1];
    }
};

Code Complexity

Time Complexity: O(m * n)

The algorithm iterates through each cell of the grid, resulting in a time complexity of O(m * n), where m and n are the dimensions of the grid.

Space Complexity: O(m * n)

The algorithm uses a 2D array of size m x n to store intermediate results.

Code copied!