Maximum Number of Points with Cost: Left-Right DP Sweep

June 5, 20265 min read

leetcodeproblemmediumarraysdynamic-programming

You are given an m x n matrix called points. You pick exactly one cell from each row and collect its value. The catch: if you pick column c in one row and column c' in the next, you pay a penalty of abs(c - c'). Your goal is to maximize the total points after all penalties.

This is LeetCode 1937: Maximum Number of Points with Cost, a medium problem that looks like a standard row-by-row DP until you realize the naive transition is O(n^2) per row. The key insight is a left-right sweep trick that brings each transition down to O(n), giving you O(m * n) overall.

Pick one cell per row. Collect the cell value, but pay abs(col_prev - col_curr) as a penalty. The green path scores 10.

The approach: left-right sweep optimization

The naive DP is clear enough. Let dp[j] be the maximum score achievable ending at column j in the current row. To compute the next row, you would set new_dp[j] = max over all i of (dp[i] - abs(i - j)) + points[row][j]. That inner max scans all n columns for each of the n cells, giving O(n^2) per row and O(m * n^2) total. For the given constraints (up to 10^5 cells), that is too slow.

The optimization splits the abs(i - j) into two cases. When i is to the left of j (so i <= j), the penalty is j - i, and you want max(dp[i] + i) for all i <= j. When i is to the right (i >= j), the penalty is i - j, and you want max(dp[i] - i) for all i >= j. Each of these running maximums can be computed with a single linear sweep.

The left sweep scans from column 0 to column n-1, maintaining a running maximum that decreases by 1 at each step (because moving one column further costs 1 more). The right sweep does the same from column n-1 down to 0. For each column j, the best transition value is max(left[j], right[j]), and you just add points[row][j].

The left-right sweep pattern works any time you have a DP transition of the form dp[j] = max(prev[i] - cost(i, j)) where the cost grows linearly with distance. You replace one O(n) scan per cell with two O(n) sweeps for the entire row.

The code

def maxPoints(points):
    m, n = len(points), len(points[0])
    dp = list(points[0])

    for r in range(1, m):
        left = [0] * n
        left[0] = dp[0]
        for j in range(1, n):
            left[j] = max(dp[j], left[j - 1] - 1)

        right = [0] * n
        right[n - 1] = dp[n - 1]
        for j in range(n - 2, -1, -1):
            right[j] = max(dp[j], right[j + 1] - 1)

        for j in range(n):
            dp[j] = max(left[j], right[j]) + points[r][j]

    return max(dp)

Initialize dp as a copy of the first row. No penalties apply to the starting row.
For each subsequent row, build the left array by scanning left to right. left[j] is the best value you can carry from any column at or to the left of j, accounting for the distance penalty.
Build the right array by scanning right to left. right[j] is the best value from any column at or to the right of j.
Combine into the new dp: for each column j, take max(left[j], right[j]) and add the current row's points.
Return the maximum value in dp after processing all rows.

Practice DP optimization patterns

Visual walkthrough

Here is a step-by-step trace of the algorithm on points = [[1,2,3,1],[1,5,1,1],[4,1,1,2]]. The answer is 10, achieved by picking column 2, then column 1, then column 0.

Step 1: Initialize DP with the first row.

No penalty for the first row. dp starts as a copy of points[0].

Step 2: Naive transition is O(n^2). For each cell j, try all cells i in the previous row.

new_dp[j] = max over all i of (dp[i] - abs(i - j)) + points[1][j]. Checking every i for every j costs O(n^2) per row.

Step 3: Left sweep on dp = [1, 2, 3, 1]. Scan left to right, decrementing by 1 each step.

left[0] = 1. left[1] = max(dp[1], left[0]-1) = max(2, 0) = 2. left[2] = max(3, 1) = 3. left[3] = max(1, 2) = 2. Each left[j] captures the best dp[i] - (j - i) from the left side.

Step 4: Right sweep on dp = [1, 2, 3, 1]. Scan right to left, decrementing by 1 each step.

right[3] = 1. right[2] = max(3, 0) = 3. right[1] = max(2, 2) = 2. right[0] = max(1, 1) = 1. Each right[j] captures the best dp[i] - (i - j) from the right side.

Step 5: Combine. new_dp[j] = max(left[j], right[j]) + points[1][j].

new_dp = [max(1,1)+1, max(2,2)+5, max(3,3)+1, max(2,1)+1] = [2, 7, 4, 3]. One full row transition in O(n).

Step 6: Repeat for row 2. Sweep dp = [2, 7, 4, 3], then add points[2] = [4, 1, 1, 2].

left = [2,7,6,5], right = [6,7,4,3]. final dp = [max(2,6)+4, max(7,7)+1, max(6,4)+1, max(5,3)+2] = [10, 8, 7, 7]. Answer = max(10, 8, 7, 7) = 10.

Notice how the left and right sweeps each take O(n) time, and combining them is another O(n). Three linear passes replace the O(n^2) inner loop of the naive approach.

Complexity analysis

Metric	Value
Time	O(m * n) where m is rows and n is columns
Space	O(n) for the DP and sweep arrays

Each row transition requires three O(n) passes: one for the left sweep, one for the right sweep, and one to combine them. With m rows, the total work is O(m * n). The dp, left, and right arrays each hold n values, so space is O(n).

Drill dynamic programming with spaced repetition

Building blocks

1. Left-right sweep for linear-cost DP transitions

When a DP transition involves a penalty that grows linearly with distance (like abs(i - j)), you can decompose it into a left sweep and a right sweep. Each sweep maintains a running maximum that decays by 1 per step, capturing the best source value minus the accumulated cost.

Candy (LeetCode 135): two passes ensure each child with a higher rating than a neighbor gets more candies. The left pass handles the left constraint, the right pass handles the right constraint.
Trapping Rain Water (LeetCode 42): a left sweep finds the running max height from the left, a right sweep finds the running max from the right. The min of the two at each position gives the water level.

2. Row-by-row DP with space optimization

Instead of storing a full 2D DP table, you keep only the previous row and update it in place. This reduces space from O(m * n) to O(n) and is a standard technique for grid DP problems.

Minimum Path Sum (LeetCode 64): compute row by row, carrying forward the minimum cost to reach each cell.
Unique Paths (LeetCode 62): count paths row by row, updating a single array using the values from the same row (left neighbor) and the previous row (above neighbor).

Edge cases

Single row: when m = 1, there are no transitions and no penalties. The answer is simply the maximum value in the single row.

Single column: when n = 1, there is no column switching. The penalties are always 0, and the answer is the sum of all values in the column.

All values equal: every column in every row has the same value. Staying in the same column avoids all penalties, so the answer is m * value.

Large penalty dominates: when values are small but the grid is wide, switching columns far apart can wipe out any gain. The sweep naturally handles this because the running maximum decays with distance.

From understanding to recall

You have seen how the left-right sweep turns an O(n^2) DP transition into O(n). The idea is elegant, but the implementation has details that are easy to fumble: initializing the sweep arrays correctly, decrementing by 1 at each step, and combining with max(left[j], right[j]) before adding the current row's points. Under interview pressure, those details matter.

Spaced repetition is the most effective way to lock in these details. You write the solution from scratch, check it, and come back at increasing intervals. After a few rounds, the sweep pattern is automatic. You see "linear penalty DP" and your hands write the left sweep, right sweep, and combine step without hesitation.

Try CodeBricks free

Best Time to Buy and Sell Stock - Another DP problem where tracking a running optimum avoids nested loops
Climbing Stairs - A foundational DP problem that introduces the row-by-row transition pattern