1937. Maximum Number of Points with Cost - Explanation

Description

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 optimal cells to pick are (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 optimal cells to pick are (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 <= 100,000
1 <= m * n <= 100,000
0 <= points[r][c] <= 100,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])

        def dfs(r, c):
            if r == m - 1:
                return 0

            res = 0
            for col in range(n):
                res = max(res, points[r + 1][col] - abs(col - c) + dfs(r + 1, col))
            return res

        ans = 0
        for c in range(n):
            ans = max(ans, points[0][c] + dfs(0, c))
        return ans

Time & Space Complexity

Time complexity: $O(n ^ m)$
Space complexity: $O(m)$ for recursion stack.

Where $m$ is the number of rows, and $n$ is the number of columns.

2. Dynamic Programming (Top-Down)

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        memo = {}

        def dfs(r, c):
            if (r, c) in memo:
                return memo[(r, c)]
            if r == m - 1:
                return 0

            res = 0
            for col in range(n):
                res = max(res, points[r + 1][col] - abs(col - c) + dfs(r + 1, col))

            memo[(r, c)] = res
            return res

        ans = 0
        for c in range(n):
            ans = max(ans, points[0][c] + dfs(0, c))
        return ans

Time & Space Complexity

Time complexity: $O(m * n ^ 2)$
Space complexity: $O(n)$

Where $m$ is the number of rows, and $n$ is the number of columns.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ROWS, COLS = len(points), len(points[0])
        dp = points[0]

        for r in range(1, ROWS):
            left = [0] * COLS
            left[0] = dp[0]
            for c in range(1, COLS):
                left[c] = max(dp[c], left[c - 1] - 1)

            right = [0] * COLS
            right[COLS - 1] = dp[COLS - 1]
            for c in range(COLS - 2, -1, -1):
                right[c] = max(dp[c], right[c + 1] - 1)

            nextDp = points[r][:]
            for c in range(COLS):
                nextDp[c] += max(left[c], right[c])

            dp = nextDp

        return max(dp)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the number of rows, and $n$ is the number of columns.

4. Dynamic Programming (Space Optimized)

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        ROWS, COLS = len(points), len(points[0])
        prev = points[0]

        for r in range(1, ROWS):
            cur = [0] * COLS
            cur[0] = prev[0]
            for c in range(1, COLS):
                cur[c] = max(prev[c], cur[c - 1] - 1)

            rightMax = prev[COLS - 1]
            for c in range(COLS - 2, -1 , -1):
                rightMax = max(prev[c], rightMax - 1)
                cur[c] = max(cur[c], rightMax) + points[r][c]

            cur[COLS - 1] += points[r][COLS - 1]
            prev = cur

        return max(prev)

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the number of rows, and $n$ is the number of columns.