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] <= 105The key idea in #3148 Maximum Difference Score in a Grid is to find the largest possible difference between two cells where the second cell is reachable from the first by moving only right or down. A brute force approach would compare every valid pair of cells, but this leads to O(m^2 * n^2) complexity, which is inefficient for larger grids.
An efficient strategy uses dynamic programming. As you scan the grid row by row, maintain the minimum value reachable from the top or left before the current cell. This represents the best starting point for forming a score difference. For each cell, compute the candidate score by subtracting the stored minimum value from the current cell value. Update the global maximum difference while also updating the running minimum for future cells.
This approach ensures each cell is processed once, resulting in O(m × n) time complexity. The auxiliary storage for tracking minimum values can be optimized to O(n) or O(m × n) depending on the implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Pair Comparison | O(m^2 * n^2) | O(1) |
| Dynamic Programming with Running Minimum | O(m * n) | O(n) or O(m * n) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Any path from a cell <code>(x1, y1)</code> to another cell <code>(x2, y2)</code> will always have a score of <code>grid[x2][y2] - grid[x1][y1]</code>.
Let’s say we fix the starting cell <code>(x1, y1)</code>, how to the find a cell <code>(x2, y2)</code> such that the value <code>grid[x2][y2] - grid[x1][y1]</code> is the maximum possible?
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Grid dynamic programming and matrix optimization problems are common in FAANG-style interviews. While this exact question may vary, the underlying concepts such as prefix minimums, DP on grids, and path constraints are frequently tested.
A 2D grid combined with a dynamic programming array or running minimum tracker works best. The DP structure helps store the smallest value reachable before each position, enabling efficient difference calculations.
The optimal approach uses dynamic programming to track the minimum reachable value from the top or left of each cell. By maintaining this running minimum, you can compute the best difference for every cell in O(m × n) time. This avoids checking all cell pairs.
Yes, the problem can be solved efficiently using dynamic programming. Instead of comparing all cell pairs, you maintain the minimum value seen along valid paths and compute the difference in a single grid traversal.