3225. Maximum Score From Grid Operations LeetCode Solution
In this guide, you will get 3225. Maximum Score From Grid Operations LeetCode Solution with the best time and space complexity. The solution to Maximum Score From Grid Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Score From Grid Operations
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.
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.
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.
1 <= n == grid.length <= 100
n == grid[i].length
0 <= grid[i][j] <= 109
Complexity Analysis
Time Complexity: O(n^3)
Space Complexity: O(n^2)
3225. Maximum Score From Grid Operations LeetCode Solution in C++
class Solution {
public:
long long maximumScore(vector<vector<int>>& grid) {
const int n = grid.size();
// prefix[j][i] := the sum of the first i elements in the j-th column
vector<vector<long>> prefix(n, vector<long>(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)
vector<long> prevPick(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)
vector<long> prevSkip(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) {
vector<long> currPick(n + 1);
vector<long> currSkip(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.
const long 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.
const long score = prefix[j][prev] - prefix[j][curr];
currPick[curr] = max(currPick[curr], prevPick[prev] + score);
currSkip[curr] = max(currSkip[curr], prevPick[prev]);
}
prevPick = std::move(currPick);
prevSkip = std::move(currSkip);
}
return ranges::max(prevPick);
}
}; /* code provided by PROGIEZ */
3225. Maximum Score From Grid Operations LeetCode Solution in Java
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();
}
} // code provided by PROGIEZ
3225. Maximum Score From Grid Operations LeetCode Solution in Python
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) # code by PROGIEZ
