leetcode

commit ebf57653ad2c6081cb9b018ec634e7b5641cb1f8
parent 29bc8f52242fc488b2665bb23828395b05d5403e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 26 Apr 2024 13:52:40 +0200

Daily Problem

Diffstat:
A
Problems/1289.cpp
 | 
24
++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 25 insertions(+), 0 deletions(-)
diff --git a/Problems/1289.cpp b/Problems/1289.cpp
@@ -0,0 +1,24 @@
+class Solution {
+  public:
+    int minFallingPathSum(const vector<vector<int>> &grid) const {
+        const int n = size(grid), m = size(grid[0]);
+        int first = 0, second = 0, pos = -1;
+
+        for (auto i = 0; i < n; i++) {
+            auto first2 = INT_MAX, second2 = INT_MAX, pos2 = -1;
+            for (auto j = 0; j < m; j++) {
+                const int crnt = grid[i][j] + (j != pos ? first : second);
+                if (crnt < first2) {
+                    second2 = first2;
+                    first2 = crnt;
+                    pos2 = j;
+                } else {
+                    second2 = min(second2, crnt);
+                }
+            }
+            first = first2, second = second2, pos = pos2;
+        }
+
+        return first;
+    }
+};
diff --git a/README.md b/README.md
@@ -709,6 +709,7 @@ for solving problems.
 |  1286  |   Medium   | [Iterator for Combination](Problems/1286.cpp)                                                      |
 |  1287  |    Easy    | [Element Appearing More Than 25% In Sorted Array](Problems/1287.cpp)                               |
 |  1288  |   Medium   | [Remove Covered Intervals](Problems/1288.cpp)                                                      |
+|  1289  |    Hard    | [Minimum Falling Path Sum II](Problems/1289.cpp)                                                   |
 |  1290  |    Easy    | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp)                             |
 |  1291  |   Medium   | [Sequential Digits](Problems/1291.cpp)                                                             |
 |  1292  |   Medium   | [Maximum Side Length of a Square with Sum Less than or Equal to Threshold](Problems/1292.cpp)      |