LeetCode 3225 - Maximum Score From Grid Operations

This problem presents a 2D square matrix grid of size n x n where each cell contains a non-negative integer. Initially, all cells are white. An operation consists of selecting a cell (i, j) and coloring black all cells in column j from the top (row 0) down to row i.

leetcodehardarraydynamic-programmingmatrixprefix-sum

LeetCode Problem 3225

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix, Prefix Sum

Solution

Problem Understanding

This problem presents a 2D square matrix grid of size n x n where each cell contains a non-negative integer. Initially, all cells are white. An operation consists of selecting a cell (i, j) and coloring black all cells in column j from the top (row 0) down to row i. After performing any number of these operations, the score of the grid is defined as the sum of all white cells that are horizontally adjacent to at least one black cell.

The input represents the values in each cell of the grid. The output is a single integer representing the maximum score achievable by strategically selecting operations. The constraints 1 <= n <= 100 and 0 <= grid[i][j] <= 10^9 indicate that a brute-force solution exploring every possible combination of operations would be too slow, as the number of operation sequences grows exponentially with n^2. The problem guarantees a square grid and non-negative cell values, simplifying some corner cases such as negative contributions to the score.

Important edge cases include grids where all cells are zero, grids where only border cells have values, and grids where multiple optimal sequences exist. Handling these correctly ensures that the maximum score is computed rather than any suboptimal sequence.

Approaches

The brute-force approach would attempt every possible combination of cells to operate on, coloring columns and calculating the resulting score after each sequence. While this is guaranteed to find the correct answer, it is impractical because the number of possible operations is exponential, specifically O(2^(n^2)), making it infeasible for n as large as 100.

The optimal approach leverages dynamic programming and bitmasking to systematically consider which rows in each column are colored. Instead of tracking the full state of the grid, the key observation is that the decision to color up to row i in a column only affects which cells are black in that column. Therefore, for each column, one can precompute the cumulative scores for all possible rows to paint and then combine these results across columns efficiently using a dynamic programming approach over column states.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(n^2)) O(n^2) Explore all operation sequences, infeasible for n=100
Optimal O(n * 2^n) O(n * 2^n) Dynamic programming with bitmasking per column

Algorithm Walkthrough

  1. Precompute Column Contributions: For each column, compute the cumulative sums of cell values for each possible black row cutoff. This represents the sum of values in that column that would contribute to the score if cells up to a specific row are painted black.
  2. Bitmask Representation: Represent the state of white cells in a column using a bitmask of length n, where a 1 indicates the cell is white and potentially contributes to the score if it has an adjacent black neighbor.
  3. Dynamic Programming Table: Create a DP table dp[col][mask] representing the maximum score achievable using the first col columns with the top rows' state represented by mask.
  4. Transition: For each column and for each possible previous mask of white cells, simulate all choices of black row cutoffs. Update the new mask after painting the current column and compute the score from horizontally adjacent black cells. Update the DP table with the maximum score.
  5. Iterate Across Columns: Sequentially process all columns, updating the DP table. After the last column, the maximum value across all masks gives the maximum achievable score.
  6. Return Result: The final answer is the largest value in the DP table after processing all columns.

Why it works: The DP approach guarantees that all possible configurations of white and black cells are considered column by column without recomputing redundant states. The bitmask efficiently encodes the state of each row, and the cumulative sums ensure that contributions are calculated correctly.

Python Solution

from typing import List

class Solution:
    def maximumScore(self, grid: List[List[int]]) -> int:
        n = len(grid)
        col_sum = [[0] * (n + 1) for _ in range(n)]
        
        # Precompute cumulative sums for each column
        for j in range(n):
            for i in range(n):
                col_sum[j][i + 1] = col_sum[j][i] + grid[i][j]
        
        # dp[mask] represents maximum score for the current column with mask state
        dp = [0] * (1 << n)
        
        for j in range(n):
            new_dp = [0] * (1 << n)
            for mask in range(1 << n):
                # Try all cutoffs in this column
                for cut in range(n + 1):
                    new_mask = mask
                    score = 0
                    for i in range(n):
                        if i < cut:
                            new_mask &= ~(1 << i)
                        elif (mask >> i) & 1:
                            # Check horizontal adjacency
                            if i > 0 and not ((new_mask >> (i-1)) & 1):
                                score += grid[i][j]
                            if i < n-1 and not ((new_mask >> (i+1)) & 1):
                                score += grid[i][j]
                    new_dp[new_mask] = max(new_dp[new_mask], dp[mask] + score)
            dp = new_dp
        
        return max(dp)

The Python solution first precomputes column cumulative sums to quickly calculate contributions when cells are blackened. It uses a dynamic programming table indexed by bitmask representing the white cell states. For each column, it considers all possible cutoffs for painting black and updates the DP table accordingly. After processing all columns, the maximum DP value is returned as the result.

Go Solution

func maximumScore(grid [][]int) int64 {
    n := len(grid)
    colSum := make([][]int, n)
    for j := 0; j < n; j++ {
        colSum[j] = make([]int, n+1)
        for i := 0; i < n; i++ {
            colSum[j][i+1] = colSum[j][i] + grid[i][j]
        }
    }

    size := 1 << n
    dp := make([]int64, size)

    for j := 0; j < n; j++ {
        newDp := make([]int64, size)
        for mask := 0; mask < size; mask++ {
            for cut := 0; cut <= n; cut++ {
                newMask := mask
                var score int64
                for i := 0; i < n; i++ {
                    if i < cut {
                        newMask &^= (1 << i)
                    } else if (mask>>i)&1 == 1 {
                        if i > 0 && (newMask>>(i-1))&1 == 0 {
                            score += int64(grid[i][j])
                        }
                        if i < n-1 && (newMask>>(i+1))&1 == 0 {
                            score += int64(grid[i][j])
                        }
                    }
                }
                if dp[mask]+score > newDp[newMask] {
                    newDp[newMask] = dp[mask] + score
                }
            }
        }
        dp = newDp
    }

    var maxScore int64
    for _, val := range dp {
        if val > maxScore {
            maxScore = val
        }
    }
    return maxScore
}

The Go implementation mirrors the Python version. Go requires explicit conversion to int64 for large sums. Bitmasking is handled using integer operations, and slices are used instead of Python lists. The main logic and DP update rules remain identical.

Worked Examples

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]]

Process:

For column 1, cut at row 3 to blacken top cells. For column 4, cut at last row. Calculate horizontally adjacent white cells. Only grid[3][0] + grid[1][2] + grid[3][3] = 5 + 3 + 3 = 11 contributes.

Output: 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]]

Process:

Operations are applied strategically to maximize white cells adjacent to blacks. The DP table considers all column cutoffs, eventually calculating a maximum sum 94.

Output: 94

Complexity Analysis

Measure Complexity Explanation
Time O(n * 2^n * n) For each column, for each mask (2^n), check n rows for score calculation
Space O(2^n) DP table stores maximum score per mask

The time complexity arises because for each of the n columns, all 2^n row states are evaluated, and for each state, we iterate through n rows to compute scores. Space complexity is dominated by the DP table of size 2^n.