Daily LeetCode - by Vítor Belim

Description

You are given a 2D matrix grid of size n x n. Initially, all cells of the grid are colored white. In one operation, you can select any cell of indices (i, j), and color black all the cells of the j^th column starting from the top row down to the i^th row.

The grid score is the sum of all grid[i][j] such that cell (i, j) is white and it has a horizontally adjacent black cell.

Return the maximum score that can be achieved after some number of operations.

Example 1:

Input: grid = [[0,0,0,0,0],[0,0,3,0,0],[0,1,0,0,0],[5,0,0,3,0],[0,0,0,0,2]]

Output: 11

Explanation:

In the first operation, we color all cells in column 1 down to row 3, and in the second operation, we color all cells in column 4 down to the last row. The score of the resulting grid is grid[3][0] + grid[1][2] + grid[3][3] which is equal to 11.

Example 2:

Input: grid = [[10,9,0,0,15],[7,1,0,8,0],[5,20,0,11,0],[0,0,0,1,2],[8,12,1,10,3]]

Output: 94

Explanation:

We perform operations on 1, 2, and 3 down to rows 1, 4, and 0, respectively. The score of the resulting grid is grid[0][0] + grid[1][0] + grid[2][1] + grid[4][1] + grid[1][3] + grid[2][3] + grid[3][3] + grid[4][3] + grid[0][4] which is equal to 94.

Constraints:

1 <= n == grid.length <= 100
n == grid[i].length
0 <= grid[i][j] <= 10⁹

Solutions

This code solves a grid optimization problem using dynamic programming where you select rows from each column to maximize a score. It maintains a DP table dp[i][currH][prevH] tracking the best score at column i when selecting currH rows in the current column and prevH rows in the previous column. The algorithm precomputes column prefix sums (colSum) to quickly calculate the sum of elements in any row range, then for each column, it computes the best score by considering two cases: if the current height is ≤ the previous height, you simply add the elements in the new range; if it's greater, you apply a penalty for the overlap. To avoid recalculating the maximum over many previous heights repeatedly, it maintains two optimization arrays—prevMax stores the best DP value up to each previous height, and prevSuffixMax stores the best value from each previous height to the end—allowing the algorithm to run in O(n³) instead of O(n⁴). Finally, it returns the maximum score found at the last column across all possible final heights.

Language: javascript(2026-04-29 09:09)DONE

CPU Performance30.77%

Memory Performance38.46%

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maximumScore = function (grid) {
    const n = grid.length;

    if (n === 1) {
        return 0;
    }

    const dp = Array(n);
    const prevMax = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
    const prevSuffixMax = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
    const colSum = Array.from({ length: n }, () => new Array(n + 1).fill(0));

    for (let c = 0; c < n; c++) {
        dp[c] = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));

        for (let r = 1; r <= n; r++) {
            colSum[c][r] = colSum[c][r - 1] + grid[r - 1][c];
        }
    }

    for (let i = 1; i < n; i++) {
        for (let currH = 0; currH <= n; currH++) {
            for (let prevH = 0; prevH <= n; prevH++) {
                if (currH <= prevH) {
                    dp[i][currH][prevH] = Math.max(
                        dp[i][currH][prevH],
                        prevSuffixMax[prevH][0] + colSum[i][prevH] - colSum[i][currH],
                    );
                } else {
                    dp[i][currH][prevH] = Math.max(
                        dp[i][currH][prevH],
                        prevSuffixMax[prevH][currH],
                        prevMax[prevH][currH] + colSum[i - 1][currH] - colSum[i - 1][prevH],
                    );
                }
            }
        }

        for (let currH = 0; currH <= n; currH++) {
            prevMax[currH][0] = dp[i][currH][0];

            for (let prevH = 1; prevH <= n; prevH++) {
                const penalty = prevH > currH ? colSum[i][prevH] - colSum[i][currH] : 0;
                prevMax[currH][prevH] = Math.max(
                    prevMax[currH][prevH - 1],
                    dp[i][currH][prevH] - penalty,
                );
            }

            prevSuffixMax[currH][n] = dp[i][currH][n];

            for (let prevH = n - 1; prevH >= 0; prevH--) {
                prevSuffixMax[currH][prevH] = Math.max(
                    prevSuffixMax[currH][prevH + 1],
                    dp[i][currH][prevH],
                );
            }
        }
    }

    let ans = 0;

    for (let k = 0; k <= n; k++) {
        ans = Math.max(ans, dp[n - 1][n][k], dp[n - 1][0][k]);
    }

    return ans;
};

Description

Solutions

AI Explanation