leetcode

commit 8d924ee213a626f679fcb2e06a9b479b17d32f0b
parent f9d366413e3f1f5152616db0939c0282dd8b60aa
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 18 Mar 2026 21:24:11 -0600

3212. count submatrices with equal frequency of x and y

Diffstat:
A
count_submat_equal_freq_xy.c
 | 
55
+++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
count_submat_equal_freq_xy.py
 | 
30
++++++++++++++++++++++++++++++

2 files changed, 85 insertions(+), 0 deletions(-)
diff --git a/count_submat_equal_freq_xy.c b/count_submat_equal_freq_xy.c
@@ -0,0 +1,55 @@
+// 3212. Count Submatrices With Equal Frequency of X and Y
+#include "leetcode.h"
+
+/*
+ * given a 2d character matrix 'grid' where 'grid[i][j]' is either "X", "Y", or
+ * ".", return the number of submatrices that contain 'grid[0][0]', an equal
+ * frequency of 'X' and 'Y', and at least one 'X'.
+ */
+
+int numberOfSubmatrices(char **grid, int gridSize, int *gridColSize) {
+  int m = gridSize, n = gridColSize[0], ans = 0;
+  int **pre_x = (int **)malloc((m + 1) * sizeof(int *));
+  int **pre_y = (int **)malloc((m + 1) * sizeof(int *));
+  for (int i = 0; i < m + 1; i++) {
+    pre_x[i] = (int *)calloc(n + 1, sizeof(int));
+    pre_y[i] = (int *)calloc(n + 1, sizeof(int));
+  }
+  for (int i = 1; i < m + 1; i++)
+    for (int j = 1; j < n + 1; j++) {
+      pre_x[i][j] += (pre_x[i - 1][j] + pre_x[i][j - 1] - pre_x[i - 1][j - 1]);
+      pre_y[i][j] += (pre_y[i - 1][j] + pre_y[i][j - 1] - pre_y[i - 1][j - 1]);
+      if (grid[i - 1][j - 1] == 'X')
+        pre_x[i][j]++;
+      else if (grid[i - 1][j - 1] == 'Y')
+        pre_y[i][j]++;
+      if ((pre_x[i][j] != 0 && pre_y[i][j] != 0) &&
+          (pre_x[i][j] == pre_y[i][j]))
+        ans++;
+    }
+  for (int i = 0; i < m + 1; i++) {
+    free(pre_x[i]);
+    free(pre_y[i]);
+  }
+  free(pre_x);
+  free(pre_y);
+  return ans;
+}
+
+int main() {
+  char *g1[2][3] = {{"X", "Y", "."}, {"Y", ".", "."}};
+  char *g2[2][2] = {{"X", "X"}, {"X", "Y"}};
+  char *g3[2][2] = {{".", "."}, {".", "."}};
+  int r1 = numberOfSubmatrices((char **)g1, ARRAY_SIZE(g1),
+                               (int *)ARRAY_SIZE(g1[0]));
+  int r2 = numberOfSubmatrices((char **)g2, ARRAY_SIZE(g2),
+                               (int *)ARRAY_SIZE(g2[0]));
+  int r3 = numberOfSubmatrices((char **)g3, ARRAY_SIZE(g3),
+                               (int *)ARRAY_SIZE(g3[0]));
+  printf("%d\n", r1);
+  assert(r1 == 3);
+  printf("%d\n", r2);
+  assert(r2 == 0);
+  printf("%d\n", r3);
+  assert(r3 == 0);
+}
diff --git a/count_submat_equal_freq_xy.py b/count_submat_equal_freq_xy.py
@@ -0,0 +1,30 @@
+# 3212. Count Submatrices With Equal Frequency of X and Y
+from typing import List
+
+"""
+given a 2d character matrix 'grid' where 'grid[i][j]' is either "X", "Y", or
+".", return the number of submatrices that contain 'grid[0][0]', an equal
+frequency of 'X' and 'Y', and at least one 'X'.
+"""
+
+
+class Solution:
+    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
+        n, ans = len(grid[0]), 0
+        x, y = [0] * n, [0] * n
+        for i in grid:
+            rx, ry = 0, 0
+            for j in range(n):
+                rx += i[j] == "X"
+                ry += i[j] == "Y"
+                x[j] += rx
+                y[j] += ry
+                ans += (x[j] > 0) & (x[j] == y[j])
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.numberOfSubmatrices(grid=[["X", "Y", "."], ["Y", ".", "."]]))
+    print(obj.numberOfSubmatrices(grid=[["X", "X"], ["X", "Y"]]))
+    print(obj.numberOfSubmatrices(grid=[[".", "."], [".", "."]]))