leetcode

commit f9d366413e3f1f5152616db0939c0282dd8b60aa
parent 2377266adb39dd1364db00342b1d317b79dbed60
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 17 Mar 2026 18:59:31 -0600

3070. count submatrices with top-left element and sum less than k

Diffstat:
A
count_submat_top_left_less_k.c
 | 
43
+++++++++++++++++++++++++++++++++++++++++++
A
count_submat_top_left_less_k.py
 | 
32
++++++++++++++++++++++++++++++++

2 files changed, 75 insertions(+), 0 deletions(-)
diff --git a/count_submat_top_left_less_k.c b/count_submat_top_left_less_k.c
@@ -0,0 +1,43 @@
+// 3070. Count Submatrices with Top-Left Element and Sum Less Than k
+#include "leetcode.h"
+
+/*
+ * you are given a 0-index integer matrix 'grid' and an integer 'k'. return the
+ * number of submatrices that contain the top-left element of the 'grid', and
+ * have a sum less than or equal to 'k'.
+ */
+
+int countSubmatrices(int **grid, int gridSize, int *gridColSize, int k) {
+  int m = gridSize, n = gridColSize[0], ans = 0;
+  for (int i = 0; i < m; i++)
+    for (int j = 0; j < n; j++) {
+      if (i > 0)
+        grid[i][j] += grid[i - 1][j];
+      if (j > 0)
+        grid[i][j] += grid[i][j - 1];
+      if (i > 0 && j > 0)
+        grid[i][j] -= grid[i - 1][j - 1];
+      if (grid[i][j] <= k)
+        ans++;
+      else
+        break;
+    }
+  return ans;
+}
+
+int main() {
+  int g1i[2][3] = {{7, 6, 3}, {6, 6, 1}};
+  int g2i[3][3] = {{7, 2, 9}, {1, 5, 0}, {2, 6, 6}};
+  struct two_d_arr *g1 =
+      two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+  struct two_d_arr *g2 =
+      two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+  int r1 = countSubmatrices(g1->arr, g1->row_size, g1->col_size, 18);
+  int r2 = countSubmatrices(g2->arr, g2->row_size, g2->col_size, 20);
+  printf("%d\n", r1);
+  assert(r1 == 4);
+  printf("%d\n", r2);
+  assert(r2 == 6);
+  two_d_arr_free(g1);
+  two_d_arr_free(g2);
+}
diff --git a/count_submat_top_left_less_k.py b/count_submat_top_left_less_k.py
@@ -0,0 +1,32 @@
+# 3070. Count Submatrices with Top-Left Element and Sum Less Than k
+from typing import List
+
+"""
+you are given a 0-index integer matrix 'grid' and an integer 'k'. return the
+number of submatrices that contain the top-left element of the 'grid', and
+have a sum less than or equal to 'k'.
+"""
+
+
+class Solution:
+    def countSubmatrices(self, grid: List[List[int]], k: int) -> int:
+        m, n, ans = len(grid), len(grid[0]), 0
+        for i in range(m):
+            for j in range(n):
+                if i > 0:
+                    grid[i][j] += grid[i - 1][j]
+                if j > 0:
+                    grid[i][j] += grid[i][j - 1]
+                if i > 0 and j > 0:
+                    grid[i][j] -= grid[i - 1][j - 1]
+                if grid[i][j] <= k:
+                    ans += 1
+                else:
+                    break
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.countSubmatrices(grid=[[7, 6, 3], [6, 6, 1]], k=18))
+    print(obj.countSubmatrices(grid=[[7, 2, 9], [1, 5, 0], [2, 6, 6]], k=20))