leetcode

commit 03a9a893c3ab5d7dd12683ef1be7c21e4fa4fffb
parent 0613ea4cc53b05b6f762bd04febe9fc59eb735b9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 28 Jan 2024 21:02:13 +0000

Daily Problem

Diffstat:
A
Problems/1074.cpp
 | 
29
+++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 30 insertions(+), 0 deletions(-)
diff --git a/Problems/1074.cpp b/Problems/1074.cpp
@@ -0,0 +1,29 @@
+class Solution {
+  public:
+    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) const {
+        const int n = size(matrix), m = size(matrix[0]);
+
+        for (int i = 0; i < n; i++) {
+            for (int j = 0, acc = 0; j < m; j++) {
+                matrix[i][j] = acc += matrix[i][j];
+            }
+        }
+
+        unordered_map<int, int> um;
+        int res = 0;
+
+        for (int i = 0; i < m; i++) {
+            for (int j = i; j < m; j++) {
+                um = {{0, 1}};
+                int crnt = 0;
+                for (int k = 0; k < n; k++) {
+                    crnt += matrix[k][j] - (i > 0 ? matrix[k][i - 1] : 0);
+                    res += um[crnt - target];
+                    um[crnt]++;
+                }
+            }
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -600,6 +600,7 @@ for solving problems.
 |  1070  |   Medium   | [Product Sales Analysis III](Problems/1070.cpp)                                                    |
 |  1071  |    Easy    | [Greatest Common Divisor of Strings](Problems/1071.cpp)                                            |
 |  1072  |   Medium   | [Flip Columns For Maximum Number of Equal Rows](Problems/1072.cpp)                                 |
+|  1074  |    Hard    | [Number of Submatrices That Sum to Target](Problems/1074.cpp)                                      |
 |  1075  |    Easy    | [Project Employees I](Problems/1075.cpp)                                                           |
 |  1079  |   Medium   | [Letter Tile Possibilities](Problems/1079.cpp)                                                     |
 |  1081  |   Medium   | [Smallest Subsequence of Distinct Characters](Problems/1081.cpp)                                   |