We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Score From Grid Operations

Number: 3470

Difficulty: Hard

Paid? No

Companies: Hudson River Trading

Problem Description

You are given an n x n grid of non‐negative integers. Initially every cell is white. In one operation you may pick any cell (i, j) and “paint” the jth column from the top down to row i black. After doing an arbitrary number of these operations the score is computed as the sum of all white cells that have at least one horizontally adjacent (left or right) cell that is black. The goal is to choose operations (i.e. choose for each column a “cut‐off” row up to which that column becomes black) so that the overall score is maximized.

Key Insights

  • Each column’s operation is equivalent to choosing a threshold (or “cut”) such that rows above (and including) the chosen cell become black and the rest remain white.
  • After all operations, every column j is fully described by its “transition” row r[j] where row i is white if and only if i ≥ r[j]. (For a column never painted, r[j]=0 so that the entire column is white.)
  • A white cell in row i, column j contributes to the score only if at least one of its horizontal neighbors (column j‑1 or j+1) is still black at row i (i.e. if i < r[neighbor]).
  • Notice that although each column’s choice is “local” in the sense that it just sets its own white–black boundary, the scoring function couples adjacent columns.
  • The optimal solution requires balancing: a column may sacrifice some of its own potential white cell values (by choosing a low r[j] and hence having few white cells) so as to help count high‐value white cells in its neighbour.
  • The dependencies among adjacent columns naturally lead to a dynamic programming formulation where the decision for column j depends on the choices for columns j–1 (and even j–2 when computing the score contribution for column j–1).

Space and Time Complexity

Time Complexity: O(n * (n+1)^3)
  (n columns; each threshold is in the range [0,n] and a DP state may depend on two neighbors.)
Space Complexity: O(n * (n+1)^2)
  (space used for the DP states)

Solution

We solve the problem by reinterpreting an “operation” as choosing, for each column j, a transition row r[j] (with 0 ≤ r[j] ≤ n). For column j the cells in rows 0..r[j]-1 become black and rows r[j]..n-1 remain white. Then, a white cell (i, j) contributes its grid value if and only if one of its horizontal adjacent cells is black at row i. In terms of r-values, this means that if j is not a boundary column, white cell (i,j) contributes when i is at least r[j] and strictly less than the r-value in at least one neighbor (i.e. i < max(r[j-1], r[j+1])). For the first and last columns the condition uses the single available neighbor.

Since the contribution from a column’s white cells depends on the r-value chosen for that column as well as on the neighbors’ r-values, we set up a dynamic programming (DP) solution. The idea is to process the columns left to right while “remembering” the r-value chosen for the previous column (and even the one before that) so that when the next column’s r-value is chosen we can “finalize” the contribution from the previous column.

Before starting the DP we precompute the prefix sums for every column to quickly compute the sum of grid values between any two row indices. The DP recurrence is defined over states that capture the thresholds chosen for the last two columns. For a state corresponding to having fixed r[j-2] and r[j-1], when deciding r[j] we can compute the contribution from column j-1. In the interior (non-boundary) case, the white cells in column j-1 that are “counted” come from the rows in [r[j-1], max(r[j-2], r[j])-1] (if that interval is valid). Similar ideas are applied at the boundaries (for the very first and last columns).

Note that one “gotcha” is to ensure that you add the grid values only once even if both neighbors are black. Also, be cautious with boundary conditions (first and last columns have only one neighbor).

The final answer will be the maximum total score over all valid choices of r-values.

Code Solutions

# Python solution with detailed line-by-line comments

def maximumScore(grid):
    n = len(grid)
    # Precompute prefix sums for each column so that col_prefix[j][i] gives sum of grid[0..i] in column j.
    col_prefix = [[0]*(n+1) for _ in range(n)]
    for j in range(n):
        for i in range(n):
            col_prefix[j][i+1] = col_prefix[j][i] + grid[i][j]
    
    # Helper function to compute the sum in column j for rows in [low, high] (inclusive low, exclusive high)
    def col_sum(j, low, high):
        # Ensure bounds are valid: low from [0, n] and high from [0, n+1]
        return col_prefix[j][high] - col_prefix[j][low]
    
    # dp[j][prev][prev2] represents the maximum score for processing columns up to index j-1,
    # where the last two columns’ cut rows are prev2 (for j-2) and prev (for j-1).
    # The DP state is defined for j >= 2.
    # Initialize dp as a 3D dictionary: dp[j][prev][prev2].
    dp = {}
    
    # Initialization for column 0: we have not “finalized” any contribution yet, so we store
    # state for j==1 with only one column decided. For column 0, r can be any value in [0, n].
    dp[1] = {}
    for r0 in range(n+1):
        # Use a dummy value -1 for the non-existent previous column.
        dp[1][(r0, -1)] = 0
    
    # Process columns 1 to n-1.
    for j in range(1, n):
        dp[j+1] = {}
        for (prev, prev2), score in dp[j].items():
            # Iterate over possible r[j] for the current column j.
            for curr in range(n+1):
                new_score = score
                # Finalize contribution from column j-1 (with threshold = prev)
                # Determine the effective r from its left neighbor (prev2) and right neighbor (curr)
                # For non-boundary columns, the white cell in column j-1 (if any) from row 'prev' to row (max(prev2, curr)-1)
                # will contribute to the score.
                if prev2 == -1:
                    # j-1 is the first column, so it has only right neighbor curr.
                    effective = curr
                else:
                    effective = max(prev2, curr)
                if prev < effective:
                    # Add the sum of white cells in column j-1 from row prev to effective-1.
                    new_score += col_sum(j-1, prev, effective)
                # Update dp state: now the last two columns become (curr, prev)
                state = (curr, prev)
                if state not in dp[j+1] or dp[j+1][state] < new_score:
                    dp[j+1][state] = new_score
    
    # Finalize contribution for the last column (column n-1)
    best = 0
    for (prev, prev2), score in dp[n].items():
        # For the last column, only the left neighbor exists (prev2),
        # so the effective value is prev2 if defined, otherwise no extra contribution.
        if prev2 == -1:
            effective = 0  # no left neighbor; boundary case, no white cells get a counted neighbor
        else:
            effective = prev2
        add = 0
        if prev < effective:
            add = col_sum(n-1, prev, effective)
        best = max(best, score + add)
    
    return best

# Example test cases:
if __name__ == "__main__":
    grid1 = [
        [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]
    ]
    print(maximumScore(grid1))  # Expected output: 11

    grid2 = [
        [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]
    ]
    print(maximumScore(grid2))  # Expected output: 94
← Back to All Questions