1937. Maximum Number of Points with Cost
Problem Description
The problem presents a scenario where we are working with an m x n
integer matrix called points
. The goal is to maximize our total points by selecting one cell from each row of the matrix. When we select a cell at (r, c), we add the points value from points[r][c]
to our score.
However, there's a catch: we must also account for the positional difference from the cells we select in adjacent rows. Specifically, if we choose a cell at (r, c1) and then a cell at (r+1, c2) in the next row, our score is reduced by abs(c1 - c2)
, which represents the absolute difference between the column indices of the selected cells in consecutive rows.
The challenge is to figure out which cells to choose from each row to end up with the highest possible score after accounting for both the points from each cell and the penalties incurred for the distance between cells in adjacent rows.
Intuition
To solve this problem efficiently, dynamic programming can be used to avoid redundant calculations while considering each possible choice. The intuition behind the solution lies in the observation that the penalty for moving horizontally between columns can affect our choice of picking the optimal cell. We need to balance the points gained against the potential loss from moving too far horizontally in the next row.
The solution keeps track of an array f
, which represents the best score we can achieve up to the current row for every possible column choice. The solution iterates over each row of the points
matrix, calculates the best scores for choosing each column in that row, and prepares the array f
for the next row.
There are two main parts in the iteration over each row:
-
Traverse left-to-right: calculating the value of
lmx
, which maintains the maximum score possible up to the current cell while moving from left to right. -
Traverse right-to-left: calculating the value of
rmx
, which keeps track of the maximum score possible up to the current cell when moving from right to left.
These two sweeps are necessary because moving to a cell on the right might be advantageous when seen from one direction but not from the other. Therefore, for every cell, we calculate the best possible score from the f
array value for that row taking into account the movement cost, both from the left and the right.
By the end of these two sweeps, we have an updated array f
that contains the best score we can have after we have finished processing the current row.
In essence, the algorithm balances selecting cells with high values versus the cost of moving to each cell from the cells chosen in previous rows. After going through all the rows, the maximum value in the f
array is the desired maximum number of points we can achieve.
Learn more about Dynamic Programming patterns.
Solution Approach
The provided solution implements a dynamic programming strategy that utilizes a single-dimensional array f
to keep track of the maximum scores achievable for each column up to the current row.
Initially, f
is a copy of the first row of the points
matrix since there is no previous row to consider, and thus no penalty cost.
As we iterate over each subsequent row, we use two temporary arrays - lmx
and rmx
standing for "left max" and "right max," respectively. These arrays are actually not explicitly created in the code; rather they represent the maxima calculated on-the-fly during left-to-right and right-to-left sweeps.
Here's a step-by-step breakdown:
-
Left-to-right sweep: Iterate through the columns from left to right. We calculate the running
lmx
, which keeps track of the maximum score that could have been obtained from choosing any of the previous cells in the row (including the cost of moving to that cell). As we move right, we add the indexj
to thef[j]
value because if we move further right in the next row, the cost will increase, which is why the costj
is proactively added to the score. For each cell, we calculate the possible score if we move there from the left asp[j] + lmx - j
and store it in the temporary arrayg
. -
Right-to-left sweep: This is similar to the left-to-right sweep but in the opposite direction. We maintain a running
rmx
to track the maximum score that could have been obtained if moving from any previous cell to the right. While moving to the left, we subtract the indexj
when calculating rmx because the cost to move leftward in the next row will decrease. For each cell, we then calculate the possible score if we move there from the right asp[j] + rmx + j
. -
Combining the results: After both sweeps, for each column, the temporary array
g
holds the maximum of the scores obtainable from either direction. Then we updatef
withg
to use in the next row's calculations. -
Return the maximum value: Once we reach the last row, we've calculated the maximum possible scores for that row considering all rows above it. The final result is the maximum value in
f
.
To summarize, the pattern used here involves iteratively updating a dynamic programming table (f
) while considering the movement cost in both directions (left-to-right and right-to-left). It elegantly captures the trade-offs between picking high-value cells and minimizing the penalty for moving between cells of different columns in adjacent rows. The sweeps are essential to factor in the cost impact from both sides before deciding on the best cells to choose.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Say we have the following 3 x 4
matrix called points
:
points = [ [1, 2, 2, 4], [3, 1, 2, 1], [4, 1, 1, 3] ]
Our goal is to choose one cell from each row to maximize the score, subtracting the absolute difference of column indices between chosen cells of consecutive rows.
Initialization
We start by copying the first row into our f
array since there is no previous row to consider:
f = [1, 2, 2, 4]
Iterating over the second row
We will perform both left-to-right and right-to-left sweeps:
- Left-to-right sweep:
Starting at j=0
:
lmx
isf[0]
since this is the first element in thef
array.lmx = 1
.- For
g[0]
, we takepoints[1][0] + lmx - 0 = 3 + 1 - 0 = 4
.
Continuing to j=1
and so on:
- We update
lmx
tomax(lmx, f[j] - j)
. - Calculate
g[j]
aspoints[1][j] + lmx - j
.
After the sweep, lmx
values are calculated and they are [4, 4, 4, 4]
.
- Right-to-left sweep:
Starting at j=3
and going left:
rmx
is initialized tof[3] - 3 = 4 - 3 = 1
.- For
g[3]
, since g already has a value from the left-to-right sweep, we takemax(g[3], points[1][3] + rmx + 3)
.
Continuing to j=2
and so on:
- We update
rmx
tomax(rmx, f[j] + j)
. - Update
g[j]
tomax(g[j], points[1][j] + rmx + j)
.
After the sweep, the combined maximum g
values are [4, 4, 4, 5]
.
Iterating over the third and final row
Repeat the same steps as above. After the left-to-right and right-to-left sweeps, the final g
values might look like [8, 8, 7, 8]
.
Conclusion
After processing all rows, g
holds the maximum scores possible for each cell in the last row including the penalties for moving between columns. The maximum score of g
is our answer, which in this case is 8
.
Thus, our dynamic programming approach has allowed us to navigate through the matrix, weighing the value of each point against the penalty for moving between columns, to find the maximum total score we can achieve.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maxPoints(self, points: List[List[int]]) -> int:
5 # Get the number of columns in the points matrix.
6 num_columns = len(points[0])
7
8 # Initialize dp array with the first row of points.
9 dp = points[0][:]
10
11 # Iterate over each row in points starting from the second row.
12 for row in points[1:]:
13 # Create a new row for dp, to store the maximum points for the current row.
14 new_dp = [0] * num_columns
15
16 # Initialize left max value, this tracks the maximum from the left side including the current position.
17 left_max = float('-inf')
18 # Left pass: Fill in the new_dp array considering the left side of each column.
19 for j in range(num_columns):
20 left_max = max(left_max, dp[j] + j)
21 new_dp[j] = max(new_dp[j], row[j] + left_max - j)
22
23 # Initialize right max value, this tracks the maximum from the right side including the current position.
24 right_max = float('-inf')
25 # Right pass: Update the new_dp array considering the right side of each column.
26 for j in range(num_columns - 1, -1, -1):
27 right_max = max(right_max, dp[j] - j)
28 new_dp[j] = max(new_dp[j], row[j] + right_max + j)
29
30 # Update dp array with the new_dp for the next iteration.
31 dp = new_dp
32
33 # Return the maximum points that can be collected, which is the max value in the last dp row.
34 return max(dp)
35
1class Solution {
2 public long maxPoints(int[][] points) {
3 // 'n' denotes the length of columns in 'points'
4 int n = points[0].length;
5
6 // 'currentRowMaxPoints' stores the maximum points achievable for the current row
7 long[] currentRowMaxPoints = new long[n];
8
9 // 'infinity' is a large number to be considered as negative infinity
10 final long infinity = 1L << 60;
11
12 // Loop through all the rows of the 'points' matrix
13 for (int[] row : points) {
14 // 'nextRowMaxPoints' is a temporary array to store the maximum points for the next row
15 long[] nextRowMaxPoints = new long[n];
16
17 // 'leftMax' tracks the maximum points from the left up to the current position
18 long leftMax = -infinity;
19
20 // 'rightMax' tracks the maximum points from the right up to the current position
21 long rightMax = -infinity;
22
23 // Forward pass to calculate the max points when coming from the left
24 for (int j = 0; j < n; ++j) {
25 leftMax = Math.max(leftMax, currentRowMaxPoints[j] + j);
26 nextRowMaxPoints[j] = Math.max(nextRowMaxPoints[j], row[j] + leftMax - j);
27 }
28
29 // Backward pass to calculate the max points when coming from the right
30 for (int j = n - 1; j >= 0; --j) {
31 rightMax = Math.max(rightMax, currentRowMaxPoints[j] - j);
32 nextRowMaxPoints[j] = Math.max(nextRowMaxPoints[j], row[j] + rightMax + j);
33 }
34
35 // Update 'currentRowMaxPoints' with the max points so far for the next iteration
36 currentRowMaxPoints = nextRowMaxPoints;
37 }
38
39 // 'maxPoints' will store the overall maximum from 'currentRowMaxPoints'
40 long maxPoints = 0;
41 for (long pointsValue : currentRowMaxPoints) {
42 maxPoints = Math.max(maxPoints, pointsValue);
43 }
44
45 // The final answer is the maximum points we can collect from the matrix
46 return maxPoints;
47 }
48}
49
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 long long maxPoints(std::vector<std::vector<int>>& pointsMatrix) {
7 // Alias for long long type to be used later in the function
8 using ll = long long;
9
10 // Number of columns in the input matrix
11 int n = pointsMatrix[0].size();
12
13 // Initial row (f) will hold the maximum points for each column
14 std::vector<ll> prevRow(n);
15
16 // Representing infinity as a large number, useful to ensure
17 // that if a path includes an unfeasible option, it is ignored
18 const ll inf = 1e18;
19
20 // Loop over each row in the points matrix
21 for (auto& points : pointsMatrix) {
22 // Temporary row (g) to calculate new scores considering the transition
23 std::vector<ll> currentRow(n);
24
25 // Variables to track the left and right maximum of previous row
26 ll leftMax = -inf, rightMax = -inf;
27
28 // Forward iteration: calculate max points from the left to the current position
29 for (int j = 0; j < n; ++j) {
30 leftMax = std::max(leftMax, prevRow[j] + j);
31 currentRow[j] = std::max(currentRow[j], points[j] + leftMax - j);
32 }
33
34 // Backward iteration: calculate max points from the right to the current position
35 for (int j = n - 1; j >= 0; --j) {
36 rightMax = std::max(rightMax, prevRow[j] - j);
37 currentRow[j] = std::max(currentRow[j], points[j] + rightMax + j);
38 }
39
40 // Update the previous row to the current row for next iteration
41 prevRow = std::move(currentRow);
42 }
43
44 // Return the maximum points that can be achieved
45 return *std::max_element(prevRow.begin(), prevRow.end());
46 }
47};
48
1function maxPoints(points: number[][]): number {
2 // n represents the number of columns in the points grid.
3 const columns = points[0].length;
4 // Initialize the dynamic programming array to store maximum points.
5 const dp: number[] = new Array(columns).fill(0);
6
7 // Iterate through each row of points.
8 for (const rowPoints of points) {
9 // Initialize a temporary array to store the current row's maximum points.
10 const currentMax: number[] = new Array(columns).fill(0);
11 // Variables to keep track of the left and right maximum with modifiers.
12 let leftMax = -Infinity;
13 let rightMax = -Infinity;
14
15 // Traverse from left to right to calculate the leftMax contributions.
16 for (let j = 0; j < columns; ++j) {
17 // Update leftMax by considering the previously calculated dp.
18 leftMax = Math.max(leftMax, dp[j] + j);
19 // Calculate maximum points for the current position from the left side.
20 currentMax[j] = Math.max(currentMax[j], rowPoints[j] + leftMax - j);
21 }
22
23 // Traverse from right to left to calculate the rightMax contributions.
24 for (let j = columns - 1; j >= 0; --j) {
25 // Update rightMax by considering the previously calculated dp.
26 rightMax = Math.max(rightMax, dp[j] - j);
27 // Calculate maximum points for the current position from the right side.
28 currentMax[j] = Math.max(currentMax[j], rowPoints[j] + rightMax + j);
29 }
30
31 // Prepare dp for the next iteration by copying the values from currentMax.
32 dp.splice(0, columns, ...currentMax);
33 }
34
35 // After processing all rows, the maximum points will be the max value in dp.
36 return Math.max(...dp);
37}
38
Time and Space Complexity
The provided code is designed to solve the problem of finding the maximum points you can obtain by walking on a grid, where points[i][j]
represents the points you get from the i-th row and j-th column. The algorithm maintains two arrays f
and g
to store the intermediate results.
Time Complexity
The time complexity of the code can be determined as follows:
- There is a nested loop structure where the outer loop iterates over the rows of the input
points
list, and the inner loops iterate over the columns. - The outer loop runs
len(points) - 1
times because it starts from the second row inpoints
. Since the inner loops iteraten
times each (wheren
is the number of columns which islen(points[0])
), we have two separate iterations for each row - one from left to right and the other from right to left. - Inside each iteration of the inner loops, a constant time operation is performed to compute the maximum points.
Therefore, the time complexity is O(m * n)
where m
is the number of rows in points
and n
is the number of columns.
Space Complexity
The space complexity of the algorithm is determined as follows:
- It uses two additional arrays
f
andg
, both of sizen
(len(points[0])
), to store intermediate results. - No other significant data structures are used that grow with the size of the input.
Hence, the space complexity is O(n)
.
In summary, the time complexity is O(m * n)
and the space complexity is O(n)
where m
is the number of rows and n
is the number of columns in the points
list.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!