Maximum Difference Score in a Grid - Solution & Explanation
Problem Statement
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.
This solution initializes a 2D dp array where each entry is the maximum difference from that cell to any valid cell below or to the right. The maximum difference for each cell is calculated, and the maximum is stored and returned.
Code
C
C++
Java
Python
C#
JavaScript
Go
TypeScript
Complexity
Time Complexity: O(m * n2)
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.
This solution sorts each row and creates column arrays to sort. It uses binary searches to determine the maximal differences in a sorted array structure for each element, optimizing search operations over possible moves.
Complexity
Time Complexity: O(m * n * log(n)) (Sorting takes NlogN for each row)
Space Complexity: O(m * n) (additional space for data structures)
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(m * n2) |
| Sorting with Binary Search | Time Complexity: O(m * n * log(n)) (Sorting takes NlogN for each row) |
Detailed 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 |
Video Solution
3148. Maximum Difference Score in a Grid | Top Down + Bottom Up | Weekly Leetcode 397 • codingMohan • 1,988 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Maximum Difference Score in a Grid easy or hard?
Maximum Difference Score in a Grid Python/Java solution
How to solve Maximum Difference Score in a Grid in O(m*n)?
What is the best approach for Maximum Difference Score in a Grid?
Is Maximum Difference Score in a Grid asked at Google/Amazon/Meta?
What data structure is used in Maximum Difference Score in a Grid?
What is the time complexity of Maximum Difference Score in a Grid?
Ready to solve this problem?
Practice Maximum Difference Score in a Grid with our built-in code editor and test cases.
Practice on FleetCode