Watch 6 video solutions for Maximum Difference Score in a Grid, a medium level problem involving Array, Dynamic Programming, Matrix. This walkthrough by codingMohan has 1,930 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem 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 | 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 |