Maximum Score From Grid Operations - Solution & Explanation
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 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 <= 100n == grid[i].length0 <= grid[i][j] <= 109
Approach Overview
Problem Overview: You are given a matrix where grid operations allow selecting cells column by column to maximize a total score. The challenge is determining the optimal row boundary for each column so the accumulated values produce the highest score across the grid.
Approach 1: Brute Force Enumeration (Exponential Time, O(n^m) time, O(1) space)
The naive idea is to try every possible configuration of column operations. For each column, you choose a row cutoff and evaluate the resulting score contribution from the grid. This means iterating through every possible combination of row boundaries across all columns and recomputing the score by scanning the matrix. While straightforward, the number of possibilities grows exponentially with the number of columns, making it impractical for larger grids. This approach mainly helps understand the decision space before introducing optimization.
Approach 2: Dynamic Programming with Prefix Sums (O(n^2) time, O(n^2) space)
A more practical solution uses prefix sums to quickly compute column segment sums and dynamic programming to track the best score as you process columns from left to right. Precompute prefix sums for each column so any vertical segment can be evaluated in constant time. Define a DP state representing the maximum score when the previous column ended at a specific row boundary. When processing the next column, iterate through possible row cutoffs and transition between states by combining the previous score with the new column's contribution. This removes repeated recomputation and collapses the exponential search space into a manageable quadratic DP.
The key insight is that column operations are independent except for the boundary chosen in the previous column. Once you cache results in DP states and compute sums using prefix arrays, each transition becomes constant time. This technique is common in grid optimization problems involving matrix traversal and cumulative scoring.
Recommended for interviews: The dynamic programming approach with prefix sums is the expected solution. Brute force demonstrates you understand the decision space and scoring mechanics, but interviewers look for the DP transition that eliminates repeated calculations and achieves quadratic complexity.
Approach 1: Brute Force Approach
The brute force approach involves evaluating every possible combination of operations and calculating the resulting score for each. This method is computationally heavy and impractical for large grids due to the high number of combinations possible.
This code is a placeholder for the brute force approach. In practice, this method is inefficient and serves only as a conceptual foundation.
Complexity
Time Complexity: O((n^2)^n), Space Complexity: O(n^2)
Approach 2: Optimized Greedy Approach
This approach utilizes a greedy strategy to maximize scores more efficiently by dynamically selecting the best columns to wipe at each potential stage, computing cumulative contributions to the score, aiming to reduce complexity substantially compared to brute force methods.
This code ranks elements from each column and adds each element's contribution to the score if it's smaller than the element above, ensuring all potential scores are considered.
Complexity
Time Complexity: O(n^2 log(n)), Space Complexity: O(n)
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O((n^2)^n), Space Complexity: O(n^2) |
| Optimized Greedy Approach | Time Complexity: O(n^2 log(n)), Space Complexity: O(n) |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^m) | O(1) | Understanding the full search space or validating small test cases |
| Dynamic Programming + Prefix Sum | O(n^2) | O(n^2) | General case and interview solution where repeated column computations must be optimized |
Video Solution
Maximum Score From Grid Operations | Super Detailed For Beginners | Leetcode 3225 | codestorywithMIK • codestorywithMIK • 5,921 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Score From Grid Operations easy or hard?
Maximum Score From Grid Operations Python/Java solution
How to solve Maximum Score From Grid Operations in O(n^2)?
What is the best approach for Maximum Score From Grid Operations?
Is Maximum Score From Grid Operations asked at Google/Amazon/Meta?
What data structure is used in Maximum Score From Grid Operations?
What is the time complexity of Maximum Score From Grid Operations?
Ready to solve this problem?
Practice Maximum Score From Grid Operations with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor