64. Minimum Path Sum

#dp

Problem

Minimum Path Sum - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public int minPathSum(int[][] grid) {
        // R -> No. of rows, C -> No. of columns
        // Time Complexity: O(R*C), need to visit all the cells only once
        // Space Complexity: O(1), no extra space is used. 
            // Input only used to store subproblem results

        int R = grid.length; // Number of rows
        int C = grid[0].length; // Number of columns

        // Iterate over each cell in the grid
        for (int row = 0; row < R; row++) {
            for (int col = 0; col < C; col++) {
                if (row == 0 && col == 0) {
                    // Skip the top-left cell since it has no incoming paths
                    continue;
                } else if (row == 0) {
                    // For cells in the first row, only consider the path from the left
                    grid[0][col] += grid[0][col - 1];
                } else if (col == 0) {
                    // For cells in the first column, only consider the path from above
                    grid[row][0] += grid[row - 1][0];
                } else {
                    // For other cells, choose the minimum path from above and from the left,
                    // and add it to the current cell's value
                    int up = grid[row - 1][col];
                    int left = grid[row][col - 1];
                    grid[row][col] += Math.min(up, left);
                }
            }
        }
        return grid[R - 1][C - 1]; // Return the minimum path sum at the bottom-right cell
    }
}