Maximum Number of Points with Cost solution and explanation
Google
9 more videos on this problem
Maximum Number of Points with Cost - Leetcode 1937 - PythonNeetCodeIO · 15:15 · 22K views
Maximum Number of Points with Cost | Detailed Explanation | Leetcode 1937 | codestorywithMIKcodestorywithMIK · 47:38 · 15K views
Leetcode 1937 Maximum Number of Points with CostSandip Jana · 15:21 · 13K views
LeetCode 1937. Maximum Number of Points with CostHappy Coding · 18:00 · 13K views
1937. Maximum Number of Points with Cost. Leetcode.Hello World · 13:29 · 3K views
1937. Maximum Number of Points with Cost (Leetcode Medium)Programming Live with Larry · 29:52 · 1K views
1937. Maximum Number of Points with Cost, LeetCode, Javabaobaollf · 14:14 · 1K views
1937. Maximum Number of Points with Cost | Dynamic Programming | Leetcode Daily Challenge | JAVALeetQuest · 12:39 · 1K views
Daily Leetcode #1600: Aug 17, 2024 - 1937. Maximum Number of Points with CostProgramming Live with Larry · 21:21 · 654 views
Leetcode 1937 Maximum Number of Points with Cost|CPP|DP|Interview ProblemCodeMystique · 14:04 · 439 views
The problem
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:
xforx >= 0.-xforx < 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] <= 105
Approach overview
Problem Overview: You get an m x n matrix where selecting a cell in each row earns its value, but moving between columns costs |c1 - c2|. The goal is to maximize the total score while picking exactly one column per row.
Approach 1: Dynamic Programming with Direct Transition (O(m * n^2) time, O(n) space)
Define dp[j] as the maximum points achievable when selecting column j in the current row. For every row, compute the new value for each column by checking every column from the previous row: dp_new[j] = points[i][j] + max(dp[k] - |j - k|) for all k. This brute-force transition explicitly evaluates the movement penalty between columns. It is straightforward and clearly expresses the state transition, but the nested loop over columns makes it O(n^2) per row. This approach works for smaller matrices but becomes slow when n grows large.
Approach 2: Dynamic Programming with Two Pass Strategy (O(m * n) time, O(n) space)
The key observation: the transition dp[k] - |j - k| can be split into two directional cases. When k ≤ j, the cost becomes dp[k] + k - j. When k ≥ j, it becomes dp[k] - k + j. This allows you to precompute running maximum values while scanning the row from left-to-right and right-to-left. During the left pass, maintain best = max(best, dp[j] + j) and compute candidate scores. During the right pass, maintain best = max(best, dp[j] - j). Combining these passes gives the optimal transition for every column in linear time. This reduces each row update from quadratic to linear complexity.
Approach 3: Dynamic Programming with Optimized Transition State (O(m * n) time, O(n) space)
This implementation expresses the same optimization more compactly by propagating the best reachable values while iterating across the row. Instead of recomputing |j - k|, you carry forward the best previous score adjusted by movement cost. The technique relies on maintaining rolling maximums and updating them as the column index changes. It produces the same optimal DP state but with fewer temporary structures and cleaner transitions. Many competitive programmers prefer this formulation because the code is shorter while preserving the O(mn) runtime.
Recommended for interviews: Start by describing the direct dynamic programming transition to demonstrate you understand the state definition and movement penalty. Then optimize it using the two-pass trick. Interviewers expect the O(mn) DP solution because it shows you can transform a quadratic transition into a linear scan using prefix maximums. This pattern appears frequently in dynamic programming problems on grids and matrix traversal, especially when working with column-distance penalties inside array-based states.
Approach 1: Dynamic Programming with Two Pass Strategy
This 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.
def maxPoints(points):
m, n = len(points), len(points[0])
prevRow = points[0][:]
for i in range(1, m):
leftToRight = prevRow[:]
for j in range(1, n):
leftToRight[j] = max(leftToRight[j], leftToRight[j - 1] - 1)
rightToLeft = prevRow[:]
for j in range(n - 2, -1, -1):
rightToLeft[j] = max(rightToLeft[j], rightToLeft[j + 1] - 1)
for j in range(n):
leftToRight[j] = points[i][j] + max(leftToRight[j], rightToLeft[j])
prevRow = leftToRight
return max(prevRow)
points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]]
print("Maximum points:", maxPoints(points))import java.util.*;
public class MaxPoints {
public static int maxPoints(int[][] points) {
int m = points.length;
int n = points[0].length;
int[] prevRow = new int[n];
System.arraycopy(points[0], 0, prevRow, 0, n);
for (int i = 1; i < m; i++) {
int[] leftToRight = new int[n];
int[] rightToLeft = new int[n];
int[] currentRow = new int[n];
leftToRight[0] = prevRow[0];
for (int j = 1; j < n; j++) {
leftToRight[j] = Math.max(leftToRight[j - 1] - 1, prevRow[j]);
}
rightToLeft[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; j--) {
rightToLeft[j] = Math.max(rightToLeft[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; j++) {
currentRow[j] = points[i][j] + Math.max(leftToRight[j], rightToLeft[j]);
}
prevRow = currentRow;
}
return Arrays.stream(prevRow).max().getAsInt();
}
public static void main(String[] args) {
int[][] points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
System.out.println("Maximum points: " + maxPoints(points));
}
}#include <vector>
#include <algorithm>
using namespace std;
int maxPoints(vector<vector<int>>& points) {
int m = points.size();
int n = points[0].size();
vector<int> prevRow(n);
for (int j = 0; j < n; ++j) {
prevRow[j] = points[0][j];
}
for (int i = 1; i < m; ++i) {
vector<int> leftToRight(n), rightToLeft(n), currentRow(n);
leftToRight[0] = prevRow[0];
for (int j = 1; j < n; ++j) {
leftToRight[j] = max(leftToRight[j - 1] - 1, prevRow[j]);
}
rightToLeft[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; --j) {
rightToLeft[j] = max(rightToLeft[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; ++j) {
currentRow[j] = points[i][j] + max(leftToRight[j], rightToLeft[j]);
}
prevRow = currentRow;
}
return *max_element(prevRow.begin(), prevRow.end());
}
int main() {
vector<vector<int>> points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
int result = maxPoints(points);
printf("Maximum points: %d\n", result);
return 0;
}function maxPoints(points) {
const m = points.length;
const n = points[0].length;
let prevRow = [...points[0]];
for (let i = 1; i < m; i++) {
let leftToRight = [...prevRow];
for (let j = 1; j < n; j++) {
leftToRight[j] = Math.max(leftToRight[j], leftToRight[j - 1] - 1);
}
let rightToLeft = [...prevRow];
for (let j = n - 2; j >= 0; j--) {
rightToLeft[j] = Math.max(rightToLeft[j], rightToLeft[j + 1] - 1);
}
for (let j = 0; j < n; j++) {
leftToRight[j] = points[i][j] + Math.max(leftToRight[j], rightToLeft[j]);
}
prevRow = leftToRight;
}
return Math.max(...prevRow);
}
const points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]];
console.log('Maximum points:', maxPoints(points));#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return a > b ? a : b;
}
int maxPoints(int** points, int pointsSize, int* pointsColSize) {
int m = pointsSize;
int n = *pointsColSize;
int* prevRow = (int*)malloc(sizeof(int) * n);
for (int j = 0; j < n; j++) {
prevRow[j] = points[0][j];
}
for (int i = 1; i < m; i++) {
int* leftToRight = (int*)malloc(sizeof(int) * n);
int* rightToLeft = (int*)malloc(sizeof(int) * n);
int* currentRow = (int*)malloc(sizeof(int) * n);
leftToRight[0] = prevRow[0];
for (int j = 1; j < n; j++) {
leftToRight[j] = max(leftToRight[j - 1] - 1, prevRow[j]);
}
rightToLeft[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; j--) {
rightToLeft[j] = max(rightToLeft[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; j++) {
currentRow[j] = points[i][j] + max(leftToRight[j], rightToLeft[j]);
}
free(prevRow);
prevRow = currentRow;
free(leftToRight);
free(rightToLeft);
}
int maxPoints = 0;
for (int j = 0; j < n; j++) {
maxPoints = max(maxPoints, prevRow[j]);
}
free(prevRow);
return maxPoints;
}
int main() {
int points[][3] = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
int *columnSizes;
int pointsSize = 3;
columnSizes = (int *)malloc(pointsSize * sizeof(int));
for (int i = 0; i < pointsSize; i++) {
columnSizes[i] = 3;
}
int result = maxPoints((int **)points, pointsSize, columnSizes);
printf("Maximum points: %d\n", result);
free(columnSizes);
return 0;
}using System;
public class Solution {
public static int MaxPoints(int[][] points) {
int m = points.Length;
int n = points[0].Length;
int[] prevRow = new int[n];
Array.Copy(points[0], prevRow, n);
for (int i = 1; i < m; i++) {
int[] leftToRight = new int[n];
Array.Copy(prevRow, leftToRight, n);
for (int j = 1; j < n; j++) {
leftToRight[j] = Math.Max(leftToRight[j], leftToRight[j - 1] - 1);
}
int[] rightToLeft = new int[n];
Array.Copy(prevRow, rightToLeft, n);
for (int j = n - 2; j >= 0; j--) {
rightToLeft[j] = Math.Max(rightToLeft[j], rightToLeft[j + 1] - 1);
}
for (int j = 0; j < n; j++) {
leftToRight[j] = points[i][j] + Math.Max(leftToRight[j], rightToLeft[j]);
}
prevRow = leftToRight;
}
int maxPoints = 0;
foreach (var val in prevRow) {
if (val > maxPoints) maxPoints = val;
}
return maxPoints;
}
public static void Main() {
int[][] points = new int[][] {
new int[] {1, 2, 3},
new int[] {1, 5, 1},
new int[] {3, 1, 1}
};
Console.WriteLine("Maximum points: " + MaxPoints(points));
}
}Similar to the C-based implementations, this Python approach optimally determines maximum points by storing pre-computed row values. The leftToRight and rightToLeft adjustments ensure correct score after factoring in distance deductions.
Time Complexity: O(m * n), Space Complexity: O(n)
Approach 2: Dynamic Programming with Optimized Transition State
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.
def maxPoints(points):
m, n = len(points), len(points[0])
prevRow = points[0][:]
for i in range(1, m):
leftMax = [0] * n
rightMax = [0] * n
leftMax[0] = prevRow[0]
for j in range(1, n):
leftMax[j] = max(leftMax[j - 1] - 1, prevRow[j])
rightMax[n - 1] = prevRow[n - 1]
for j in range(n - 2, -1, -1):
rightMax[j] = max(rightMax[j + 1] - 1, prevRow[j])
for j in range(n):
prevRow[j] = points[i][j] + max(leftMax[j], rightMax[j])
return max(prevRow)
points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]]
print("Maximum points:", maxPoints(points))import java.util.*;
public class MaxPoints {
public static int maxPoints(int[][] points) {
int m = points.length;
int n = points[0].length;
int[] prevRow = Arrays.copyOf(points[0], n);
for (int i = 1; i < m; i++) {
int[] leftMax = new int[n];
int[] rightMax = new int[n];
int[] currentRow = new int[n];
leftMax[0] = prevRow[0];
for (int j = 1; j < n; j++) {
leftMax[j] = Math.max(leftMax[j - 1] - 1, prevRow[j]);
}
rightMax[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; j--) {
rightMax[j] = Math.max(rightMax[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; j++) {
currentRow[j] = points[i][j] + Math.max(leftMax[j], rightMax[j]);
}
prevRow = currentRow;
}
return Arrays.stream(prevRow).max().getAsInt();
}
public static void main(String[] args) {
int[][] points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
System.out.println("Maximum points: " + maxPoints(points));
}
}#include <vector>
#include <algorithm>
using namespace std;
int maxPoints(vector<vector<int>>& points) {
int m = points.size();
int n = points[0].size();
vector<int> prevRow(points[0].begin(), points[0].end());
for (int i = 1; i < m; ++i) {
vector<int> leftMax(n);
vector<int> rightMax(n);
vector<int> currentRow(n);
leftMax[0] = prevRow[0];
for (int j = 1; j < n; ++j) {
leftMax[j] = max(leftMax[j - 1] - 1, prevRow[j]);
}
rightMax[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; --j) {
rightMax[j] = max(rightMax[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; ++j) {
currentRow[j] = points[i][j] + max(leftMax[j], rightMax[j]);
}
prevRow = currentRow;
}
return *max_element(prevRow.begin(), prevRow.end());
}
int main() {
vector<vector<int>> points = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
int result = maxPoints(points);
printf("Maximum points: %d\n", result);
return 0;
}function maxPoints(points) {
const m = points.length;
const n = points[0].length;
let prevRow = [...points[0]];
for (let i = 1; i < m; i++) {
let leftMax = Array(n).fill(0);
let rightMax = Array(n).fill(0);
leftMax[0] = prevRow[0];
for (let j = 1; j < n; j++) {
leftMax[j] = Math.max(leftMax[j - 1] - 1, prevRow[j]);
}
rightMax[n - 1] = prevRow[n - 1];
for (let j = n - 2; j >= 0; j--) {
rightMax[j] = Math.max(rightMax[j + 1] - 1, prevRow[j]);
}
for (let j = 0; j < n; j++) {
prevRow[j] = points[i][j] + Math.max(leftMax[j], rightMax[j]);
}
}
return Math.max(...prevRow);
}
const points = [[1, 2, 3], [1, 5, 1], [3, 1, 1]];
console.log('Maximum points:', maxPoints(points));#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return a > b ? a : b;
}
int maxPoints(int** points, int pointsSize, int* pointsColSize) {
int m = pointsSize;
int n = *pointsColSize;
int* prevRow = (int*)malloc(sizeof(int) * n);
for (int j = 0; j < n; j++) {
prevRow[j] = points[0][j];
}
for (int i = 1; i < m; i++) {
int* leftMax = (int*)malloc(sizeof(int) * n);
int* rightMax = (int*)malloc(sizeof(int) * n);
int* currentRow = (int*)malloc(sizeof(int) * n);
leftMax[0] = prevRow[0];
for (int j = 1; j < n; j++) {
leftMax[j] = max(leftMax[j - 1] - 1, prevRow[j]);
}
rightMax[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; j--) {
rightMax[j] = max(rightMax[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; j++) {
currentRow[j] = points[i][j] + max(leftMax[j], rightMax[j]);
}
free(prevRow);
prevRow = currentRow;
free(leftMax);
free(rightMax);
}
int result = 0;
for (int j = 0; j < n; j++) {
result = max(result, prevRow[j]);
}
free(prevRow);
return result;
}
int main() {
int points[][3] = {{1, 2, 3}, {1, 5, 1}, {3, 1, 1}};
int *columnSizes;
int pointsSize = 3;
columnSizes = (int *)malloc(pointsSize * sizeof(int));
for (int i = 0; i < pointsSize; i++) {
columnSizes[i] = 3;
}
int result = maxPoints((int **)points, pointsSize, columnSizes);
printf("Maximum points: %d\n", result);
free(columnSizes);
return 0;
}using System;
public class Solution {
public static int MaxPoints(int[][] points) {
int m = points.Length;
int n = points[0].Length;
int[] prevRow = new int[n];
Array.Copy(points[0], prevRow, n);
for (int i = 1; i < m; i++) {
int[] leftMax = new int[n];
int[] rightMax = new int[n];
leftMax[0] = prevRow[0];
for (int j = 1; j < n; j++) {
leftMax[j] = Math.Max(leftMax[j - 1] - 1, prevRow[j]);
}
rightMax[n - 1] = prevRow[n - 1];
for (int j = n - 2; j >= 0; j--) {
rightMax[j] = Math.Max(rightMax[j + 1] - 1, prevRow[j]);
}
for (int j = 0; j < n; j++) {
prevRow[j] = points[i][j] + Math.Max(leftMax[j], rightMax[j]);
}
}
int maxPoints = 0;
foreach (var val in prevRow) {
if (val > maxPoints) maxPoints = val;
}
return maxPoints;
}
public static void Main() {
int[][] points = new int[][] {
new int[] {1, 2, 3},
new int[] {1, 5, 1},
new int[] {3, 1, 1}
};
Console.WriteLine("Maximum points: " + MaxPoints(points));
}
}Utilizing Python's dynamic array handling, this method builds the processing around prefix and suffix maxima which collaborate to deduce upon beneficial transitions and maximize the points efficiently.
Time Complexity: O(m * n). Space Complexity: O(n) for handling dynamic list allocations.
Approach 3: Default Approach
function maxPoints(points: number[][]): number {
const n = points[0].length;
const f: number[] = new Array(n).fill(0);
for (const p of points) {
const g: number[] = new Array(n).fill(0);
let lmx = -Infinity;
let rmx = -Infinity;
for (let j = 0; j < n; ++j) {
lmx = Math.max(lmx, f[j] + j);
g[j] = Math.max(g[j], p[j] + lmx - j);
}
for (let j = n - 1; ~j; --j) {
rmx = Math.max(rmx, f[j] - j);
g[j] = Math.max(g[j], p[j] + rmx + j);
}
f.splice(0, n, ...g);
}
return Math.max(...f);
}func maxPoints(points [][]int) int64 {
n := len(points[0])
const inf int64 = 1e18
f := make([]int64, n)
for _, p := range points {
g := make([]int64, n)
lmx, rmx := -inf, -inf
for j := range p {
lmx = max(lmx, f[j]+int64(j))
g[j] = max(g[j], int64(p[j])+lmx-int64(j))
}
for j := n - 1; j >= 0; j-- {
rmx = max(rmx, f[j]-int64(j))
g[j] = max(g[j], int64(p[j])+rmx+int64(j))
}
f = g
}
return slices.Max(f)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with Two Pass Strategy | Time Complexity: O(m * n), Space Complexity: O(n) |
| Dynamic Programming with Optimized Transition State | Time Complexity: O(m * n). Space Complexity: O(n) for handling dynamic list allocations. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Direct Transition | O(m * n^2) | O(n) | Useful for understanding the DP state and transition before optimizing |
| Dynamic Programming with Two Pass Strategy | O(m * n) | O(n) | Optimal solution for large matrices and typical interview expectations |
| DP with Optimized Transition State | O(m * n) | O(n) | Cleaner implementation of the optimized DP using rolling maximums |
Frequently asked questions
Is Maximum Number of Points with Cost easy or hard?
Maximum Number of Points with Cost is generally considered a medium-level problem on LeetCode. The challenge lies in recognizing how to optimize the DP transition from O(n^2) to O(n) per row using prefix maximum techniques.
Maximum Number of Points with Cost Python/Java solution
Python and Java implementations both follow the same DP pattern. Maintain an array representing the best score for each column from the previous row, then compute the next row using left and right scans to apply the column movement penalty efficiently.
How to solve Maximum Number of Points with Cost in O(n)?
Process the matrix row by row using dynamic programming. For each row, perform a left-to-right pass maintaining the best value of dp[j] + j and a right-to-left pass maintaining dp[j] - j. These running maximums allow computing the best transition for every column in constant time, making each row O(n).
What is the best approach for Maximum Number of Points with Cost?
The best approach uses dynamic programming with a two-pass optimization. Instead of evaluating every previous column for each state, the algorithm scans left-to-right and right-to-left while maintaining running maximums. This converts the transition dp[k] - |j-k| into linear scans, reducing complexity to O(m*n) time and O(n) space.
Is Maximum Number of Points with Cost asked at Google/Amazon/Meta?
Matrix dynamic programming problems with transition penalties frequently appear in interviews at companies like Amazon, Google, and Meta. Variants that require optimizing DP transitions using prefix maximums or directional scans are common in senior-level coding interviews.
What data structure is used in Maximum Number of Points with Cost?
The solution mainly uses arrays to store dynamic programming states for each column. The algorithm iterates through the matrix rows and updates a 1D DP array while maintaining running maximum values during left and right passes.
What is the time complexity of Maximum Number of Points with Cost?
The optimal solution runs in O(m*n) time where m is the number of rows and n is the number of columns. Each row is processed with two linear passes to compute the best transitions. Space complexity is O(n) because only the previous row's DP values are stored.