Maximum Difference Score in a Grid — Problem & Solution
Maximum Difference Score in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Difference Score in a Grid is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an m x n matrix grid of positive integers. From a cell you may move to any cell strictly below it in the same column, or strictly to its right in the same row — not necessarily adjacent. A move from a cell holding c1 to a cell holding c2 scores c2 - c1.
You may start at any cell and must make at least one move. Return the maximum total score you can achieve (it may be negative).
Example 1
Input: grid = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]
Output: 9
Explanation: Start at (0,1) holding 5, move to (2,1) holding 7 (+2), then to (2,2) holding 14 (+7): total 9.
Example 2
Input: grid = [[4,3,2],[3,2,1]]
Output: -1
Explanation: Every move goes to a smaller value; the best single move is from 4 to 3 (or 3 to 2, …), scoring -1.
Example 3
Input: grid = [[1,9],[9,9]]
Output: 8
Explanation: Start at the 1 and move to any 9.
Constraints
m == grid.lengthn == grid[i].length2 <= m, n <= 10004 <= m * n <= 10^51 <= grid[i][j] <= 10^5
Hints for Maximum Difference Score in a Grid
Hint 1
Add up the scores along a path: the middle values cancel. A path's score is just (last value) − (first value).
Hint 2
So you only need the best pair of cells where the end is below and/or right of the start (and not the same cell).
Hint 3
For each cell, keep the minimum over the rectangle above-left of it:
mn[i][j] = min(grid[i][j], mn[i-1][j], mn[i][j-1]). The best path ending at(i, j)scoresgrid[i][j] − min(mn[i-1][j], mn[i][j-1]).
How to solve Maximum Difference Score in a Grid
The scores telescope: moving a → b → c scores (b − a) + (c − b) = c − a. So the answer is the largest grid[end] − grid[start] over pairs where end is reachable from start — any cell weakly below and weakly right, other than the start itself.
Approach
- Let
mn[i][j]be the smallest value in the rectangle of rows0..iand columns0..j. - For each cell in row-major order, let
prev = min(mn[i-1][j], mn[i][j-1])(ignoring missing neighbours). If some neighbour exists, update the answer withgrid[i][j] − prev. - Set
mn[i][j] = min(prev, grid[i][j]). - Return the best value found.
Why it works
The cells that can reach (i, j) with at least one move are exactly the cells of its above-left rectangle other than itself, which is the union of the rectangles ending at (i-1, j) and (i, j-1); their minimum is prev. Any such start reaches (i, j) by one vertical and one horizontal move (or a single move), and the telescoping sum makes the route irrelevant.
Complexity
- Time —
O(m · n) - Space —
O(m · n), or O(n) with one row
Pitfalls
- At least one move is required, so the start cannot equal the end — do not include
grid[i][j]itself inprev. - The answer can be negative; initialise the best with negative infinity, not 0.
- Moves go right or down only — a cell up-right of the start is not reachable.
Reference solution
Python
from typing import List
def maxScore(grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
INF = float('inf')
mn = [[INF] * n for _ in range(m)]
best = -INF
for i in range(m):
for j in range(n):
prev = INF
if i > 0:
prev = mn[i - 1][j]
if j > 0 and mn[i][j - 1] < prev:
prev = mn[i][j - 1]
if prev < INF and grid[i][j] - prev > best:
best = grid[i][j] - prev
mn[i][j] = min(prev, grid[i][j])
return bestJava
public static int maxScore(int[][] grid) {
int m = grid.length, n = grid[0].length;
final int INF = Integer.MAX_VALUE;
int[][] mn = new int[m][n];
int best = Integer.MIN_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int prev = INF;
if (i > 0) prev = mn[i - 1][j];
if (j > 0) prev = Math.min(prev, mn[i][j - 1]);
if (prev < INF) best = Math.max(best, grid[i][j] - prev);
mn[i][j] = Math.min(prev, grid[i][j]);
}
}
return best;
}C++
int maxScore(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
const int INF = INT_MAX;
vector<vector<int>> mn(m, vector<int>(n, INF));
int best = INT_MIN;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int prev = INF;
if (i > 0) prev = mn[i - 1][j];
if (j > 0) prev = min(prev, mn[i][j - 1]);
if (prev < INF) best = max(best, grid[i][j] - prev);
mn[i][j] = min(prev, grid[i][j]);
}
}
return best;
}JavaScript
var maxScore = function(grid) {
var m = grid.length, n = grid[0].length;
var INF = Infinity, best = -Infinity;
var mn = [];
for (var i = 0; i < m; i++) mn.push(new Array(n).fill(INF));
for (var i = 0; i < m; i++) {
for (var j = 0; j < n; j++) {
var prev = INF;
if (i > 0) prev = mn[i - 1][j];
if (j > 0 && mn[i][j - 1] < prev) prev = mn[i][j - 1];
if (prev < INF && grid[i][j] - prev > best) best = grid[i][j] - prev;
mn[i][j] = Math.min(prev, grid[i][j]);
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming