Maximum Number of Points with Cost

How it works

We can reduce memory usage by combining the left and right sweeps into a single pass. Instead of storing separate left and right arrays, we build the left maximum in a cur array during the left-to-right pass. Then, during the right-to-left pass, we update cur[c] by taking the max of the current left value and the running right maximum, adding the cell value as we go.

This avoids allocating a separate right array, reducing the constant factor in space usage.

Steps

1. Initialize prev with the first row's values.
2. For each subsequent row:
   • Create a cur array and build left maximums by iterating left-to-right: cur[c] = max(prev[c], cur[c-1] - 1).
   • Iterate right-to-left, tracking rightMax. For each column, update cur[c] = max(cur[c], rightMax) + points[r][c], then update rightMax = max(prev[c], rightMax - 1).
   • Handle the last column separately since it was not processed in the right-to-left loop.
   • Set prev = cur for the next iteration.
3. Return the maximum value in prev.

Complexity

• Time complexity: O(m * n)
• Space complexity: O(n)

Where m is the number of rows, and n is the number of columns.

Things to watch for

Integer Overflow

With grid dimensions up to 10^5 and cell values up to 10^5, the maximum total points can exceed the 32-bit integer limit. Using int instead of long (or equivalent 64-bit type) will cause overflow and incorrect results.

Missing One Direction in Prefix Maximum

The optimized solution requires computing both left-to-right and right-to-left prefix maximums. Forgetting one direction or incorrectly combining them will miss optimal transitions from certain columns, leading to suboptimal answers.

Off-by-One in Penalty Propagation

When propagating the prefix maximum, the penalty decreases by 1 for each column of distance. A common error is applying the penalty incorrectly, such as subtracting the penalty before comparing or not decrementing for each step. The update should be left[c] = max(dp[c], left[c-1] - 1), not left[c] = max(dp[c] - 1, left[c-1]).

from typing import List

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ROWS, COLS = len(points), len(points[0])
        prev = points[0]

        for r in range(1, ROWS):
            cur = [0] * COLS
            cur[0] = prev[0]
            for c in range(1, COLS):
                cur[c] = max(prev[c], cur[c - 1] - 1)

            rightMax = prev[COLS - 1]
            for c in range(COLS - 2, -1 , -1):
                rightMax = max(prev[c], rightMax - 1)
                cur[c] = max(cur[c], rightMax) + points[r][c]

            cur[COLS - 1] += points[r][COLS - 1]
            prev = cur

        return max(prev)

class Solution {
public:
    long long maxPoints(vector<vector<int>>& points) {
        int rows = points.size(), cols = points[0].size();
        vector<long long> prev(cols);
        for (int c = 0; c < cols; c++) prev[c] = points[0][c];

        for (int r = 1; r < rows; r++) {
            vector<long long> cur(cols);
            cur[0] = prev[0];
            for (int c = 1; c < cols; c++)
                cur[c] = max(prev[c], cur[c - 1] - 1);

            long long rightMax = prev[cols - 1];
            for (int c = cols - 2; c >= 0; c--) {
                rightMax = max(prev[c], rightMax - 1);
                cur[c] = max(cur[c], rightMax) + points[r][c];
            }
            cur[cols - 1] += points[r][cols - 1];
            prev = cur;
        }
        return *max_element(prev.begin(), prev.end());
    }
};