Maximum Difference Score in a Grid
MedPrompt
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.
Constraints:
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 1051 <= grid[i][j] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
The problem asks for the maximum score from a sequence of moves. A key observation is that the total score of a path from a starting cell (r0, c0) to an ending cell (rk, ck) is a telescoping sum that simplifies to grid[rk][ck] - grid[r0][c0]. Therefore, the problem reduces to finding the maximum difference grid[r2][c2] - grid[r1][c1] such that a path can exist from (r1, c1) to (r2, c2). A path exists if r2 >= r1, c2 >= c1, and (r1, c1) != (r2, c2).
A brute-force approach directly implements this simplified problem. It involves checking every possible pair of start and end cells in the grid that satisfy the movement constraints, calculating their difference, and keeping track of the maximum difference found.
Algorithm
- Initialize
max_scoreto a very small number (e.g.,Integer.MIN_VALUE). - Use four nested loops to iterate through all possible pairs of start cells
(r1, c1)and end cells(r2, c2). - The outer two loops iterate through
r1from0tom-1andc1from0ton-1. - The inner two loops iterate through
r2fromr1tom-1andc2fromc1ton-1. - Inside the innermost loop, check if the start and end cells are the same (
r1 == r2andc1 == c2). If they are, skip this pair as at least one move is required. - If the cells are different, calculate the score:
score = grid[r2][c2] - grid[r1][c1]. - Update
max_score = max(max_score, score). - After all pairs have been checked, return
max_score.
Walkthrough
This method iterates through every possible start cell (r1, c1) and every possible end cell (r2, c2). For each pair, it first validates if a move from (r1, c1) to (r2, c2) is legitimate. According to the problem, we can move to any cell to the bottom or right, which means r2 >= r1 and c2 >= c1. We also need to make at least one move, so the start and end cells cannot be the same. If these conditions are met, we calculate the score and update our maximum score if the current score is higher.
import java.util.List; class Solution { public int maxScore(List<List<Integer>> grid) { int m = grid.size(); int n = grid.get(0).size(); int maxScore = Integer.MIN_VALUE; for (int r1 = 0; r1 < m; r1++) { for (int c1 = 0; c1 < n; c1++) { for (int r2 = r1; r2 < m; r2++) { for (int c2 = c1; c2 < n; c2++) { if (r1 == r2 && c1 == c2) { continue; } int score = grid.get(r2).get(c2) - grid.get(r1).get(c1); if (score > maxScore) { maxScore = score; } } } } } return maxScore; }}Complexity
Time
O(m² * n²), where `m` is the number of rows and `n` is the number of columns. This is due to four nested loops iterating over the grid dimensions.
Space
O(1) extra space.
Trade-offs
Pros
Simple to understand and implement.
Correctly solves the problem for small grids.
Cons
Extremely inefficient and will result in a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
Solutions
Solution
class Solution {public int maxScore(List<List<Integer>> grid) { int m = grid.size(), n = grid.get(0).size(); final int inf = 1 << 30; int ans = -inf; int[][] f = new int[m][n]; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int mi = inf; if (i > 0) { mi = Math.min(mi, f[i - 1][j]); } if (j > 0) { mi = Math.min(mi, f[i][j - 1]); } ans = Math.max(ans, grid.get(i).get(j) - mi); f[i][j] = Math.min(grid.get(i).get(j), mi); } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.