Maximum Difference Score in a Grid

Medium
1655.

Maximum Difference Score in a Grid

Maximum Difference Score in a Grid is a medium coding problem on arrays, dynamic programming and matrix, asked in Amazon and Google interviews.

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.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxScore = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.length
  • n == grid[i].length
  • 2 <= m, n <= 1000
  • 4 <= m * n <= 10^5
  • 1 <= grid[i][j] <= 10^5

Hints for Maximum Difference Score in a Grid

  1. Hint 1

    Add up the scores along a path: the middle values cancel. A path's score is just (last value) − (first value).

  2. 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).

  3. 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) scores grid[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

  1. Let mn[i][j] be the smallest value in the rectangle of rows 0..i and columns 0..j.
  2. 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 with grid[i][j] − prev.
  3. Set mn[i][j] = min(prev, grid[i][j]).
  4. 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 in prev.
  • 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 best

Java

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