Maximum Difference Score in a Grid solution and explanation
5 more videos on this problem
3148. Maximum Difference Score in a Grid | Top Down + Bottom Up | Weekly Leetcode 397codingMohan · 40:26 · 1K views
3148. Maximum Difference Score in a Grid (Leetcode Medium)Programming Live with Larry · 14:15 · 1K views
Leetcode 3148 Maximum Difference Score in a GridSandip Jana · 9:49 · 953 views
Solving Leetcode Weekly Contest 397. | LC 3148. Maximum Difference Score in a GridLet's Solve · 16:32 · 360 views
Maximum Difference Score in a Grid (LeetCode Q3148)kode · 12:35 · 193 views
Leetcode 3148. Maximum Difference Score in a Grid (2d prefix sum)LetsCode · 6:26 · 122 views
The problem
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
Approach overview
Problem Overview: You are given an m x n grid. From any cell, you can move to another cell that is strictly to the right or strictly below through a sequence of moves. The score of a move is the difference between the destination value and the starting value. The goal is to compute the maximum possible score between two valid cells.
Approach 1: Dynamic Programming with Prefix Minimum (O(m*n) time, O(1) extra space)
The key observation: for every cell (i, j), the best score ending at that cell depends on the smallest value reachable from any cell above or to the left. While scanning the grid row by row, maintain the minimum value seen so far from the top or left directions. For each cell, compute grid[i][j] - minPrev where minPrev is the minimum value from reachable previous cells. Update the answer if this difference is larger. Then update the running minimum with min(minPrev, grid[i][j]). This effectively turns the problem into tracking the best earlier candidate while iterating through the matrix. Time complexity is O(m*n) and space complexity is O(1) beyond the grid. This approach fits naturally with dynamic programming patterns on a matrix.
Approach 2: Sorting with Binary Search on Score (O(m*n log V) time, O(m*n) space)
Another way to think about the problem is to binary search the maximum achievable score difference. Define a candidate difference d. Then check whether there exists a pair of cells (r1, c1) and (r2, c2) such that r2 ≥ r1, c2 ≥ c1, and grid[r2][c2] - grid[r1][c1] ≥ d. During the check, maintain a prefix minimum matrix that tracks the smallest value reachable before each position. If any cell satisfies the condition against that prefix minimum, the difference is feasible. Binary search over the value range of the grid to find the largest valid difference. Each feasibility check scans the grid once, giving O(m*n) per iteration and O(log V) iterations where V is the value range. This method is useful when framing the problem as a decision problem combined with value ordering techniques on arrays.
Recommended for interviews: The dynamic programming scan is the expected solution. It shows you recognize the monotonic movement constraint and convert the task into maintaining a prefix minimum. The binary search formulation demonstrates deeper algorithmic thinking, but the O(m*n) DP solution is simpler, faster, and typically what interviewers look for.
Approach 1: Dynamic Programming
This approach involves using dynamic programming to store the maximum score possible for each cell when considering only moves to the right or downward. The idea is to start from the top-left and compute the best possible score dynamically going right and down.
def max_difference_score(grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
max_diff = -1
for i in range(m):
for j in range(n):
dp[i][j] = 0
for k in range(i + 1, m):
if grid[k][j] > grid[i][j]:
diff = grid[k][j] - grid[i][j]
dp[i][j] = max(dp[i][j], diff)
for k in range(j + 1, n):
if grid[i][k] > grid[i][j]:
diff = grid[i][k] - grid[i][j]
dp[i][j] = max(dp[i][j], diff)
max_diff = max(max_diff, dp[i][j])
return max_diff
grid = [
[9, 5, 7, 3],
[8, 9, 6, 1],
[6, 7, 14, 3],
[2, 5, 3, 1]
]
print("Maximum Difference Score:", max_difference_score(grid))import java.util.*;
public class MaxDifferenceScore {
public static int maxDifferenceScore(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
int maxDiff = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = 0;
for (int k = i + 1; k < m; k++) {
if (grid[k][j] > grid[i][j]) {
int diff = grid[k][j] - grid[i][j];
dp[i][j] = Math.max(dp[i][j], diff);
}
}
for (int k = j + 1; k < n; k++) {
if (grid[i][k] > grid[i][j]) {
int diff = grid[i][k] - grid[i][j];
dp[i][j] = Math.max(dp[i][j], diff);
}
}
maxDiff = Math.max(maxDiff, dp[i][j]);
}
}
return maxDiff;
}
public static void main(String[] args) {
int[][] grid = {
{9, 5, 7, 3},
{8, 9, 6, 1},
{6, 7, 14, 3},
{2, 5, 3, 1}
};
System.out.println("Maximum Difference Score: " + maxDifferenceScore(grid));
}
}#include <iostream>
#include <vector>
using namespace std;
int maxDifferenceScore(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int maxDiff = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = 0;
for (int k = i + 1; k < m; k++) {
if (grid[k][j] > grid[i][j]) {
int diff = grid[k][j] - grid[i][j];
dp[i][j] = max(dp[i][j], diff);
}
}
for (int k = j + 1; k < n; k++) {
if (grid[i][k] > grid[i][j]) {
int diff = grid[i][k] - grid[i][j];
dp[i][j] = max(dp[i][j], diff);
}
}
maxDiff = max(maxDiff, dp[i][j]);
}
}
return maxDiff;
}
int main() {
vector<vector<int>> grid = {{9, 5, 7, 3}, {8, 9, 6, 1}, {6, 7, 14, 3}, {2, 5, 3, 1}};
cout << "Maximum Difference Score: " << maxDifferenceScore(grid) << endl;
return 0;
}function maxDifferenceScore(grid) {
const m = grid.length;
const n = grid[0].length;
const dp = Array.from({ length: m }, () => new Array(n).fill(0));
let maxDiff = -1;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
dp[i][j] = 0;
for (let k = i + 1; k < m; k++) {
if (grid[k][j] > grid[i][j]) {
const diff = grid[k][j] - grid[i][j];
dp[i][j] = Math.max(dp[i][j], diff);
}
}
for (let k = j + 1; k < n; k++) {
if (grid[i][k] > grid[i][j]) {
const diff = grid[i][k] - grid[i][j];
dp[i][j] = Math.max(dp[i][j], diff);
}
}
maxDiff = Math.max(maxDiff, dp[i][j]);
}
}
return maxDiff;
}
const grid = [
[9, 5, 7, 3],
[8, 9, 6, 1],
[6, 7, 14, 3],
[2, 5, 3, 1]
];
console.log("Maximum Difference Score:", maxDifferenceScore(grid));#include <stdio.h>
#include <stdlib.h>
int maxDifferenceScore(int** grid, int m, int n) {
int** dp = (int**)malloc(m * sizeof(int*));
for (int i = 0; i < m; i++) {
dp[i] = (int*)malloc(n * sizeof(int));
}
int maxDiff = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = 0;
for (int k = i + 1; k < m; k++) {
if (grid[k][j] > grid[i][j]) {
int diff = grid[k][j] - grid[i][j];
dp[i][j] = diff > dp[i][j] ? diff : dp[i][j];
}
}
for (int k = j + 1; k < n; k++) {
if (grid[i][k] > grid[i][j]) {
int diff = grid[i][k] - grid[i][j];
dp[i][j] = diff > dp[i][j] ? diff : dp[i][j];
}
}
if (dp[i][j] > maxDiff) {
maxDiff = dp[i][j];
}
}
}
for (int i = 0; i < m; i++) {
free(dp[i]);
}
free(dp);
return maxDiff;
}
int main() {
int m = 4, n = 4;
int gridArray[4][4] = {
{9, 5, 7, 3},
{8, 9, 6, 1},
{6, 7, 14, 3},
{2, 5, 3, 1}
};
int* grid[4];
for (int i = 0; i < 4; i++) {
grid[i] = gridArray[i];
}
printf("Maximum Difference Score: %d\n", maxDifferenceScore(grid, 4, 4));
return 0;
}using System;
class Solution {
public int MaxDifferenceScore(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int[,] dp = new int[m, n];
int maxDiff = -1;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i, j] = 0;
for (int k = i + 1; k < m; k++) {
if (grid[k][j] > grid[i][j]) {
int diff = grid[k][j] - grid[i][j];
dp[i, j] = Math.Max(dp[i, j], diff);
}
}
for (int k = j + 1; k < n; k++) {
if (grid[i][k] > grid[i][j]) {
int diff = grid[i][k] - grid[i][j];
dp[i, j] = Math.Max(dp[i, j], diff);
}
}
maxDiff = Math.Max(maxDiff, dp[i, j]);
}
}
return maxDiff;
}
static void Main(string[] args) {
int[][] grid = new int[][] {
new int[] {9, 5, 7, 3},
new int[] {8, 9, 6, 1},
new int[] {6, 7, 14, 3},
new int[] {2, 5, 3, 1}
};
Console.WriteLine("Maximum Difference Score: " + new Solution().MaxDifferenceScore(grid));
}
}This Python implementation uses list comprehensions and loops to build a dynamic programming solution where it calculates the maximum score possible by exploring all valid downward and rightward paths from each cell.
Time Complexity: O(m * n * max(m, n))
Space Complexity: O(m * n)
Approach 2: Sorting with Binary Search
This approach conceptualizes treating each row and column as sorted lists. By sorting, it enables binary search operations to efficiently find the differences that contribute to a maximizing score move.
def max_difference_score(grid):
m, n = len(grid), len(grid[0])
max_diff = -1
for row in grid:
row.sort()
for j in range(n):
col = sorted(grid[i][j] for i in range(m))
for i in range(m):
pos = next((k for k in range(m) if col[k] > grid[i][j]), m)
if pos < m:
max_diff = max(max_diff, col[pos] - grid[i][j])
return max_diff
grid = [
[9, 5, 7, 3],
[8, 9, 6, 1],
[6, 7, 14, 3],
[2, 5, 3, 1]
]
print("Maximum Difference Score:", max_difference_score(grid))import java.util.*;
public class MaxDifferenceScore {
public static int maxDifferenceScore(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int maxDiff = -1;
for (int[] row : grid) {
Arrays.sort(row);
}
for (int j = 0; j < n; j++) {
int[] col = new int[m];
for (int i = 0; i < m; i++) {
col[i] = grid[i][j];
}
Arrays.sort(col);
for (int i = 0; i < m; i++) {
int pos = Arrays.binarySearch(col, grid[i][j]);
if (pos < 0) pos = -pos - 1;
while (pos < m && col[pos] <= grid[i][j]) pos++;
if (pos < m) {
maxDiff = Math.max(maxDiff, col[pos] - grid[i][j]);
}
}
}
return maxDiff;
}
public static void main(String[] args) {
int[][] grid = {
{9, 5, 7, 3},
{8, 9, 6, 1},
{6, 7, 14, 3},
{2, 5, 3, 1}
};
System.out.println("Maximum Difference Score: " + maxDifferenceScore(grid));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxDifferenceScore(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int maxDiff = -1;
for (auto& row : grid) {
sort(row.begin(), row.end());
}
for (int j = 0; j < n; j++) {
vector<int> col(m);
for (int i = 0; i < m; i++) {
col[i] = grid[i][j];
}
sort(col.begin(), col.end());
for (int i = 0; i < m; i++) {
auto it = upper_bound(col.begin(), col.end(), grid[i][j]);
if (it != col.end()) {
maxDiff = max(maxDiff, (*it) - grid[i][j]);
}
}
}
return maxDiff;
}
int main() {
vector<vector<int>> grid = {{9, 5, 7, 3}, {8, 9, 6, 1}, {6, 7, 14, 3}, {2, 5, 3, 1}};
cout << "Maximum Difference Score: " << maxDifferenceScore(grid) << endl;
return 0;
}function maxDifferenceScore(grid) {
const m = grid.length;
const n = grid[0].length;
let maxDiff = -1;
for (let row of grid) {
row.sort((a, b) => a - b);
}
for (let j = 0; j < n; j++) {
let col = [];
for (let i = 0; i < m; i++) {
col.push(grid[i][j]);
}
col.sort((a, b) => a - b);
for (let i = 0; i < m; i++) {
let pos = col.findIndex(x => x > grid[i][j]);
if (pos !== -1) {
maxDiff = Math.max(maxDiff, col[pos] - grid[i][j]);
}
}
}
return maxDiff;
}
const grid = [
[9, 5, 7, 3],
[8, 9, 6, 1],
[6, 7, 14, 3],
[2, 5, 3, 1]
];
console.log("Maximum Difference Score:", maxDifferenceScore(grid));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int findMaxDifference(int a[], int size, int value) {
int start = 0, end = size - 1, mid;
int maxDiff = -1;
while (start <= end) {
mid = (start + end) / 2;
if (a[mid] > value) {
maxDiff = a[mid] - value;
start = mid + 1;
} else {
end = mid - 1;
}
}
return maxDiff;
}
int maxDifferenceScore(int** grid, int m, int n) {
int maxDiff = -1;
for (int i = 0; i < m; i++) {
qsort(grid[i], n, sizeof(int), cmp);
}
for (int j = 0; j < n; j++) {
int* col = (int*)malloc(m * sizeof(int));
for (int i = 0; i < m; i++) {
col[i] = grid[i][j];
}
qsort(col, m, sizeof(int), cmp);
for (int i = 0; i < m; i++) {
int diff = findMaxDifference(col, m, grid[i][j]);
if (diff > maxDiff) {
maxDiff = diff;
}
}
free(col);
}
return maxDiff;
}
int main() {
int m = 4, n = 4;
int gridArray[4][4] = {
{9, 5, 7, 3},
{8, 9, 6, 1},
{6, 7, 14, 3},
{2, 5, 3, 1}
};
int* grid[4];
for (int i = 0; i < 4; i++) {
grid[i] = gridArray[i];
}
printf("Maximum Difference Score: %d\n", maxDifferenceScore(grid, 4, 4));
return 0;
}using System;
using System.Linq;
class Solution {
public int MaxDifferenceScore(int[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int maxDiff = -1;
foreach (var row in grid) {
Array.Sort(row);
}
for (int j = 0; j < n; j++) {
int[] col = Enumerable.Range(0, m).Select(i => grid[i][j]).ToArray();
Array.Sort(col);
for (int i = 0; i < m; i++) {
int pos = Array.BinarySearch(col, grid[i][j]);
if (pos < 0) pos = ~pos;
while (pos < m && col[pos] <= grid[i][j]) pos++;
if (pos < m) {
maxDiff = Math.Max(maxDiff, col[pos] - grid[i][j]);
}
}
}
return maxDiff;
}
static void Main(string[] args) {
int[][] grid = new int[][] {
new int[] {9, 5, 7, 3},
new int[] {8, 9, 6, 1},
new int[] {6, 7, 14, 3},
new int[] {2, 5, 3, 1}
};
Console.WriteLine("Maximum Difference Score: " + new Solution().MaxDifferenceScore(grid));
}
}This Python implementation sorts rows and precomputed column data using sorting and binary search techniques to optimize selection of the minimal greater value.
Time Complexity: O(m * n * log(n))
Space Complexity: O(m * n) due to pre-sorted arrays
Approach 3: Dynamic Programming
According to the problem description, if the values of the cells we pass through are c_1, c_2, cdots, c_k, then our score is c_2 - c_1 + c_3 - c_2 + cdots + c_k - c_{k-1} = c_k - c_1. Therefore, the problem is transformed into: for each cell (i, j) of the matrix, if we take it as the endpoint, what is the minimum value of the starting point.
We can use dynamic programming to solve this problem. We define f[i][j] as the minimum value of the path with (i, j) as the endpoint. Then we can get the state transition equation:
$
f[i][j] = min(f[i-1][j], f[i][j-1], grid[i][j])
So the answer is the maximum value of grid[i][j] - min(f[i-1][j], f[i][j-1]).
The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n$ are the number of rows and columns of the matrix, respectively.
function maxScore(grid: number[][]): number {
const [m, n] = [grid.length, grid[0].length];
const f: number[][] = Array.from({ length: m }, () => Array.from({ length: n }, () => 0));
let ans = -Infinity;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
let mi = Infinity;
if (i) {
mi = Math.min(mi, f[i - 1][j]);
}
if (j) {
mi = Math.min(mi, f[i][j - 1]);
}
ans = Math.max(ans, grid[i][j] - mi);
f[i][j] = Math.min(mi, grid[i][j]);
}
}
return ans;
}func maxScore(grid [][]int) int {
m, n := len(grid), len(grid[0])
f := make([][]int, m)
for i := range f {
f[i] = make([]int, n)
}
const inf int = 1 << 30
ans := -inf
for i, row := range grid {
for j, x := range row {
mi := inf
if i > 0 {
mi = min(mi, f[i-1][j])
}
if j > 0 {
mi = min(mi, f[i][j-1])
}
ans = max(ans, x-mi)
f[i][j] = min(x, mi)
}
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(m * n * max(m, n)) |
| Sorting with Binary Search | Time Complexity: O(m * n * log(n)) |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Prefix Minimum | O(m*n) | O(1) | Best general solution for matrix traversal when moves are restricted to right and down |
| Sorting + Binary Search on Difference | O(m*n log V) | O(m*n) | Useful when framing the task as a decision problem or exploring value-range search strategies |
Frequently asked questions
Is Maximum Difference Score in a Grid easy or hard?
Maximum Difference Score in a Grid is rated Medium difficulty. The challenge is recognizing that the problem reduces to maintaining the minimum earlier value in a constrained traversal. Once that insight is clear, the implementation is straightforward.
Maximum Difference Score in a Grid Python/Java solution
The algorithm is language independent and easy to implement in Python, Java, C++, JavaScript, or C#. Iterate through the grid, maintain the minimum previously reachable value, and update the maximum difference at each step. The implementation is typically under 15–20 lines in most languages.
How to solve Maximum Difference Score in a Grid in O(m*n)?
Traverse the grid row by row while maintaining the minimum value reachable from any earlier cell in the same row or column path. For each position compute the difference between the current value and the smallest previous value. Update the answer and refresh the running minimum. This single pass produces the maximum score in O(m*n) time.
What is the best approach for Maximum Difference Score in a Grid?
The most efficient approach uses dynamic programming with a running prefix minimum. While scanning the grid, track the smallest value reachable from previous cells (top or left). For each cell compute grid[i][j] - minPrev and update the maximum score. This runs in O(m*n) time and O(1) extra space.
Is Maximum Difference Score in a Grid asked at Google/Amazon/Meta?
Grid dynamic programming and prefix-minimum style matrix problems are common in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of tracking optimal values during matrix traversal frequently appears in coding interviews.
What data structure is used in Maximum Difference Score in a Grid?
The core solution uses a matrix traversal combined with dynamic programming. Instead of extra data structures, it maintains a running minimum value while iterating through the grid. Some alternative approaches may use auxiliary matrices for prefix minima.
What is the time complexity of Maximum Difference Score in a Grid?
The optimal dynamic programming solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is processed once while maintaining the minimum value from reachable previous cells. Space complexity is O(1) if the grid itself is reused.