Maximum Number of Points with Cost

Med

#1767Time: O(m * n^2) - We iterate through each cell of the `m x n` matrix. For each cell `(i, j)`, we iterate through all `n` columns of the previous row to find the optimal path. This results in three nested loops.Space: O(m * n) - We use a 2D DP table of size `m x n`. This can be optimized to `O(n)` by noticing that for row `i`, we only need the results from row `i-1`.

Patterns

Dynamic Programming

Data structures

Array Matrix

Prompt

You are given an m x n integer matrix points (0-indexed). Starting with 0 points, you want to maximize the number of points you can get from the matrix.

To gain points, you must pick one cell in each row. Picking the cell at coordinates (r, c) will add points[r][c] to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows r and r + 1 (where 0 <= r < m - 1), picking cells at coordinates (r, c₁) and (r + 1, c₂) will subtract abs(c₁ - c₂) from your score.

Return the maximum number of points you can achieve.

abs(x) is defined as:

x for x >= 0.
-x for x < 0.

Example 1:

Input: points = [[1,2,3],[1,5,1],[3,1,1]]
Output: 9
Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).
You add 3 + 5 + 3 = 11 to your score.
However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
Your final score is 11 - 2 = 9.

Example 2:

Input: points = [[1,5],[2,3],[4,2]]
Output: 11
Explanation:
The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
You add 5 + 3 + 4 = 12 to your score.
However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
Your final score is 12 - 1 = 11.

Constraints:

m == points.length
n == points[r].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
0 <= points[r][c] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define dp[i][j] as the maximum score we can obtain by picking cells up to row i, with the cell in row i being at column j.

The base case is the first row, where the score is simply the value of the cell, as there's no preceding row to calculate a penalty from. For any other cell (i, j), we calculate its maximum possible score by considering all possible cells (i-1, k) in the previous row. We take the maximum score from the previous row, dp[i-1][k], add the current cell's points, points[i][j], and subtract the penalty abs(j - k). We iterate through all possible k to find the maximum achievable score for dp[i][j]. The final answer is the maximum value in the last row of our DP table.

Algorithm

Define a 2D DP array dp[m][n], where dp[i][j] stores the maximum score achievable up to row i, ending at column j.
Base Case: For the first row (i=0), there is no previous row, so the score is just the points in that cell. Initialize dp[0][j] = points[0][j] for all j from 0 to n-1.
Transition: For each subsequent row i (from 1 to m-1) and each column j (from 0 to n-1), calculate dp[i][j].
- To find the score for dp[i][j], we must have come from some cell (i-1, k) in the previous row.
- The score contribution from the previous rows ending at (i-1, k) is dp[i-1][k].
- The cost of moving from column k to j is abs(j - k).
- So, the total score is dp[i-1][k] + points[i][j] - abs(j - k).
- We need to maximize this over all possible previous columns k.
- The recurrence relation is: dp[i][j] = points[i][j] + max(dp[i-1][k] - abs(j - k)) for 0 <= k < n.
Final Answer: After filling the entire dp table, the maximum score is the maximum value in the last row, max(dp[m-1][j]) for 0 <= j < n.

Walkthrough

The core of this method is a straightforward implementation of the dynamic programming recurrence. We build a dp table of the same dimensions as the points matrix.

State: dp[i][j] represents the maximum points accumulated up to row i, with the path ending at column j.
Base Case: The first row of the dp table is initialized directly from the input matrix, as there are no prior rows to consider for penalties: dp[0][j] = points[0][j].
Recurrence: For every cell (i, j) where i > 0, we compute dp[i][j] by iterating through all possible columns k in the previous row i-1. For each k, we calculate a potential score dp[i-1][k] - abs(j - k) and find the maximum among them. This maximum value is then added to points[i][j] to get dp[i][j]. This requires a nested loop inside the main loops that iterate through rows and columns.

1public long maxPoints(int[][] points) {2    int m = points.length;3    int n = points[0].length;4 5    long[][] dp = new long[m][n];6 7    // Initialize the first row8    for (int j = 0; j < n; j++) {9        dp[0][j] = points[0][j];10    }11 12    // Fill the rest of the DP table13    for (int i = 1; i < m; i++) {14        for (int j = 0; j < n; j++) {15            long maxPrev = 0;16            for (int k = 0; k < n; k++) {17                maxPrev = Math.max(maxPrev, dp[i - 1][k] - Math.abs(j - k));18            }19            dp[i][j] = points[i][j] + maxPrev;20        }21    }22 23    // Find the maximum score in the last row24    long maxScore = 0;25    for (int j = 0; j < n; j++) {26        maxScore = Math.max(maxScore, dp[m - 1][j]);27    }28 29    return maxScore;30}

Note: The space complexity can be optimized to O(n) by only storing the DP values for the previous row, but the time complexity remains the bottleneck.

Complexity

Time

O(m * n^2) - We iterate through each cell of the `m x n` matrix. For each cell `(i, j)`, we iterate through all `n` columns of the previous row to find the optimal path. This results in three nested loops.

Space

O(m * n) - We use a 2D DP table of size `m x n`. This can be optimized to `O(n)` by noticing that for row `i`, we only need the results from row `i-1`.

Trade-offs

Pros

It is a direct translation of the problem statement into a DP recurrence, making it easy to understand and implement.

Cons

The time complexity of O(m * n^2) is too slow for the given constraints and will result in a 'Time Limit Exceeded' error on most platforms.

The O(m * n^2) complexity of the brute-force approach comes from the inner loop that recalculates the maximum previous score for every cell. We can optimize this by observing that the calculation max_{k}(dp[k] - abs(j-k)) can be broken down. The abs(j-k) term depends on whether k <= j or k > j. This structure allows us to precompute the necessary maximums for each row in linear time.

For each row, we can use two passes. A left-to-right pass calculates the maximum score coming from a previous cell k where k <= j. A right-to-left pass does the same for k >= j. By combining the results of these two passes, we can find the optimal previous cell for each current cell j in O(1) time. This reduces the complexity of processing each row from O(n^2) to O(n), leading to an overall time complexity of O(m * n).

Algorithm

Since computing row i only depends on row i-1, we can optimize space by using a 1D array, dp, of size n to store the results of the previous row.
Initialize dp with the values from the first row of points.
Iterate through the rows of points from i = 1 to m-1.
For each row i, we calculate the new dp values. The key is to optimize the calculation of max_{k}(dp[k] - abs(j-k)). This can be done in two passes for each row.
Pass 1 (Left-to-Right):
- Create a temporary array left of size n.
- left[j] will store max_{k<=j}(dp[k] - (j-k)). This can be calculated with the recurrence left[j] = max(left[j-1] - 1, dp[j]).
- Initialize left[0] = dp[0] and iterate from j=1 to n-1.
Pass 2 (Right-to-Left):
- Create a temporary array right of size n.
- right[j] will store max_{k>=j}(dp[k] - (k-j)). This can be calculated with the recurrence right[j] = max(right[j+1] - 1, dp[j]).
- Initialize right[n-1] = dp[n-1] and iterate from j=n-2 down to 0.
Update DP array:
- For each column j, the maximum value from the previous row is max(left[j], right[j]).
- Update dp[j] = points[i][j] + max(left[j], right[j]).
After iterating through all rows, the maximum value in the final dp array is the answer.

Walkthrough

This optimized DP approach avoids the costly inner loop by using a more clever way to compute the maximum score from the previous row. We maintain a 1D array, dp, representing the maximum scores for the most recently processed row.

For each new row i, we want to compute a new dp array. The value for dp[j] will be points[i][j] + max_prev_score, where max_prev_score = max_{0 <= k < n} (old_dp[k] - abs(j - k)).

We can find max_prev_score efficiently. Let's analyze the term old_dp[k] - abs(j-k):

If k <= j, it's old_dp[k] - (j-k) = old_dp[k] + k - j.
If k > j, it's old_dp[k] - (k-j) = old_dp[k] - k + j.

So, max_prev_score is max( max_{k<=j}(old_dp[k]+k) - j, max_{k>j}(old_dp[k]-k) + j ).

Instead of recomputing these maximums every time, we can use two passes over the old_dp array:

A left-to-right pass to compute max_{k<=j}(old_dp[k] - (j-k)) for all j.
A right-to-left pass to compute max_{k>=j}(old_dp[k] - (k-j)) for all j.

Let left[j] = max_{k<=j}(old_dp[k] - (j-k)) and right[j] = max_{k>=j}(old_dp[k] - (k-j)). These can be computed via simple recurrences:

left[j] = max(left[j-1] - 1, old_dp[j])
right[j] = max(right[j+1] - 1, old_dp[j])

After computing the left and right arrays, the new dp[j] is points[i][j] + max(left[j], right[j]). Since the total score can exceed the capacity of a 32-bit integer, we use long for our DP arrays.

1public long maxPoints(int[][] points) {2    int m = points.length;3    int n = points[0].length;4 5    long[] dp = new long[n];6    for (int j = 0; j < n; j++) {7        dp[j] = points[0][j];8    }9 10    for (int i = 1; i < m; i++) {11        long[] left = new long[n];12        left[0] = dp[0];13        for (int j = 1; j < n; j++) {14            left[j] = Math.max(left[j - 1] - 1, dp[j]);15        }16 17        long[] right = new long[n];18        right[n - 1] = dp[n - 1];19        for (int j = n - 2; j >= 0; j--) {20            right[j] = Math.max(right[j + 1] - 1, dp[j]);21        }22 23        for (int j = 0; j < n; j++) {24            dp[j] = points[i][j] + Math.max(left[j], right[j]);25        }26    }27 28    long maxScore = 0;29    for (long score : dp) {30        maxScore = Math.max(maxScore, score);31    }32 33    return maxScore;34}

Complexity

Time

O(m * n) - For each of the `m` rows, we perform a constant number of passes (three) over the `n` columns. This results in a linear time complexity with respect to the size of the input matrix.

Space

O(n) - We use a 1D `dp` array of size `n` to store the results for the current row, and two additional arrays `left` and `right` of size `n` for the intermediate calculations.

Trade-offs

Pros

Highly efficient with a time complexity of O(m * n), which passes the given constraints.
Space-efficient, using only O(n) extra space.

Cons

The logic is more complex than the brute-force approach, involving multiple passes and auxiliary arrays for each row's computation.

Solutions

Solution

1class Solution {2public3  long maxPoints(int[][] points) {4    int n = points[0].length;5    long[] f = new long[n];6    final long inf = 1L << 60;7    for (int[] p : points) {8      long[] g = new long[n];9      long lmx = -inf, rmx = -inf;10      for (int j = 0; j < n; ++j) {11        lmx = Math.max(lmx, f[j] + j);12        g[j] = Math.max(g[j], p[j] + lmx - j);13      }14      for (int j = n - 1; j >= 0; --j) {15        rmx = Math.max(rmx, f[j] - j);16        g[j] = Math.max(g[j], p[j] + rmx + j);17      }18      f = g;19    }20    long ans = 0;21    for (long x : f) {22      ans = Math.max(ans, x);23    }24    return ans;25  }26}

1class Solution {2public:3  long long maxPoints(vector<vector<int>> &points) {4    using ll = long long;5    int n = points[0].size();6    vector<ll> f(n);7    const ll inf = 1e18;8    for (auto &p : points) {9      vector<ll> g(n);10      ll lmx = -inf, rmx = -inf;11      for (int j = 0; j < n; ++j) {12        lmx = max(lmx, f[j] + j);13        g[j] = max(g[j], p[j] + lmx - j);14      }15      for (int j = n - 1; ~j; --j) {16        rmx = max(rmx, f[j] - j);17        g[j] = max(g[j], p[j] + rmx + j);18      }19      f = move(g);20    }21    return *max_element(f.begin(), f.end());22  }23};

1class Solution:2    def maxPoints(self, points: List[List[int]]) -> int: n = len(points[0]) f = points[0][:] for p in points[1:]: g = [0] * n lmx = - inf for j in range(n): lmx = max(lmx, f[j] + j) g[j] = max(g[j], p[j] + lmx - j) 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) f = g return max(f)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem