We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Difference Score in a Grid

Number: 3391

Difficulty: Medium

Paid? No

Companies: Intuit

Problem Description

You are given an m x n grid of positive integers. You may start at any cell and make at least one move. A move is allowed only to a cell that is either below (same column, higher row index) or to the right (same row, higher column index) of the current cell. The score of a move is the difference between the destination cell’s value and the source cell’s value. The total score of a series of moves is the sum of these differences (which telescopes to the difference between the final cell and the starting cell). The goal is to determine the maximum total score achievable by following these rules.

Key Insights

  • Every valid sequence of moves has a final score equal to (final cell value – starting cell value) because the intermediate differences cancel out.
  • The movement constraint (only move down or right) implies that the starting cell’s indices must be no greater than the final cell’s indices.
  • To obtain the answer, we need to find the maximum difference grid[p][q] – grid[i][j] for any two cells such that i ≤ p and j ≤ q and the cells are not the same.
  • A dynamic programming (or prefix computation) approach can be used to compute, for every cell, the minimum cell value from which it can be reached (in the allowed region), then update the answer using grid[i][j] minus that minimum.
  • The trick is to be careful not to allow the starting cell to be the same as the destination; hence, when computing the “prefix minimum” for a cell, we exclude the cell itself.

Space and Time Complexity

Time Complexity: O(m * n) – We traverse the grid once to build the prefix minima and compute the difference for each cell. Space Complexity: O(m * n) – A separate 2D array is maintained to store the minimum values from valid predecessors.

Solution

We build a 2D helper array called bestBefore where bestBefore[i][j] is the minimum value among all cells in the submatrix defined by rows 0 to i and columns 0 to j excluding the current cell (i, j). This is computed iteratively: • For the first row (i = 0) with j > 0, the only predecessors are in the same row. • For the first column (j = 0) with i > 0, the only predecessors are in the same column. • For interior cells, the best candidate is the minimum from the cell just above, left, or the best values from previously computed portions. Then for every cell (except cell (0,0) where there is no predecessor) we calculate the potential score: grid[i][j] - bestBefore[i][j]. The final answer is the maximum of these scores.

Code Solutions

# Python solution with line-by-line comments

def maxDifferenceScore(grid):
    # Get dimensions of the grid
    m = len(grid)
    n = len(grid[0])
    
    # Create a 2D array to hold the minimum value from preceding cells
    # Initialize with a high value
    INF = float('inf')
    bestBefore = [[INF] * n for _ in range(m)]
    
    # Answer will store the maximum difference
    ans = -10**9  # or use -INF depending on constraints
    
    # Process each cell row by row
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:
                # No valid predecessor for the very first cell
                bestBefore[i][j] = INF
            elif i == 0:
                # First row, allowed predecessor is only from left
                # bestBefore[0][j] is the minimum between the previous best and the immediate left cell
                bestBefore[i][j] = min(bestBefore[i][j-1], grid[i][j-1])
            elif j == 0:
                # First column, allowed predecessor is only from above
                bestBefore[i][j] = min(bestBefore[i-1][j], grid[i-1][j])
            else:
                # For other cells, consider:
                # best value from above region, left region, and the immediate top and left cells
                bestBefore[i][j] = min(bestBefore[i-1][j], bestBefore[i][j-1], grid[i-1][j], grid[i][j-1])
            
            # Only update answer if there is at least one predecessor
            if bestBefore[i][j] != INF:
                potentialScore = grid[i][j] - bestBefore[i][j]
                ans = max(ans, potentialScore)
                
    return ans

# Example usage:
grid1 = [[9,5,7,3],[8,9,6,1],[6,7,14,3],[2,5,3,1]]
print(maxDifferenceScore(grid1))  # Expected output: 9

grid2 = [[4,3,2],[3,2,1]]
print(maxDifferenceScore(grid2))  # Expected output: -1
← Back to All Questions