Maximum Score From Grid Operations - Practice Coding Problems

Maximum Score From Grid Operations - Problem

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.

Input & Output

Example 1 — Basic 3x3 Grid

$ Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

› Output: 13

💡 Note: Color columns with heights [2,1,0]. White cells (2,0)=7 and (1,1)=5 are adjacent to black cells, giving score 7+5=12. Actually optimal is different configuration giving 13.

Example 2 — Small 2x2 Grid

$ Input: grid = [[1,2],[3,4]]

› Output: 4

💡 Note: With heights [1,0], cell (1,1)=4 is white and adjacent to black cell at (0,1), giving score 4.

Example 3 — All Same Values

$ Input: grid = [[1,1],[1,1]]

› Output: 1

💡 Note: Best configuration gives score 1 from one white cell adjacent to black.

Constraints

1 ≤ n ≤ 10²
1 ≤ grid[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Grid

3x3 grid with values, all cells initially white

Paint Columns

Paint columns from top down to different heights

Calculate Score

Score from white cells adjacent to black cells

Key Takeaway

🎯 Key Insight: Optimal column heights create maximum scoring boundaries between black and white cells

Asked in

G Google 25 M Microsoft 18

The key insight is that score comes from white cells adjacent to black boundaries created by column painting operations. Best approach uses dynamic programming with memoization to efficiently explore all column height combinations. Time: O(n³), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Memoization	O(n³)	O(n²)	Use memoization to avoid recalculating the same column height combinations
Brute Force - Try All Combinations	O(n^n)	O(n)	Try every possible combination of column heights and calculate scores

Dynamic Programming with Memoization — Algorithm Steps

Use memoization table for (column, prev_height) states
For each column, try all heights and memoize results
Calculate score incrementally for efficiency

Visualization

Tap to expand

Step-by-Step Walkthrough

State Definition

Define state as (column, previous_height)

Memoization

Cache results to avoid recalculation

Optimal Path

Find path with maximum score

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int memo[1000][1000];
static int memoInit[1000][1000];

int calculateTotalScore(int* heights, int** grid, int n) {
    int score = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i >= heights[j]) {
                int hasAdjacentBlack = 0;
                if (j > 0 && i < heights[j-1]) {
                    hasAdjacentBlack = 1;
                }
                if (j < n-1 && i < heights[j+1]) {
                    hasAdjacentBlack = 1;
                }
                if (hasAdjacentBlack) {
                    score += grid[i][j];
                }
            }
        }
    }
    return score;
}

int dp(int col, int prevHeight, int** grid, int n) {
    if (col == n) {
        return 0;
    }
    
    if (memoInit[col][prevHeight]) {
        return memo[col][prevHeight];
    }
    
    int maxScore = 0;
    for (int height = 0; height <= n; height++) {
        int score = 0;
        for (int i = 0; i < n; i++) {
            if (i >= height) {
                int hasAdjacentBlack = 0;
                if (col > 0 && i < prevHeight) {
                    hasAdjacentBlack = 1;
                }
                if (hasAdjacentBlack) {
                    score += grid[i][col];
                }
            }
        }
        
        int totalScore = score + dp(col + 1, height, grid, n);
        if (totalScore > maxScore) {
            maxScore = totalScore;
        }
    }
    
    memo[col][prevHeight] = maxScore;
    memoInit[col][prevHeight] = 1;
    return maxScore;
}

int solution(int** grid, int n) {
    int best = 0;
    
    for (int firstHeight = 0; firstHeight <= n; firstHeight++) {
        memset(memoInit, 0, sizeof(memoInit));
        int* heights = (int*)calloc(n, sizeof(int));
        heights[0] = firstHeight;
        int score = calculateTotalScore(heights, grid, n);
        if (score > best) {
            best = score;
        }
        free(heights);
    }
    
    return best;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int n = 3;
    int** grid = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        grid[i] = (int*)malloc(n * sizeof(int));
    }
    
    sscanf(line, "[[%d,%d,%d],[%d,%d,%d],[%d,%d,%d]]", 
           &grid[0][0], &grid[0][1], &grid[0][2],
           &grid[1][0], &grid[1][1], &grid[1][2],
           &grid[2][0], &grid[2][1], &grid[2][2]);
    
    printf("%d\n", solution(grid, n));
    
    for (int i = 0; i < n; i++) {
        free(grid[i]);
    }
    free(grid);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

n columns × n heights × n operations per state

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores n×n states

⚠ Quadratic Space

25.4K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler