Watch 3 video solutions for Maximum Score From Grid Operations, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by codingMohan has 2,621 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 jth column starting from the top row down to the ith 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 <= 100n == grid[i].length0 <= grid[i][j] <= 109Problem Overview: You are given a matrix where grid operations allow selecting cells column by column to maximize a total score. The challenge is determining the optimal row boundary for each column so the accumulated values produce the highest score across the grid.
Approach 1: Brute Force Enumeration (Exponential Time, O(n^m) time, O(1) space)
The naive idea is to try every possible configuration of column operations. For each column, you choose a row cutoff and evaluate the resulting score contribution from the grid. This means iterating through every possible combination of row boundaries across all columns and recomputing the score by scanning the matrix. While straightforward, the number of possibilities grows exponentially with the number of columns, making it impractical for larger grids. This approach mainly helps understand the decision space before introducing optimization.
Approach 2: Dynamic Programming with Prefix Sums (O(n^2) time, O(n^2) space)
A more practical solution uses prefix sums to quickly compute column segment sums and dynamic programming to track the best score as you process columns from left to right. Precompute prefix sums for each column so any vertical segment can be evaluated in constant time. Define a DP state representing the maximum score when the previous column ended at a specific row boundary. When processing the next column, iterate through possible row cutoffs and transition between states by combining the previous score with the new column's contribution. This removes repeated recomputation and collapses the exponential search space into a manageable quadratic DP.
The key insight is that column operations are independent except for the boundary chosen in the previous column. Once you cache results in DP states and compute sums using prefix arrays, each transition becomes constant time. This technique is common in grid optimization problems involving matrix traversal and cumulative scoring.
Recommended for interviews: The dynamic programming approach with prefix sums is the expected solution. Brute force demonstrates you understand the decision space and scoring mechanics, but interviewers look for the DP transition that eliminates repeated calculations and achieves quadratic complexity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^m) | O(1) | Understanding the full search space or validating small test cases |
| Dynamic Programming + Prefix Sum | O(n^2) | O(n^2) | General case and interview solution where repeated column computations must be optimized |