LeetCode #3225 — HARD

Maximum Score From Grid Operations

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

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⁹

Step 01

Brute Force Baseline

Problem summary: 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.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Dynamic Programming

Example 1

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

Example 2

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

Core Insight

What unlocks the optimal approach

Use dynamic programming.
Solve the problem in O(N^4) using a 3-states dp.
Let <code>dp[i][lastHeight][beforeLastHeight]</code> denote the maximum score if the grid was limited to column <code>i</code>, and the height of column <code>i - 1</code> is <code>lastHeight</code> and the height of column <code>i - 2</code> is <code>beforeLastHeight</code>.
The third state, <code>beforeLastHeight</code>, is used to determine which values of column <code>i - 1</code> will be added to the score. We can replace this state with another state that only takes two values 0 or 1.
Let <code>dp[i][lastHeight][isBigger]</code> denote the maximum score if the grid was limited to column <code>i</code>, and where the height of column <code>i - 1</code> is <code>lastHeight</code>. Additionally, if <code>isBigger == 1</code>, the number of black cells in column <code>i</code> is assumed to be larger than the number of black cells in column <code>i - 2</code>, and vice versa. Note that if our assumption is wrong, it would lead to a suboptimal score and, therefore, it would not be considered as the final answer.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3225: Maximum Score From Grid Operations
class Solution {
  public long maximumScore(int[][] grid) {
    final int n = grid.length;
    // prefix[j][i] := the sum of the first i elements in the j-th column
    long[][] prefix = new long[n][n + 1];
    // prevPick[i] := the maximum achievable score up to the previous column,
    // where the bottommost selected element in that column is in row (i - 1)
    long[] prevPick = new long[n + 1];
    // prevSkip[i] := the maximum achievable score up to the previous column,
    // where the bottommost selected element in the column before the previous
    // one is in row (i - 1)
    long[] prevSkip = new long[n + 1];

    for (int j = 0; j < n; ++j)
      for (int i = 0; i < n; ++i)
        prefix[j][i + 1] = prefix[j][i] + grid[i][j];

    for (int j = 1; j < n; ++j) {
      long[] currPick = new long[n + 1];
      long[] currSkip = new long[n + 1];
      // Consider all possible combinations of the number of current and
      // previous selected elements.
      for (int curr = 0; curr <= n; ++curr)
        for (int prev = 0; prev <= n; ++prev)
          if (curr > prev) {
            // 1. The current bottom is deeper than the previous bottom.
            // Get the score of grid[prev..curr)[j - 1] for pick and skip.
            final long score = prefix[j - 1][curr] - prefix[j - 1][prev];
            currPick[curr] = Math.max(currPick[curr], prevSkip[prev] + score);
            currSkip[curr] = Math.max(currSkip[curr], prevSkip[prev] + score);
          } else {
            // 2. The previous bottom is deeper than the current bottom.
            // Get the score of grid[curr..prev)[j] for pick only.
            final long score = prefix[j][prev] - prefix[j][curr];
            currPick[curr] = Math.max(currPick[curr], prevPick[prev] + score);
            currSkip[curr] = Math.max(currSkip[curr], prevPick[prev]);
          }
      prevPick = currPick;
      prevSkip = currSkip;
    }

    return Arrays.stream(prevPick).max().getAsLong();
  }
}

// Accepted solution for LeetCode #3225: Maximum Score From Grid Operations
package main

// https://space.bilibili.com/206214
func maximumScore(grid [][]int) (ans int64) {
	n := len(grid)
	colSum := make([][]int64, n)
	for j := range colSum {
		colSum[j] = make([]int64, n+1)
		for i, row := range grid {
			colSum[j][i+1] = colSum[j][i] + int64(row[j])
		}
	}

	f := make([][][2]int64, n)
	for j := range f {
		f[j] = make([][2]int64, n+1)
	}
	for j := 0; j < n-1; j++ {
		// 用前缀最大值优化
		preMax := f[j][0][1] - colSum[j][0]
		for pre := 1; pre <= n; pre++ {
			f[j+1][pre][0] = max(f[j][pre][0], preMax+colSum[j][pre])
			f[j+1][pre][1] = f[j+1][pre][0]
			preMax = max(preMax, f[j][pre][1]-colSum[j][pre])
		}

		// 用后缀最大值优化
		sufMax := f[j][n][0] + colSum[j+1][n]
		for pre := n - 1; pre > 0; pre-- {
			f[j+1][pre][0] = max(f[j+1][pre][0], sufMax-colSum[j+1][pre])
			sufMax = max(sufMax, f[j][pre][0]+colSum[j+1][pre])
		}

		// 单独计算 pre=0 的状态
		f[j+1][0][0] = sufMax // 无需考虑 f[j][0][0]，因为不能连续三列全白
		f[j+1][0][1] = max(f[j][0][0], f[j][n][0]) // 第 j 列要么全白，要么全黑
	}

	for _, row := range f[n-1] {
		ans = max(ans, row[0])
	}
	return ans
}

func maximumScore2(grid [][]int) (ans int64) {
	n := len(grid)
	colSum := make([][]int64, n)
	for j := range colSum {
		colSum[j] = make([]int64, n+1)
		for i, row := range grid {
			colSum[j][i+1] = colSum[j][i] + int64(row[j])
		}
	}

	f := make([][][2]int64, n)
	for j := range f {
		f[j] = make([][2]int64, n+1)
	}
	for j := 0; j < n-1; j++ {
		// pre 表示第 j+1 列的黑格个数
		for pre := 0; pre <= n; pre++ {
			// dec=1 意味着第 j+1 列的黑格个数 (pre) < 第 j+2 列的黑格个数
			for dec := 0; dec < 2; dec++ {
				res := int64(0)
				// 枚举第 j 列有 cur 个黑格
				for cur := 0; cur <= n; cur++ {
					if cur == pre { // 情况一：相等
						// 没有可以计入总分的格子
						res = max(res, f[j][cur][0])
					} else if cur < pre { // 情况二：右边黑格多
						// 第 j 列的第 [cur, pre) 行的格子可以计入总分
						res = max(res, f[j][cur][1]+colSum[j][pre]-colSum[j][cur])
					} else if dec == 0 { // 情况三：cur > pre >= 第 j+2 列的黑格个数
						// 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
						res = max(res, f[j][cur][0]+colSum[j+1][cur]-colSum[j+1][pre])
					} else if pre == 0 { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
						// 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
						// 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
						// 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
						res = max(res, f[j][cur][0])
					}
				}
				f[j+1][pre][dec] = res
			}
		}
	}

	for _, row := range f[n-1] {
		ans = max(ans, row[0])
	}
	return ans
}

func maximumScore3(grid [][]int) (ans int64) {
	n := len(grid)
	colSum := make([][]int64, n)
	for j := range colSum {
		colSum[j] = make([]int64, n+1)
		for i, row := range grid {
			colSum[j][i+1] = colSum[j][i] + int64(row[j])
		}
	}

	memo := make([][][2]int64, n-1)
	for i := range memo {
		memo[i] = make([][2]int64, n+1)
		for j := range memo[i] {
			memo[i][j] = [2]int64{-1, -1} // -1 表示没有计算过
		}
	}
	var dfs func(int, int, int) int64
	dfs = func(j, pre, dec int) int64 {
		if j < 0 {
			return 0
		}
		p := &memo[j][pre][dec]
		if *p != -1 { // 之前计算过
			return *p
		}
		res := int64(0)
		// 枚举第 j 列有 cur 个黑格
		for cur := 0; cur <= n; cur++ {
			if cur == pre { // 情况一：相等
				// 没有可以计入总分的格子
				res = max(res, dfs(j-1, cur, 0))
			} else if cur < pre { // 情况二：右边黑格多
				// 第 j 列的第 [cur, pre) 行的格子可以计入总分
				res = max(res, dfs(j-1, cur, 1)+colSum[j][pre]-colSum[j][cur])
			} else if dec == 0 { // 情况三：cur > pre >= 第 j+2 列的黑格个数
				// 第 j+1 列的第 [pre, cur) 行的格子可以计入总分
				res = max(res, dfs(j-1, cur, 0)+colSum[j+1][cur]-colSum[j+1][pre])
			} else if pre == 0 { // 情况四（凹形）：cur > pre < 第 j+2 列的黑格个数
				// 此时第 j+2 列全黑最优（递归过程中一定可以枚举到这种情况）
				// 第 j+1 列全白是最优的，所以只需考虑 pre=0 的情况
				// 由于第 j+1 列在 dfs(j+1) 的情况二中已经统计过，这里不重复统计
				res = max(res, dfs(j-1, cur, 0))
			}
		}
		*p = res // 记忆化
		return res
	}

	// 枚举第 n-1 列有 i 个黑格
	for i := 0; i <= n; i++ {
		ans = max(ans, dfs(n-2, i, 0))
	}
	return
}

# Accepted solution for LeetCode #3225: Maximum Score From Grid Operations
class Solution:
  def maximumScore(self, grid: list[list[int]]) -> int:
    n = len(grid)
    # prefix[j][i] := the sum of the first i elements in the j-th column
    prefix = [[0] * (n + 1) for _ in range(n)]
    # prevPick[i] := the maximum score up to the previous column, where the
    # bottommost selected element in the previous column is in row (i - 1)
    prevPick = [0] * (n + 1)
    # prevSkip[i] := the maximum score up to the previous column, where the
    # bottommost selected element in the column before the previous one is in
    # row (i - 1)
    prevSkip = [0] * (n + 1)

    for j in range(n):
      for i in range(n):
        prefix[j][i + 1] = prefix[j][i] + grid[i][j]

    for j in range(1, n):
      currPick = [0] * (n + 1)
      currSkip = [0] * (n + 1)
      # Consider all possible combinations of the number of current and
      # previous selected elements.
      for curr in range(n + 1):  # the number of current selected elements
        for prev in range(n + 1):  # the number of previous selected elements
          if curr > prev:
            # 1. The current bottom is deeper than the previous bottom.
            # Get the score of grid[prev..curr)[j - 1] for both pick and skip.
            score = prefix[j - 1][curr] - prefix[j - 1][prev]
            currPick[curr] = max(currPick[curr], prevSkip[prev] + score)
            currSkip[curr] = max(currSkip[curr], prevSkip[prev] + score)
          else:
            # 2. The previous bottom is deeper than the current bottom.
            # Get the score of grid[curr..prev)[j] for pick only.
            score = prefix[j][prev] - prefix[j][curr]
            currPick[curr] = max(currPick[curr], prevPick[prev] + score)
            currSkip[curr] = max(currSkip[curr], prevPick[prev])
      prevPick = currPick
      prevSkip = currSkip

    return max(prevPick)

// Accepted solution for LeetCode #3225: Maximum Score From Grid Operations
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (java):
// // Accepted solution for LeetCode #3225: Maximum Score From Grid Operations
// class Solution {
//   public long maximumScore(int[][] grid) {
//     final int n = grid.length;
//     // prefix[j][i] := the sum of the first i elements in the j-th column
//     long[][] prefix = new long[n][n + 1];
//     // prevPick[i] := the maximum achievable score up to the previous column,
//     // where the bottommost selected element in that column is in row (i - 1)
//     long[] prevPick = new long[n + 1];
//     // prevSkip[i] := the maximum achievable score up to the previous column,
//     // where the bottommost selected element in the column before the previous
//     // one is in row (i - 1)
//     long[] prevSkip = new long[n + 1];
// 
//     for (int j = 0; j < n; ++j)
//       for (int i = 0; i < n; ++i)
//         prefix[j][i + 1] = prefix[j][i] + grid[i][j];
// 
//     for (int j = 1; j < n; ++j) {
//       long[] currPick = new long[n + 1];
//       long[] currSkip = new long[n + 1];
//       // Consider all possible combinations of the number of current and
//       // previous selected elements.
//       for (int curr = 0; curr <= n; ++curr)
//         for (int prev = 0; prev <= n; ++prev)
//           if (curr > prev) {
//             // 1. The current bottom is deeper than the previous bottom.
//             // Get the score of grid[prev..curr)[j - 1] for pick and skip.
//             final long score = prefix[j - 1][curr] - prefix[j - 1][prev];
//             currPick[curr] = Math.max(currPick[curr], prevSkip[prev] + score);
//             currSkip[curr] = Math.max(currSkip[curr], prevSkip[prev] + score);
//           } else {
//             // 2. The previous bottom is deeper than the current bottom.
//             // Get the score of grid[curr..prev)[j] for pick only.
//             final long score = prefix[j][prev] - prefix[j][curr];
//             currPick[curr] = Math.max(currPick[curr], prevPick[prev] + score);
//             currSkip[curr] = Math.max(currSkip[curr], prevPick[prev]);
//           }
//       prevPick = currPick;
//       prevSkip = currSkip;
//     }
// 
//     return Arrays.stream(prevPick).max().getAsLong();
//   }
// }

// Accepted solution for LeetCode #3225: Maximum Score From Grid Operations
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #3225: Maximum Score From Grid Operations
// class Solution {
//   public long maximumScore(int[][] grid) {
//     final int n = grid.length;
//     // prefix[j][i] := the sum of the first i elements in the j-th column
//     long[][] prefix = new long[n][n + 1];
//     // prevPick[i] := the maximum achievable score up to the previous column,
//     // where the bottommost selected element in that column is in row (i - 1)
//     long[] prevPick = new long[n + 1];
//     // prevSkip[i] := the maximum achievable score up to the previous column,
//     // where the bottommost selected element in the column before the previous
//     // one is in row (i - 1)
//     long[] prevSkip = new long[n + 1];
// 
//     for (int j = 0; j < n; ++j)
//       for (int i = 0; i < n; ++i)
//         prefix[j][i + 1] = prefix[j][i] + grid[i][j];
// 
//     for (int j = 1; j < n; ++j) {
//       long[] currPick = new long[n + 1];
//       long[] currSkip = new long[n + 1];
//       // Consider all possible combinations of the number of current and
//       // previous selected elements.
//       for (int curr = 0; curr <= n; ++curr)
//         for (int prev = 0; prev <= n; ++prev)
//           if (curr > prev) {
//             // 1. The current bottom is deeper than the previous bottom.
//             // Get the score of grid[prev..curr)[j - 1] for pick and skip.
//             final long score = prefix[j - 1][curr] - prefix[j - 1][prev];
//             currPick[curr] = Math.max(currPick[curr], prevSkip[prev] + score);
//             currSkip[curr] = Math.max(currSkip[curr], prevSkip[prev] + score);
//           } else {
//             // 2. The previous bottom is deeper than the current bottom.
//             // Get the score of grid[curr..prev)[j] for pick only.
//             final long score = prefix[j][prev] - prefix[j][curr];
//             currPick[curr] = Math.max(currPick[curr], prevPick[prev] + score);
//             currSkip[curr] = Math.max(currSkip[curr], prevPick[prev]);
//           }
//       prevPick = currPick;
//       prevSkip = currSkip;
//     }
// 
//     return Arrays.stream(prevPick).max().getAsLong();
//   }
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n × m)

Space

O(n × m)

Approach Breakdown

RECURSIVE

O(2ⁿ) time

O(n) space

Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.

DYNAMIC PROGRAMMING

O(n × m) time

O(n × m) space

Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.

Shortcut: Count your DP state dimensions → that’s your time. Can you drop one? That’s your space optimization.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.