{x}
blog image

Maximum Number of Points with Cost

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, c1) and (r + 1, c2) will subtract abs(c1 - c2) 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 <= 105
  • 1 <= m * n <= 105
  • 0 <= points[r][c] <= 105

Solution Explanation:

This problem can be efficiently solved using dynamic programming. The core idea is to iterate through the rows of the points matrix and maintain, for each column, the maximum score achievable up to the current row. We'll use two arrays, f and g, for optimization. f will store the maximum points achieved up to the previous row, and g will store the maximum points achievable up to the current row.

Algorithm:

  1. Initialization: Initialize f with the points from the first row of the points matrix. This represents the maximum score achievable after considering only the first row.

  2. Iteration: Iterate through the remaining rows of the points matrix (rows 1 to m-1). For each row:

    • Initialize g with zeros. This array will store the maximum scores for each column in the current row.

    • Left-to-right scan: Iterate through the columns (0 to n-1). For each column j, compute the maximum score achievable by considering all previous columns (0 to j-1). We do this by using a left maximum (lmx), storing the maximum value of f[k] + k up to column j -1. The +k is because the cost decreases linearly when moving left from j. This will be added to the current point p[j] and then -j will be used to account for the cost for the transition from previous row to the current row.

    • Right-to-left scan: Iterate through the columns in reverse order (n-1 to 0). Similarly, we compute the maximum score achievable by considering all subsequent columns (j+1 to n-1). We use a right maximum (rmx), storing the maximum value of f[k] - k from column j+1 to the end. The -k is because the cost increases linearly when moving right from j. This will be added to the current point p[j] and then +j will be used to account for the cost for the transition from previous row to the current row.

    • Update g: For each column j, g[j] is the maximum of the scores calculated in the left-to-right and right-to-left scans. This ensures we consider all possible transitions from the previous row.

    • Update f: Assign g to f to prepare for the next row's calculation.

  3. Final Result: After processing all rows, the maximum value in f is the maximum number of points achievable.

Time Complexity: The algorithm iterates through the rows and columns of the matrix once each, resulting in a time complexity of O(m*n), where 'm' is the number of rows and 'n' is the number of columns.

Space Complexity: The algorithm uses two arrays, f and g, of size 'n', resulting in a space complexity of O(n).

Code Examples (Python):

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        f = points[0][:]  # Initialize f with the first row
 
        for i in range(1, m):
            g = [0] * n
            lmx = -float('inf')
            for j in range(n):
                lmx = max(lmx, f[j] + j)  #Left to right max
                g[j] = max(g[j], points[i][j] + lmx - j)
 
            rmx = -float('inf')
            for j in range(n - 1, -1, -1): # Right to left max
                rmx = max(rmx, f[j] - j)
                g[j] = max(g[j], points[i][j] + rmx + j)
            f = g #update f for next iteration
 
        return max(f)

The code in other languages (Java, C++, Go, TypeScript) follows the same logic and algorithm as described above, with minor syntactic differences. They all achieve the same O(m*n) time complexity and O(n) space complexity.