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.lengthn == points[r].length1 <= m, n <= 1051 <= m * n <= 1050 <= points[r][c] <= 105This approach uses dynamic programming where we keep track of the maximum points obtainable for each cell using two linear passes per row: one from left to right and the other from right to left. This ensures that we account for the cost of moving between rows efficiently.
The solution uses two arrays, leftToRight and rightToLeft, to keep track of the running maximum of points at each cell considering the point loss moving horizontally. The maximum value for each cell in the current row is calculated by combining the respective running maximum from leftToRight and rightToLeft plus the points from the current cell.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n) as we iterate through the cells twice per row. Space Complexity: O(n) due to the auxiliary arrays used.
This approach uses a dynamic array to store optimal points value and computes it via a prefix and suffix maximum accumulations, thereby reducing the transition complexity while still making sure every cell's deduction is feasible within two linear passes.
This variation keeps the dynamic arrays leftMax and rightMax for efficient transitions between rows to directly adjust the prefix-suffix maximum pairs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n). Space Complexity: O(n), reducing allocation per row iteration.
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Pass Strategy | Time Complexity: O(m * n) as we iterate through the cells twice per row. Space Complexity: O(n) due to the auxiliary arrays used. |
| Dynamic Programming with Optimized Transition State | Time Complexity: O(m * n). Space Complexity: O(n), reducing allocation per row iteration. |
Leetcode 149 - Maximum Points on a Line - Python • NeetCodeIO • 25,713 views views
Watch 9 more video solutions →Practice Maximum Number of Points with Cost with our built-in code editor and test cases.
Practice on FleetCode