Leetcode | Maximum Number of Points with Cost | Kotlin

devstromo · devstromo · commit 76bff6ccb522 · 2025-04-20T20:19:30.000-03:00
diff --git a/leetcode/src/main/kotlin/com/devstromo/medium/p1937/DESCRIPTION.md b/leetcode/src/main/kotlin/com/devstromo/medium/p1937/DESCRIPTION.md
@@ -0,0 +1,42 @@
+# 1937. Maximum Number of Points with Cost
+
+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.length`
+- `n == points[r].length`
+- `1 <= m, n <= 10^5`
+- `1 <= m * n <= 10^5`
+- `0 <= points[r][c] <= 10^5`
diff --git a/leetcode/src/main/kotlin/com/devstromo/medium/p1937/SolutionKt.kt b/leetcode/src/main/kotlin/com/devstromo/medium/p1937/SolutionKt.kt
@@ -0,0 +1,36 @@
+package com.devstromo.medium.p1937
+
+class SolutionKt {
+    fun maxPoints(points: Array<IntArray>): Long {
+        val m = points.size
+        val n = points[0].size
+        var prev = LongArray(n) { points[0][it].toLong() }
+
+        for (i in 1 until m) {
+            val left = LongArray(n)
+            val right = LongArray(n)
+            val curr = LongArray(n)
+
+            // Build left max array
+            left[0] = prev[0]
+            for (j in 1 until n) {
+                left[j] = maxOf(left[j - 1] - 1, prev[j])
+            }
+
+            // Build right max array
+            right[n - 1] = prev[n - 1]
+            for (j in n - 2 downTo 0) {
+                right[j] = maxOf(right[j + 1] - 1, prev[j])
+            }
+
+            // Calculate current row's maximum points
+            for (j in 0 until n) {
+                curr[j] = points[i][j] + maxOf(left[j], right[j])
+            }
+
+            prev = curr
+        }
+
+        return prev.max()
+    }
+}
diff --git a/leetcode/src/test/kotlin/com/devstromo/medium/p1937/SolutionKtUnitTest.kt b/leetcode/src/test/kotlin/com/devstromo/medium/p1937/SolutionKtUnitTest.kt
@@ -0,0 +1,31 @@
+package com.devstromo.medium.p1937
+
+import org.junit.jupiter.api.Assertions
+import org.junit.jupiter.api.Test
+
+class SolutionKtUnitTest {
+    private val solution = SolutionKt()
+
+    @Test
+    fun `Test Maximum Number of Points with Cost`() {
+        Assertions.assertEquals(
+            9, solution.maxPoints(
+                arrayOf(
+                    intArrayOf(1, 2, 3),
+                    intArrayOf(1, 5, 1),
+                    intArrayOf(3, 1, 1)
+                )
+            )
+        )
+        Assertions.assertEquals(
+            11, solution.maxPoints(
+                arrayOf(
+                    intArrayOf(1, 5),
+                    intArrayOf(2, 3),
+                    intArrayOf(4, 2)
+                )
+            )
+        )
+    }
+
+}
