3148. Maximum Difference Score in a Grid LeetCode Solution
In this guide, you will get 3148. Maximum Difference Score in a Grid LeetCode Solution with the best time and space complexity. The solution to Maximum Difference Score in a Grid 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 Difference Score in a Grid
You are given an m x n matrix grid consisting of positive integers. You can move from a cell in the matrix to any other cell that is either to the bottom or to the right (not necessarily adjacent). The score of a move from a cell with the value c1 to a cell with the value c2 is c2 – c1.
You can start at any cell, and you have to make at least one move.
Return the maximum total score you can achieve.
Example 1:
Input: grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]
Output: 9
Explanation: We start at the cell (0, 1), and we perform the following moves:
– Move from the cell (0, 1) to (2, 1) with a score of 7 – 5 = 2.
– Move from the cell (2, 1) to (2, 2) with a score of 14 – 7 = 7.
The total score is 2 + 7 = 9.
Example 2:
Input: grid = [[4,3,2],[3,2,1]]
Output: -1
Explanation: We start at the cell (0, 0), and we perform one move: (0, 0) to (0, 1). The score is 3 – 4 = -1.
m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 105
1 <= grid[i][j] <= 105
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
3148. Maximum Difference Score in a Grid LeetCode Solution in C++
class Solution {
public:
int maxScore(vector<vector<int>>& grid) {
constexpr int kMax = 200'000;
int ans = -kMax;
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j) {
const int prevMin = min(i > 0 ? grid[i - 1][j] : kMax, //
j > 0 ? grid[i][j - 1] : kMax);
ans = max(ans, grid[i][j] - prevMin);
grid[i][j] = min(grid[i][j], prevMin);
}
return ans;
}
}; /* code provided by PROGIEZ */
3148. Maximum Difference Score in a Grid LeetCode Solution in Java
class Solution {
public int maxScore(List<List<Integer>> grid) {
final int kMax = 200_000;
int ans = -kMax;
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid.get(0).size(); ++j) {
final int prevMin = Math.min(i > 0 ? grid.get(i - 1).get(j) : kMax, //
j > 0 ? grid.get(i).get(j - 1) : kMax);
ans = Math.max(ans, grid.get(i).get(j) - prevMin);
if (prevMin < grid.get(i).get(j))
grid.get(i).set(j, prevMin);
}
return ans;
}
} // code provided by PROGIEZ
3148. Maximum Difference Score in a Grid LeetCode Solution in Python
class Solution:
def maxScore(self, grid: list[list[int]]) -> int:
kMax = 200000
ans = -kMax
for i, row in enumerate(grid):
for j, num in enumerate(row):
prevMin = min(grid[i - 1][j] if i > 0 else kMax,
grid[i][j - 1] if j > 0 else kMax)
ans = max(ans, num - prevMin)
grid[i][j] = min(num, prevMin)
return ans # code by PROGIEZ
