Scale Engineer

Maximum Score From Grid Operations

Hard
#2864Time: O(n^2 * (n+1)^n). There are `(n+1)^n` configurations. For each, calculating the score takes `O(n^2)`. This is too slow for the given constraints.Space: O(n) for the recursion stack depth and the `choices` array.1 company
Patterns
Dynamic ProgrammingPrefix Sum
Data structures
ArrayMatrix
Companies
Hudson River Trading

Prompt

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 <= 100
  • n == grid[i].length
  • 0 <= grid[i][j] <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

This approach explores every possible combination of operations. For each of the n columns, we can choose to color it black down to any row i (from 0 to n-1), or not color it at all. This gives n+1 choices for each column. A recursive function can be defined to try all these choices and find the one that yields the maximum score.

Algorithm

  • Define a recursive function, say solve(col, choices), where col is the current column index and choices is an array storing the chosen cutoff row for each column processed so far.
  • The base case for the recursion is when col == n. At this point, a choice has been made for every column. Calculate the total score for this configuration.
  • To calculate the score, iterate through the grid. A cell (r, c) is black if r <= choices[c]. A white cell (r, c) contributes its value grid[r][c] to the score if it has a horizontally adjacent black cell.
  • In the recursive step, for the current col, iterate through all n+1 possible choices for the cutoff row (from -1 to n-1, where -1 signifies no operation on the column). For each choice, make a recursive call solve(col + 1, choices).
  • Maintain a global variable to keep track of the maximum score found across all configurations.

Walkthrough

The core idea is to use recursion with backtracking to explore the entire search space of possible operations. We define a function that makes a decision for one column at a time.

For each column, we have n+1 options: either don't perform an operation (which we can represent with a cutoff row of -1) or perform an operation on cell (i, j) for i from 0 to n-1. This means for each column j, the number of black cells from the top can be anything from 0 to n.

Our recursive function solve(col, choices) will try each of these n+1 options for col, and then recursively call itself for the next column col + 1. When col reaches n, we have a complete configuration defined by the choices array. We then compute the score for this configuration and update our maximum score if needed.

class Solution {    long maxScore = 0;    int n;    int[][] grid;     public long maximumScore(int[][] grid) {        this.n = grid.length;        this.grid = grid;        // choices[j] = last black row index in column j        int[] choices = new int[n];         solve(0, choices);        return maxScore;    }     private void solve(int col, int[] choices) {        if (col == n) {            maxScore = Math.max(maxScore, calculateScore(choices));            return;        }         // Try all n+1 possibilities for the current column's operation        // i = -1 means no operation (0 black cells)        // i = 0..n-1 means operation on (i, col)        for (int i = -1; i < n; i++) {            choices[col] = i;            solve(col + 1, choices);        }    }     private long calculateScore(int[] choices) {        long score = 0;        for (int r = 0; r < n; r++) {            for (int c = 0; c < n; c++) {                // Check if cell (r, c) is white                if (r > choices[c]) {                    boolean hasBlackNeighbor = false;                    // Check left neighbor                    if (c > 0 && r <= choices[c - 1]) {                        hasBlackNeighbor = true;                    }                    // Check right neighbor                    if (!hasBlackNeighbor && c < n - 1 && r <= choices[c + 1]) {                        hasBlackNeighbor = true;                    }                    if (hasBlackNeighbor) {                        score += grid[r][c];                    }                }            }        }        return score;    }}

Complexity

Time

O(n^2 * (n+1)^n). There are `(n+1)^n` configurations. For each, calculating the score takes `O(n^2)`. This is too slow for the given constraints.

Space

O(n) for the recursion stack depth and the `choices` array.

Trade-offs

Pros

  • Conceptually simple and easy to understand.

  • A direct translation of the problem statement into a search algorithm.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Only feasible for very small values of n (e.g., n < 5).

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem