Practice Maximum Score From Grid Operations
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Initially every cell of the square grid is white. An operation chooses a column and paints a prefix of that column black, from row 0 through a chosen row. After any number of operations, score each white cell's value once if its immediate left or right neighbor is black. Vertical neighbors do not qualify. Return the largest possible score; doing no operations is allowed. Approach: Represent each column by its black-prefix height h, from 0 to n. For three consecutive heights a,b,c, the middle column contributes the values in rows b through max(a,c)-1, or zero if this interval is empty. Column prefix sums give that contribution in constant time. Dynamic programming over the last two heights evaluates columns once both neighbors are known. Prefix/suffix maximum tables over candidate a values reduce transitions to O(n^3) total time and O(n^2) space. Treat missing edge columns as height zero; use wide integers. Worked example: Painting the entire first column black in [[2,7],[4,1]] leaves white cells with a total score of 7+1=8. A one-cell grid scores zero because it has no horizontal neighbor.
Source: Maximum Score From Grid Operations on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
grid = [[2,7],[4,1]]
8
# Example 2
grid = [[9]]
0
Constraints
How to solve Maximum Score From Grid Operations
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Every operation blackens a column prefix, so each column's final state is one number, its black height, and a white cell in column j scores exactly when its row is at least column j's height and below the taller of its two neighbors' heights. A column's score depends only on three consecutive heights, which makes a dynamic program over adjacent height pairs sufficient.
Why brute force is not enough
Enumerating all (n + 1)^n height assignments is exponential, and even a dynamic program over the last two heights that scans the third height in full costs O(n^4), about 10^8 steps for n = 100 with a sizable constant.
Approach
- Precompute per-column prefix sums of cell values so any row interval of a column is summed in constant time.
- Define the state after placing columns 0..j as the pair (height of column j - 1, height of column j) with columns 0..j - 1 already scored; a column is finalized only once its right neighbor's height is known.
- Extending to column j + 1 with height c, column j with height b and left neighbor a contributes its values in rows b through max(a, c) - 1, or nothing if empty; columns beyond both edges count as height 0.
- Split the maximization over a: when a is at most c the contribution depends only on b and c, so a prefix maximum of previous states over a suffices; when a exceeds c it depends on a and b but not c, so a suffix maximum of state plus contribution serves every c. This cuts each column from O(n^3) to O(n^2) transitions.
- After the last column, extend once more with a virtual height-0 column, take the maximum over states, and use 64-bit integers.
Walkthrough of Example 1
grid = [[2,7],[4,1]] → 8
- Column 0 holds 2 and 4, column 1 holds 7 and 1; heights range over 0, 1, 2 and virtual outer columns have height 0.
- Heights (2, 0): column 0 is all black and scores nothing; column 1 is all white beside a height-2 neighbor, so rows 0 and 1 score 7 + 1 = 8.
- Heights (0, 2): column 0 scores 2 + 4 = 6 and column 1 is all black, total 6.
- Heights (1, 0): column 0 row 1 has no black neighbor, column 1 row 0 scores 7, total 7; pairs (1, 2) and (2, 1) give 4 and 1.
- The best score is 8.
Time and space
Time O(n^3) · Space O(n^2). Each of the n columns has (n + 1)^2 height-pair states answered in O(1) via prefix and suffix maximum tables; only two layers of states plus column prefix sums are stored.
Interview pitfalls
- Scoring a white cell twice when both neighbors are black; the interval uses max(a, c), not a sum over both sides.
- Letting vertical neighbors trigger a score, or scoring black cells.
- Omitting the virtual height-0 columns at the edges, leaving the last column unscored or indexing out of range.
- Scoring a column when its own height is chosen rather than when its right neighbor is, which forces a three-height state and O(n^4) or worse.
- Using 32-bit accumulators when a single column can total 10^11.
Follow-up questions interviewers ask
- How does the recurrence change if operations paint a column suffix, or either a prefix or a suffix?
- Does the three-consecutive-heights structure extend to a rectangular grid with many more rows than columns?
- If the first and last columns were neighbors on a torus, how would you break the cycle?
Further reading on the technique: Dynamic programming
Related LeetCode Problems
Practice more problems similar to Maximum Score From Grid Operations.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.