leetcode

commit 65d4c333e07eaa581033ab4295e79db2687235f5
parent 0f6d39ed1716d15faada8478613caa0f6cf7e125
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue, 24 Mar 2026 20:23:14 -0600

3546. equal sum grid partition 1

Diffstat:
A
equal_sum_grid_partition1.c
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++
A
equal_sum_grid_partition1.py
 | 
36
++++++++++++++++++++++++++++++++++++

2 files changed, 85 insertions(+), 0 deletions(-)
diff --git a/equal_sum_grid_partition1.c b/equal_sum_grid_partition1.c
@@ -0,0 +1,49 @@
+// 3546. Equal Sum Grid Partition I
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' matrix 'grid' of positive integers. your task is to
+ * determine if it is possible to make either one horizontal or one vertical cut
+ * on the grid such that each of the two resulting sections formed by the cut is
+ * non-empty and the sum of the elements in both sections is equal. return
+ * 'true' if such partition exists, otherwise return 'false'.
+ */
+
+bool canPartitionGrid(int **grid, int gridSize, int *gridColSize) {
+  int m = gridSize, n = gridColSize[0];
+  long long total = 0;
+  for (int i = 0; i < m; i++)
+    for (int j = 0; j < n; j++)
+      total += grid[i][j];
+  if (total % 2)
+    return false;
+  long long target = total / 2, sum = 0;
+  for (int i = 0; i < m - 1; i++) {
+    for (int j = 0; j < n; j++)
+      sum += grid[i][j];
+    if (sum == target)
+      return true;
+  }
+  sum = 0;
+  for (int j = 0; j < n - 1; j++) {
+    for (int i = 0; i < m; i++)
+      sum += grid[i][j];
+    if (sum == target)
+      return true;
+  }
+  return false;
+}
+
+int main() {
+  int g1i[2][2] = {{1, 4}, {2, 3}}, g2i[2][2] = {{1, 3}, {2, 4}};
+  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);
+  bool r1 = canPartitionGrid(g1->arr, g1->row_size, g1->col_size);
+  bool r2 = canPartitionGrid(g2->arr, g2->row_size, g2->col_size);
+  printf("%d\n", r1);
+  assert(r1 == true);
+  printf("%d\n", r2);
+  assert(r2 == false);
+}
diff --git a/equal_sum_grid_partition1.py b/equal_sum_grid_partition1.py
@@ -0,0 +1,36 @@
+# 3546. Equal Sum Grid Partition I
+from typing import List
+
+"""
+you are given an 'm x n' matrix 'grid' of positive integers. your task is to
+determine if it is possible to make either one horizontal or one vertical cut
+on the grid such that each of the two resulting sections formed by the cut is
+non-empty and the sum of the elements in both sections is equal. return
+'true' if such partition exists, otherwise return 'false'.
+"""
+
+
+class Solution:
+    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
+        m, n = len(grid), len(grid[0])
+        total = sum(sum(row) for row in grid)
+        if total % 2:
+            return False
+        target, s = total // 2, 0
+        for i in range(m - 1):
+            s += sum(grid[i])
+            if s == target:
+                return True
+        s = 0
+        for j in range(n - 1):
+            for i in range(m):
+                s += grid[i][j]
+            if s == target:
+                return True
+        return False
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.canPartitionGrid(grid=[[1, 4], [2, 3]]))
+    print(obj.canPartitionGrid(grid=[[1, 3], [2, 4]]))