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:

1. 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.

2. 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:

1. 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 index j to the f[j] value because if we move further right in the next row, the cost will increase, which is why the cost j is proactively added to the score. For each cell, we calculate the possible score if we move there from the left as p[j] + lmx - j and store it in the temporary array g.

2. 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 index j 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 as p[j] + rmx + j.

3. 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 update f with g to use in the next row's calculations.

4. 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.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Say we have the following 3 x 4 matrix called points:

1points = [
2  [1, 2, 2, 4],
3  [3, 1, 2, 1],
4  [4, 1, 1, 3]
5]

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:

1f = [1, 2, 2, 4]

Iterating over the second row

We will perform both left-to-right and right-to-left sweeps:

1. Left-to-right sweep:

Starting at j=0:

• lmx is f[0] since this is the first element in the f array. lmx = 1.
• For g[0], we take points[1][0] + lmx - 0 = 3 + 1 - 0 = 4.

Continuing to j=1 and so on:

• We update lmx to max(lmx, f[j] - j).
• Calculate g[j] as points[1][j] + lmx - j.

After the sweep, lmx values are calculated and they are [4, 4, 4, 4].

2. Right-to-left sweep:

Starting at j=3 and going left:

• rmx is initialized to f[3] - 3 = 4 - 3 = 1.
• For g[3], since g already has a value from the left-to-right sweep, we take max(g[3], points[1][3] + rmx + 3).

Continuing to j=2 and so on:

• We update rmx to max(rmx, f[j] + j).
• Update g[j] to max(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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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 in points. Since the inner loops iterate n times each (where n is the number of columns which is len(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 and g, both of size n (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.