leetcode

commit da7d5339764626a55f99e426551e2ecdd034a169
parent 03ca5c6054084ae3997c481efbc6e8eeb31a005c
Author: Jack Sangdahl <jack@pngu.org>
Date:   Thu, 13 Nov 2025 18:56:20 -0700

2536. increment submatrices by one

Diffstat:
A
increment_submatrices_one.c
 | 
75
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
increment_submatrices_one.py
 | 
43
+++++++++++++++++++++++++++++++++++++++++++

2 files changed, 118 insertions(+), 0 deletions(-)
diff --git a/increment_submatrices_one.c b/increment_submatrices_one.c
@@ -0,0 +1,75 @@
+// 2536. Increment Submatrices by One
+#include "leetcode.h"
+
+/*
+ * you are given a positive integer 'n', indicating that we initially have an 'n
+ * x n' 0-indexed integer matrix 'mat' filled with zeros. you are also given a
+ * 2d integer array 'query'. for each 'query[i] = [row1_i, col1_i, row2_i,
+ * col2_i]', you should do the following operation: add 1 to every element in
+ * the submatrix with the top left corner '(row1_i, col1_i)' and the bottom
+ * right corner '(row2_i, col2_i)'. that is, add 1 to 'mat[x][y]' for all
+ * 'row1_i <= x <= row2_i' and 'col1_i <= y <= col2_i'. return the matrix 'mat'
+ * after performing every query
+ */
+
+int **rangeAddQueries(int n, int **queries, int queriesSize,
+                      int *queriesColSize, int *returnSize,
+                      int **returnColumnSizes) {
+  int **ans = (int **)malloc(n * sizeof(int *));
+  for (int i = 0; i < n; i++)
+    ans[i] = (int *)calloc(n, sizeof(int));
+  for (int i = 0; i < queriesSize; i++) {
+    int r1 = queries[i][0];
+    int c1 = queries[i][1];
+    int r2 = queries[i][2];
+    int c2 = queries[i][3];
+    for (int j = r1; j <= r2; j++) {
+      ans[j][c1]++;
+      if (c2 < n - 1)
+        ans[j][c2 + 1]--;
+    }
+  }
+  for (int i = 0; i < n; i++)
+    for (int j = 1; j < n; j++)
+      ans[i][j] += ans[i][j - 1];
+  *returnSize = n;
+  *returnColumnSizes = (int *)malloc(n * sizeof(int));
+  for (int i = 0; i < n; i++)
+    returnColumnSizes[0][i] = n;
+  return ans;
+}
+
+int main() {
+  int q1i[2][4] = {{1, 1, 2, 2}, {0, 0, 1, 1}}, rs1, *rcs1;
+  int q2i[1][4] = {{0, 0, 1, 1}}, rs2, *rcs2;
+  struct two_d_arr *q1 =
+      two_d_arr_init(ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i);
+  struct two_d_arr *q2 =
+      two_d_arr_init(ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i);
+  int **raq1 =
+      rangeAddQueries(3, q1->arr, q1->row_size, q1->col_size, &rs1, &rcs1);
+  int **raq2 =
+      rangeAddQueries(2, q2->arr, q2->row_size, q2->col_size, &rs2, &rcs2);
+  for (int i = 0; i < rs1; i++) {
+    for (int j = 0; j < rcs1[i]; j++)
+      printf("%d ", raq1[i][j]); // expect: [[1,1,0],[1,2,1],[0,1,1]]
+    printf("\n");
+  }
+  printf("\n");
+  for (int i = 0; i < rs2; i++) {
+    for (int j = 0; j < rcs2[i]; j++)
+      printf("%d ", raq2[i][j]); // expect: [[1,1],[1,1]]
+    printf("\n");
+  }
+  printf("\n");
+  for (int i = 0; i < rs1; i++)
+    free(raq1[i]);
+  free(raq1);
+  free(rcs1);
+  two_d_arr_free(q1);
+  for (int i = 0; i < rs2; i++)
+    free(raq2[i]);
+  free(raq2);
+  free(rcs2);
+  two_d_arr_free(q2);
+}
diff --git a/increment_submatrices_one.py b/increment_submatrices_one.py
@@ -0,0 +1,43 @@
+# 2536. Increment Submatrices by One
+
+"""
+you are given a positive integer 'n', indicating that we initially have an 'n
+x n' 0-indexed integer matrix 'mat' filled with zeros. you are also given a
+2d integer array 'query'. for each 'query[i] = [row1_i, col1_i, row2_i,
+col2_i]', you should do the following operation: add 1 to every element in
+the submatrix with the top left corner '(row1_i, col1_i)' and the bottom
+right corner '(row2_i, col2_i)'. that is, add 1 to 'mat[x][y]' for all
+'row1_i <= x <= row2_i' and 'col1_i <= y <= col2_i'. return the matrix 'mat'
+after performing every query
+"""
+
+
+class Solution(object):
+    def rangeAddQueries(self, n, queries):
+        """
+        :type n: int
+        :type queries: List[List[int]]
+        :rtype: List[List[int]]
+        """
+        ans = [[0] * n for _ in range(n)]
+        for r1, c1, r2, c2 in queries:
+            ans[r1][c1] += 1
+            if r2 + 1 < n:
+                ans[r2 + 1][c1] -= 1
+            if c2 + 1 < n:
+                ans[r1][c2 + 1] -= 1
+            if r2 + 1 < n and c2 + 1 < n:
+                ans[r2 + 1][c2 + 1] += 1
+        for i in range(1, n):
+            for j in range(n):
+                ans[i][j] += ans[i - 1][j]
+        for i in range(n):
+            for j in range(1, n):
+                ans[i][j] += ans[i][j - 1]
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.rangeAddQueries(n=3, queries=[[1, 1, 2, 2], [0, 0, 1, 1]]))
+    print(obj.rangeAddQueries(n=2, queries=[[0, 0, 1, 1]]))