LeetCode 3148 - Maximum Difference Score in a Grid

The problem gives us an m x n matrix called grid, where every cell contains a positive integer. From any cell (r1, c1), we are allowed to move to another cell (r2, c2) as long as the destination is either strictly below or strictly to the right.

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 3148

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem gives us an m x n matrix called grid, where every cell contains a positive integer. From any cell (r1, c1), we are allowed to move to another cell (r2, c2) as long as the destination is either strictly below or strictly to the right. In other words:

  • r2 > r1, or
  • c2 > c1

The move does not need to be adjacent. We can jump multiple rows or columns in a single move.

The score of one move is:

$\text{score} = c_2 - c_1$

where c1 is the value of the starting cell and c2 is the value of the destination cell.

We may start from any cell in the grid, but we must make at least one move. The goal is to maximize the total score across all moves.

An important observation is that if we move through several cells:

  • a -> b contributes b - a
  • b -> c contributes c - b

The total becomes:

  • (b - a) + (c - b) = c - a

The intermediate values cancel out. This means that the total score of an entire path is simply:

  • final cell value minus starting cell value

Therefore, instead of thinking about many moves, we only need to find two reachable cells where:

  • the second cell is below or to the right of the first cell
  • the value difference is maximized

The constraints are important:

  • m * n <= 10^5
  • both dimensions can be as large as 1000

A brute force solution that compares every pair of cells would be too slow because there can be up to 10^10 pairs in the worst case.

Several edge cases are important:

  • The answer can be negative if every reachable destination has a smaller value.
  • Since at least one move is required, we cannot simply return 0.
  • Large matrices require an efficient linear or near-linear solution.
  • Multiple paths may lead to the same destination, but only the best starting value matters.

Approaches

Brute Force

A straightforward solution is to try every possible starting cell and every reachable destination cell.

For every cell (r, c):

  • check every cell below it
  • check every cell to the right of it
  • compute the difference

Then keep track of the maximum score.

This works because it explicitly evaluates every legal move pair, guaranteeing that the best answer is found.

However, the complexity is far too large. With up to 10^5 cells, comparing all pairs can approach O((mn)^2), which is not feasible.

Key Insight

The critical observation is that the total score of a path telescopes.

For example:

  • (7 - 5) + (14 - 7) = 14 - 5

All intermediate terms cancel out.

So the problem becomes:

For each cell, find the minimum value that can appear before it, from either the top or the left reachable region.

If we process the grid from top-left to bottom-right, then for each cell (r, c):

  • any valid previous cell must lie somewhere above or somewhere left

  • therefore we only need the minimum value seen in the rectangle:

  • rows [0..r]

  • columns [0..c]

If we know that minimum previous value, then the best score ending at (r, c) is:

$\text{best score ending here} = grid[r][c] - \text{minimum previous value}$

We can compute this efficiently with dynamic programming.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((mn)^2) O(1) Compare every reachable pair of cells
Optimal O(mn) O(mn) Dynamic programming with running minimums

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

  1. Create a DP matrix called min_value.

min_value[r][c] will store the minimum grid value seen in the rectangle from (0,0) to (r,c).

This allows us to quickly determine the best possible starting cell for any destination. 2. Initialize the answer to negative infinity.

The answer may legitimately be negative, so starting from 0 would be incorrect. 3. Traverse the grid row by row, from top-left to bottom-right.

This traversal order guarantees that when we process (r,c), all possible predecessor regions have already been processed. 4. For each cell, determine the minimum reachable previous value.

A valid predecessor can come from:

  • above
  • left

So we compute:

  • minimum from top
  • minimum from left

and take the smaller one. 5. Compute the best score ending at the current cell.

The current cell acts as the destination.

The best possible starting point is the smallest reachable value before it.

So:

  • score = grid[r][c] - previous_min
  1. Update the global answer.

If this score is larger than the current best answer, update it. 7. Update the DP state for future cells.

The rectangle minimum ending at (r,c) is:

  • the current cell value
  • or the minimum already seen from top/left

whichever is smaller. 8. Continue until all cells are processed. 9. Return the maximum score found.

Why it works

For every destination cell (r,c), any valid starting cell must lie somewhere above or to the left because movement is only allowed downward or rightward.

The DP table maintains exactly the minimum value reachable before each cell. Since the total score of a path collapses to:

  • destination value minus starting value

choosing the smallest reachable starting value always produces the best score for that destination.

By evaluating every cell once and computing the best possible score ending there, the algorithm guarantees that the global maximum score is found.

Python Solution

from typing import List

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        min_value = [[0] * cols for _ in range(rows)]

        answer = float("-inf")

        for r in range(rows):
            for c in range(cols):
                current = grid[r][c]

                best_previous = float("inf")

                if r > 0:
                    best_previous = min(best_previous, min_value[r - 1][c])

                if c > 0:
                    best_previous = min(best_previous, min_value[r][c - 1])

                if best_previous != float("inf"):
                    answer = max(answer, current - best_previous)

                min_value[r][c] = min(current, best_previous)

        return answer

The implementation follows the dynamic programming strategy directly.

The min_value matrix stores the smallest value seen so far for every top-left subrectangle. This allows constant time access to the best starting value for each destination cell.

For each cell:

  • we gather the minimum reachable value from the top and left
  • compute the best score ending at the current cell
  • update the answer
  • store the updated rectangle minimum

The condition:

if best_previous != float("inf"):

ensures that the top-left corner does not attempt to form a move, since it has no valid predecessor.

The algorithm processes each cell exactly once, making it efficient enough for the input limits.

Go Solution

package main

import "math"

func maxScore(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	minValue := make([][]int, rows)
	for i := range minValue {
		minValue[i] = make([]int, cols)
	}

	answer := math.MinInt32

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			current := grid[r][c]

			bestPrevious := math.MaxInt32

			if r > 0 {
				if minValue[r-1][c] < bestPrevious {
					bestPrevious = minValue[r-1][c]
				}
			}

			if c > 0 {
				if minValue[r][c-1] < bestPrevious {
					bestPrevious = minValue[r][c-1]
				}
			}

			if bestPrevious != math.MaxInt32 {
				score := current - bestPrevious
				if score > answer {
					answer = score
				}
			}

			minValue[r][c] = current
			if bestPrevious < minValue[r][c] {
				minValue[r][c] = bestPrevious
			}
		}
	}

	return answer
}

The Go implementation mirrors the Python solution closely.

Since Go does not provide built in infinity values for integers, math.MaxInt32 and math.MinInt32 are used as sentinel values.

The DP matrix is created using slices of slices. Each cell is processed once, and updates happen in constant time.

Integer overflow is not a concern because:

  • grid values are at most 10^5
  • score differences remain safely within 32-bit integer range

Worked Examples

Example 1

grid =
[
  [9, 5, 7, 3],
  [8, 9, 6, 1],
  [6, 7,14, 3],
  [2, 5, 3, 1]
]

We maintain:

  • min_value[r][c]
  • global answer
Cell Current Value Best Previous Min Score Answer min_value
(0,0) 9 inf none -inf 9
(0,1) 5 9 -4 -4 5
(0,2) 7 5 2 2 5
(0,3) 3 5 -2 2 3
(1,0) 8 9 -1 2 8
(1,1) 9 5 4 4 5
(1,2) 6 5 1 4 5
(1,3) 1 3 -2 4 1
(2,0) 6 8 -2 4 6
(2,1) 7 5 2 4 5
(2,2) 14 5 9 9 5
(2,3) 3 1 2 9 1
(3,0) 2 6 -4 9 2
(3,1) 5 2 3 9 2
(3,2) 3 2 1 9 2
(3,3) 1 1 0 9 1

Final answer:

9

Example 2

grid =
[
  [4,3,2],
  [3,2,1]
]
Cell Current Value Best Previous Min Score Answer
(0,0) 4 inf none -inf
(0,1) 3 4 -1 -1
(0,2) 2 3 -1 -1
(1,0) 3 4 -1 -1
(1,1) 2 3 -1 -1
(1,2) 1 2 -1 -1

Final answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(mn) Every cell is processed exactly once
Space O(mn) The DP matrix stores one value per cell

The algorithm performs only constant work per grid cell:

  • checking top and left minimums
  • updating the answer
  • storing a new minimum

Since there are m * n cells, the total runtime is linear in the size of the grid.

The DP table also contains one value per cell, resulting in linear auxiliary space usage.

Test Cases

from typing import List

class Solution:
    def maxScore(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        min_value = [[0] * cols for _ in range(rows)]

        answer = float("-inf")

        for r in range(rows):
            for c in range(cols):
                current = grid[r][c]

                best_previous = float("inf")

                if r > 0:
                    best_previous = min(best_previous, min_value[r - 1][c])

                if c > 0:
                    best_previous = min(best_previous, min_value[r][c - 1])

                if best_previous != float("inf"):
                    answer = max(answer, current - best_previous)

                min_value[r][c] = min(current, best_previous)

        return answer

sol = Solution()

assert sol.maxScore([
    [9, 5, 7, 3],
    [8, 9, 6, 1],
    [6, 7, 14, 3],
    [2, 5, 3, 1]
]) == 9  # provided example with positive result

assert sol.maxScore([
    [4, 3, 2],
    [3, 2, 1]
]) == -1  # provided example with all decreasing values

assert sol.maxScore([
    [1, 2],
    [3, 4]
]) == 3  # best move is 1 -> 4

assert sol.maxScore([
    [5, 5],
    [5, 5]
]) == 0  # equal values produce zero score

assert sol.maxScore([
    [10, 1],
    [2, 20]
]) == 19  # large positive jump

assert sol.maxScore([
    [100000, 1],
    [1, 100000]
]) == 99999  # tests large values

assert sol.maxScore([
    [7, 6, 5, 4]
]) == -1  # single row decreasing

assert sol.maxScore([
    [1],
    [2],
    [3],
    [4]
]) == 3  # single column increasing

assert sol.maxScore([
    [8, 1, 9]
]) == 8  # jump across columns

assert sol.maxScore([
    [9],
    [1]
]) == -8  # minimum valid grid size

Test Summary

Test Why
Mixed positive example Verifies standard DP behavior
Fully decreasing grid Ensures negative answers are handled
Increasing 2x2 grid Validates optimal destination selection
Equal values Confirms zero score handling
Large jump case Tests long-distance movement
Maximum value range Verifies integer safety
Single row Ensures horizontal-only movement works
Single column Ensures vertical-only movement works
Non-adjacent jump Confirms jumps are allowed
Smallest valid dimensions Tests boundary constraints

Edge Cases

All Moves Produce Negative Scores

A common mistake is initializing the answer to 0. This fails when every possible move decreases the score.

For example:

[
  [4, 3],
  [2, 1]
]

Every move is negative, so the correct answer is negative as well.

The implementation avoids this bug by initializing the answer to negative infinity, ensuring negative results are preserved correctly.

Single Row or Single Column

When the grid has only one row or one column, movement is restricted to a single direction.

For example:

[[1, 2, 3, 4]]

Only rightward moves are possible.

The DP transition still works because each cell checks independently:

  • top neighbor if it exists
  • left neighbor if it exists

No special handling is required.

Large Non-Adjacent Jumps

The problem allows jumping multiple rows or columns in one move. A naive adjacent-only interpretation would be incorrect.

For example:

[
  [1, 100]
]

The optimal move directly jumps from 1 to 100.

The DP formulation naturally supports this because min_value[r][c] represents the minimum value anywhere in the reachable prefix region, not just adjacent cells.

Equal Values

If two reachable cells contain the same value, the move score becomes zero.

For example:

[
  [5, 5]
]

The algorithm correctly computes:

  • 5 - 5 = 0

and returns zero when it is the maximum possible score.