Problem Description

You have an m x n matrix of integers called points. Your goal is to collect the maximum possible score by selecting exactly one cell from each row.

The scoring works as follows:

• When you pick a cell at position (r, c), you gain points[r][c] points
• However, there's a penalty for picking cells that are far apart horizontally between consecutive rows
• If you pick cell at column c1 in row r and cell at column c2 in row r+1, you lose abs(c1 - c2) points

Your task is to find the maximum total score possible.

For example, with the matrix:

[[1,2,3],
 [1,5,1],
 [3,1,1]]

If you pick cells at positions (0,2), (1,1), and (2,0), you would:

• Gain: 3 + 5 + 3 = 11 points from the cell values
• Lose: |2-1| + |1-0| = 1 + 1 = 2 points from column differences
• Final score: 11 - 2 = 9

The challenge is to find the optimal path through the matrix that maximizes your final score after accounting for both the cell values and the penalties for horizontal movement between rows.

Intuition

This problem screams dynamic programming because we need to make optimal choices row by row, and our decision at each row depends on what we chose in the previous row.

Let's think about it step by step. If we define f[j] as the maximum score we can get ending at column j in the current row, then for the next row, we need to consider all possible previous columns we could have come from.

The naive approach would be: for each cell (r, c2) in the current row, check all possible previous columns c1 and calculate f[c1] + points[r][c2] - abs(c1 - c2). But this gives us O(n²) time per row, which is too slow given the constraints.

The key insight is recognizing that the penalty term abs(c1 - c2) can be split based on whether we're coming from the left or right:

• If coming from left (c1 ≤ c2): penalty is c2 - c1
• If coming from right (c1 > c2): penalty is c1 - c2

This allows us to rewrite the transition as:

• From left: f[c1] + points[r][c2] - (c2 - c1) = (f[c1] + c1) + points[r][c2] - c2
• From right: f[c1] + points[r][c2] - (c1 - c2) = (f[c1] - c1) + points[r][c2] + c2

Notice how we can separate the terms that depend on c1 from those that depend on c2. This means:

• For transitions from the left, we want to maximize f[c1] + c1 for all c1 ≤ c2
• For transitions from the right, we want to maximize f[c1] - c1 for all c1 > c2

We can compute these maximum values efficiently by doing two passes:

1. Left-to-right pass: maintain the running maximum of f[j] + j
2. Right-to-left pass: maintain the running maximum of f[j] - j

This optimization reduces our time complexity from O(mn²) to O(mn), making the solution efficient enough for the given constraints.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation uses dynamic programming with space optimization, storing only the previous row's results instead of the entire DP table.

Initial Setup:

• n = len(points[0]): Get the number of columns
• f = points[0][:]: Initialize f with the first row's values (no previous row to consider penalties)

Processing Each Subsequent Row:

For each row starting from the second one (points[1:]), we calculate the new DP values in array g:

1. Left-to-Right Pass:

lmx = -inf
for j in range(n):
    lmx = max(lmx, f[j] + j)
    g[j] = max(g[j], p[j] + lmx - j)

• lmx tracks the maximum value of f[j] + j seen so far from the left
• For each column j, we compute the best score if we came from any column to the left or the current column
• The formula p[j] + lmx - j represents:
  • p[j]: points gained at current cell
  • lmx: best value of (previous_score + previous_column)
  • -j: subtract current column (part of the distance penalty)

2. Right-to-Left Pass:

rmx = -inf
for j in range(n - 1, -1, -1):
    rmx = max(rmx, f[j] - j)
    g[j] = max(g[j], p[j] + rmx + j)

• rmx tracks the maximum value of f[j] - j seen so far from the right
• For each column j, we compute the best score if we came from any column to the right
• The formula p[j] + rmx + j represents:
  • p[j]: points gained at current cell
  • rmx: best value of (previous_score - previous_column)
  • +j: add current column (part of the distance penalty when coming from right)

3. Update for Next Iteration:

f = g

After processing both passes, g contains the maximum scores for the current row, which becomes f for the next iteration.

Final Result:

return max(f)

After processing all rows, return the maximum value in f, which represents the best score achievable ending at any column in the last row.

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns Space Complexity: O(n) for storing the DP arrays f and g

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given matrix:

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

Step 1: Initialize with first row

• f = [2, 1, 4] (no penalties since it's the first row)

Step 2: Process second row [3, 5, 2]

• Create g = [-inf, -inf, -inf] to store new values

Left-to-Right Pass:

• j = 0:
  • lmx = max(-inf, f[0] + 0) = max(-inf, 2 + 0) = 2
  • g[0] = max(-inf, 3 + 2 - 0) = 5
• j = 1:
  • lmx = max(2, f[1] + 1) = max(2, 1 + 1) = 2
  • g[1] = max(-inf, 5 + 2 - 1) = 6
• j = 2:
  • lmx = max(2, f[2] + 2) = max(2, 4 + 2) = 6
  • g[2] = max(-inf, 2 + 6 - 2) = 6

After left pass: g = [5, 6, 6]

Right-to-Left Pass:

• j = 2:
  • rmx = max(-inf, f[2] - 2) = max(-inf, 4 - 2) = 2
  • g[2] = max(6, 2 + 2 + 2) = max(6, 6) = 6
• j = 1:
  • rmx = max(2, f[1] - 1) = max(2, 1 - 1) = 2
  • g[1] = max(6, 5 + 2 + 1) = max(6, 8) = 8
• j = 0:
  • rmx = max(2, f[0] - 0) = max(2, 2 - 0) = 2
  • g[0] = max(5, 3 + 2 + 0) = max(5, 5) = 5

After right pass: g = [5, 8, 6]

Step 3: Final result

• f = [5, 8, 6]
• Maximum score = 8

This corresponds to choosing:

• Row 0, Column 2: gain 4 points
• Row 1, Column 1: gain 5 points
• Penalty: |2 - 1| = 1
• Total: 4 + 5 - 1 = 8

The algorithm efficiently computes the optimal path by considering transitions from both left and right directions separately, avoiding the need to check all possible previous columns individually.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the points matrix.

The algorithm iterates through each row of the points matrix (excluding the first row which is used for initialization), resulting in m - 1 iterations. For each row, it performs two passes through all columns:

• First pass from left to right: O(n) operations
• Second pass from right to left: O(n) operations

Since we have m - 1 rows and each row requires 2n operations, the total time complexity is O((m - 1) * 2n) = O(m * n).

Space Complexity: O(n) where n is the number of columns.

The algorithm uses:

• Array f to store the maximum points for the previous row: O(n) space
• Array g to store the maximum points for the current row: O(n) space
• Variables lmx and rmx for tracking maximum values: O(1) space

The total auxiliary space used is O(n) + O(n) + O(1) = O(n). Note that we're not counting the input array in the space complexity analysis, only the additional space used by the algorithm.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Distance Penalty Calculation

A common mistake is misunderstanding how the absolute distance penalty works when transitioning between columns in consecutive rows. Developers often incorrectly apply the penalty formula or confuse when to add vs. subtract the column indices.

Pitfall Example:

# WRONG: Incorrectly calculating penalty
for j in range(n):
    for prev_j in range(n):
        # This naive approach might use wrong signs or formula
        current_row_max[j] = max(current_row_max[j], 
                                prev_row_max[prev_j] + current_row_points[j] - (j - prev_j))

Why it's wrong: The absolute value abs(prev_j - j) needs careful handling. When prev_j < j, the penalty is j - prev_j, but when prev_j > j, it's prev_j - j. The naive subtraction (j - prev_j) doesn't account for this.

Solution: Separate the calculation into two passes:

• Left-to-right pass: Handle transitions from columns to the left (where prev_col <= current_col)
• Right-to-left pass: Handle transitions from columns to the right (where prev_col >= current_col)

This way, you can algebraically manipulate the formula to avoid explicitly calculating absolute values for each pair.

2. Not Initializing the Current Row Array Properly

Pitfall Example:

# WRONG: Reusing the same array reference
current_row_max = prev_row_max  # This creates a reference, not a copy!

Why it's wrong: This doesn't create a new array but rather points to the same array in memory. Modifications to current_row_max will affect prev_row_max, leading to incorrect calculations.

Solution: Always create a fresh array for each row:

current_row_max = [0] * num_cols  # Create new array
# OR
current_row_max = [float('-inf')] * num_cols  # If you want to be explicit about initialization

3. Attempting O(n²) Solution Without Optimization

Pitfall Example:

# WRONG: Brute force O(n²) per row - will cause Time Limit Exceeded for large inputs
for current_col in range(num_cols):
    for prev_col in range(num_cols):
        current_row_max[current_col] = max(
            current_row_max[current_col],
            prev_row_max[prev_col] + current_row_points[current_col] - abs(prev_col - current_col)
        )

Why it's wrong: While logically correct, this has O(m × n²) time complexity, which is too slow for large matrices.

Solution: Use the two-pass optimization technique that reduces the inner loop from O(n²) to O(n) by maintaining running maximums (left_max and right_max) that efficiently track the best previous column choice.