LeetCode 1937 - Maximum Number of Points with Cost

The problem gives us an m x n matrix called points. We must choose exactly one cell from every row. The value of the chosen cell is added to our score. However, there is a movement penalty between consecutive rows.

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 1937

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem gives us an m x n matrix called points. We must choose exactly one cell from every row. The value of the chosen cell is added to our score.

However, there is a movement penalty between consecutive rows. If we choose column c1 in row r and column c2 in row r + 1, we lose abs(c1 - c2) points. This means moving farther horizontally between rows becomes more expensive.

The goal is to maximize the final score after adding all chosen cell values and subtracting all movement penalties.

More formally, if we choose columns:

c0, c1, c2, ..., c(m-1)

then the score becomes:

points[0][c0]
+ points[1][c1]
+ ...
+ points[m-1][c(m-1)]
- abs(c0 - c1)
- abs(c1 - c2)
- ...
- abs(c(m-2) - c(m-1))

We need to compute the maximum possible value.

The constraints are extremely important:

  • m * n <= 100000
  • Each dimension can individually be as large as 100000

This means we cannot afford algorithms with complexity like O(m * n^2) in the worst case. Even a matrix with 1 x 100000 or 100000 x 1 is possible.

The problem guarantees:

  • Every row has the same number of columns.
  • Values are non-negative.
  • At least one row and one column exist.

Several edge cases matter immediately:

  • A matrix with only one row, where there is no movement penalty.
  • A matrix with one column, where movement cost is always zero.
  • Large matrices where a naive transition between all column pairs becomes too slow.
  • Cases where moving to a high-valued distant column is still worth paying the penalty.

This problem is fundamentally a dynamic programming optimization problem.

Approaches

Brute Force Dynamic Programming

A natural first idea is dynamic programming.

Define:

dp[r][c]

as the maximum score obtainable when we end at column c in row r.

The transition becomes:

dp[r][c] =
points[r][c] +
max over all previous columns k:
(
    dp[r-1][k] - abs(k - c)
)

This recurrence is correct because every valid solution reaching (r, c) must come from some column k in the previous row.

Unfortunately, computing this transition directly is expensive.

For every row:

  • We iterate over all current columns c
  • For each c, we scan all previous columns k

That gives:

O(m * n^2)

With n up to 100000, this is far too slow.

Key Insight for Optimization

The expensive part is:

max(dp[k] - abs(k - c))

The absolute value creates two cases:

k <= c:
dp[k] - (c - k)
= (dp[k] + k) - c

and

k >= c:
dp[k] - (k - c)
= (dp[k] - k) + c

This is the critical observation.

For every column c, we need:

max(
    max(dp[k] + k) - c,
    max(dp[k] - k) + c
)

Instead of recomputing these maxima repeatedly, we can preprocess them with two linear sweeps:

  • Left-to-right sweep handles dp[k] + k
  • Right-to-left sweep handles dp[k] - k

This reduces each row transition from O(n^2) to O(n).

Overall complexity becomes:

O(m * n)

which fits the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force DP O(m * n²) O(n) or O(m * n) Checks every previous column for every current column
Optimal DP with Two Sweeps O(m * n) O(n) Uses left and right maximum propagation

Algorithm Walkthrough

Step 1: Initialize DP for the First Row

The first row has no previous row, so there is no movement penalty.

Therefore:

dp[c] = points[0][c]

This represents the best score ending at each column in row 0.

Step 2: Process Rows One by One

For every subsequent row, we compute a new DP array.

We need:

new_dp[c] =
points[row][c] +
max(previous_dp[k] - abs(k - c))

Computing this directly would be too expensive.

Step 3: Left-to-Right Sweep

We create an array called left.

While scanning from left to right, we maintain:

max(previous_dp[k] + k)

for all positions k <= c.

At position c:

left[c] =
max(left[c-1], previous_dp[c] + c)

This lets us compute:

max(previous_dp[k] - (c - k))

efficiently as:

left[c] - c

Step 4: Right-to-Left Sweep

We create another array called right.

While scanning from right to left, we maintain:

max(previous_dp[k] - k)

for all positions k >= c.

At position c:

right[c] =
max(right[c+1], previous_dp[c] - c)

This lets us compute:

max(previous_dp[k] - (k - c))

efficiently as:

right[c] + c

Step 5: Compute the Best Transition

For every column c:

best_previous =
max(
    left[c] - c,
    right[c] + c
)

Then:

new_dp[c] =
points[row][c] + best_previous

Step 6: Move to the Next Row

After processing the row:

dp = new_dp

Repeat until all rows are processed.

Step 7: Return the Maximum Value

The final answer is:

max(dp)

because the optimal path may end in any column of the last row.

Why it works

The algorithm works because every transition cost depends only on column distance. By separating the absolute value into two directional cases, we transform the quadratic transition into two linear scans.

The left sweep correctly captures all transitions from columns on the left side, while the right sweep captures transitions from columns on the right side. Taking the maximum of the two gives the exact optimal transition value for every column.

Since every row transition is computed optimally, the DP invariant holds:

dp[c] always stores the maximum achievable score ending at column c for the current row.

Therefore, after processing all rows, the maximum value in the final DP array is the global optimum.

Python Solution

from typing import List

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        rows = len(points)
        cols = len(points[0])

        dp = [value for value in points[0]]

        for row in range(1, rows):
            left = [0] * cols
            right = [0] * cols

            left[0] = dp[0]
            for col in range(1, cols):
                left[col] = max(left[col - 1] - 1, dp[col])

            right[cols - 1] = dp[cols - 1]
            for col in range(cols - 2, -1, -1):
                right[col] = max(right[col + 1] - 1, dp[col])

            new_dp = [0] * cols

            for col in range(cols):
                best_previous = max(left[col], right[col])
                new_dp[col] = points[row][col] + best_previous

            dp = new_dp

        return max(dp)

The implementation stores only one DP row at a time, which keeps memory usage efficient.

The variable dp represents the best achievable score for each column in the previous row.

The left sweep propagates values from left to right. Moving one step to the right costs 1, so we decrement the propagated value by 1 at each step:

left[col] = max(left[col - 1] - 1, dp[col])

This compactly represents:

max(dp[k] - (col - k))

for all k <= col.

The right sweep performs the symmetric operation from right to left:

right[col] = max(right[col + 1] - 1, dp[col])

This represents:

max(dp[k] - (k - col))

for all k >= col.

Finally, for each column we choose the better of the two directional transitions and add the current cell value.

Go Solution

func maxPoints(points [][]int) int64 {
    rows := len(points)
    cols := len(points[0])

    dp := make([]int64, cols)

    for c := 0; c < cols; c++ {
        dp[c] = int64(points[0][c])
    }

    for r := 1; r < rows; r++ {
        left := make([]int64, cols)
        right := make([]int64, cols)

        left[0] = dp[0]
        for c := 1; c < cols; c++ {
            candidate := left[c-1] - 1
            if dp[c] > candidate {
                left[c] = dp[c]
            } else {
                left[c] = candidate
            }
        }

        right[cols-1] = dp[cols-1]
        for c := cols - 2; c >= 0; c-- {
            candidate := right[c+1] - 1
            if dp[c] > candidate {
                right[c] = dp[c]
            } else {
                right[c] = candidate
            }
        }

        newDP := make([]int64, cols)

        for c := 0; c < cols; c++ {
            bestPrevious := left[c]
            if right[c] > bestPrevious {
                bestPrevious = right[c]
            }

            newDP[c] = int64(points[r][c]) + bestPrevious
        }

        dp = newDP
    }

    answer := dp[0]
    for _, value := range dp {
        if value > answer {
            answer = value
        }
    }

    return answer
}

The Go solution uses int64 because the total score can exceed the range of a 32-bit integer when many large values accumulate across rows.

Slices are used instead of fixed-size arrays because matrix dimensions are only known at runtime.

Unlike Python integers, Go integers do not automatically expand, so explicit int64 conversion is necessary.

Worked Examples

Example 1

Input:

points = [
    [1, 2, 3],
    [1, 5, 1],
    [3, 1, 1]
]

Initial DP:

Column DP
0 1
1 2
2 3

Processing Row 1

Current row:

[1, 5, 1]

Left Sweep

Column Computation Left
0 1 1
1 max(1 - 1, 2) 2
2 max(2 - 1, 3) 3

Result:

left = [1, 2, 3]

Right Sweep

Column Computation Right
2 3 3
1 max(3 - 1, 2) 2
0 max(2 - 1, 1) 1

Result:

right = [1, 2, 3]

New DP

Column max(left,right) points New DP
0 1 1 2
1 2 5 7
2 3 1 4

Result:

dp = [2, 7, 4]

Processing Row 2

Current row:

[3, 1, 1]

Left Sweep

Column Computation Left
0 2 2
1 max(2 - 1, 7) 7
2 max(7 - 1, 4) 6

Result:

left = [2, 7, 6]

Right Sweep

Column Computation Right
2 4 4
1 max(4 - 1, 7) 7
0 max(7 - 1, 2) 6

Result:

right = [6, 7, 4]

New DP

Column max(left,right) points New DP
0 6 3 9
1 7 1 8
2 6 1 7

Final:

dp = [9, 8, 7]

Answer:

9

Example 2

Input:

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

Initial:

dp = [1, 5]

Processing Row 1

Left sweep:

left = [1, 5]

Right sweep:

right = [4, 5]

New DP:

Column Best Previous Points New DP
0 4 2 6
1 5 3 8

Result:

dp = [6, 8]

Processing Row 2

Left sweep:

left = [6, 8]

Right sweep:

right = [7, 8]

New DP:

Column Best Previous Points New DP
0 7 4 11
1 8 2 10

Final answer:

11

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each row is processed with two linear sweeps
Space O(n) Only DP arrays for one row are stored

The algorithm processes every cell a constant number of times. For each row, we perform:

  • One left sweep
  • One right sweep
  • One DP construction pass

Each pass is linear in the number of columns.

No nested column-to-column transition loop exists, which avoids the quadratic bottleneck.

Test Cases

from typing import List

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        rows = len(points)
        cols = len(points[0])

        dp = [value for value in points[0]]

        for row in range(1, rows):
            left = [0] * cols
            right = [0] * cols

            left[0] = dp[0]
            for col in range(1, cols):
                left[col] = max(left[col - 1] - 1, dp[col])

            right[cols - 1] = dp[cols - 1]
            for col in range(cols - 2, -1, -1):
                right[col] = max(right[col + 1] - 1, dp[col])

            new_dp = [0] * cols

            for col in range(cols):
                new_dp[col] = points[row][col] + max(left[col], right[col])

            dp = new_dp

        return max(dp)

solver = Solution()

assert solver.maxPoints([[1, 2, 3], [1, 5, 1], [3, 1, 1]]) == 9  # Example 1
assert solver.maxPoints([[1, 5], [2, 3], [4, 2]]) == 11  # Example 2

assert solver.maxPoints([[5]]) == 5  # Single cell
assert solver.maxPoints([[1, 2, 3, 4]]) == 4  # Single row
assert solver.maxPoints([[1], [2], [3]]) == 6  # Single column

assert solver.maxPoints([[10, 1], [1, 10]]) == 19  # Movement penalty still worth paying
assert solver.maxPoints([[0, 0, 0], [0, 0, 0]]) == 0  # All zeros

assert solver.maxPoints([[100000]]) == 100000  # Maximum single value

assert solver.maxPoints([
    [1, 100, 1],
    [1, 1, 100],
    [100, 1, 1]
]) == 298  # Large zigzag movement

assert solver.maxPoints([
    [1, 2],
    [3, 4],
    [5, 6],
    [7, 8]
]) == 20  # Multiple rows accumulating values
Test Why
[[1,2,3],[1,5,1],[3,1,1]] Validates the first example
[[1,5],[2,3],[4,2]] Validates the second example
[[5]] Smallest possible input
[[1,2,3,4]] No movement penalties because only one row exists
[[1],[2],[3]] Single-column case where movement cost is always zero
[[10,1],[1,10]] Ensures algorithm correctly pays movement cost for better reward
[[0,0,0],[0,0,0]] All values zero
[[100000]] Maximum individual value
Zigzag high-value case Ensures long-distance transitions are handled correctly
Multi-row accumulation Verifies repeated DP transitions

Edge Cases

Single Row

If the matrix contains only one row, there are no movement penalties because no transitions occur between rows.

A buggy implementation might still attempt to perform transition logic or accidentally subtract costs. This implementation handles the case naturally because the DP array is initialized directly from the first row, and the transition loop never executes.

Single Column

When there is only one column, every selection must remain in column 0.

The movement penalty is always:

abs(0 - 0) = 0

A poorly written solution might still attempt unnecessary sweeps or incorrectly access neighboring indices. This implementation works correctly because both sweeps operate safely even when cols == 1.

Large Movement Penalties

Sometimes the best solution involves jumping across many columns because the destination value is extremely large.

For example:

[
    [1, 100],
    [100, 1]
]

The optimal path may intentionally pay a movement cost to gain a much larger reward.

A greedy solution that only minimizes movement would fail here. The DP formulation correctly evaluates all possible transitions and chooses the globally optimal path.

Very Large Inputs

Since m * n can reach 100000, quadratic solutions become infeasible.

A naive transition loop would time out on large wide matrices. The optimized two-sweep technique guarantees linear work per row, ensuring the algorithm scales efficiently within the problem limits.