commit c2626ccd050dd852b59d63a97529978b1e4ade9a
parent 65d4c333e07eaa581033ab4295e79db2687235f5
Author: Jack Sangdahl <jack@pngu.org>
Date: Wed, 25 Mar 2026 21:45:34 -0600
3548. equal sum grid partition 2
Diffstat:
2 files changed, 225 insertions(+), 0 deletions(-)
diff --git a/equal_sum_grid_partition2.c b/equal_sum_grid_partition2.c
@@ -0,0 +1,157 @@
+// 3548. Equal Sum Grid Partition II
+#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, the sum of the elements in both sections is equal or can be made
+ * equal by discounting at most one single cell in total, and if a cell is
+ * discounted, the rest of the section must remain connected. return 'true' if
+ * such a partition exists, otherwise return false.
+ */
+
+struct hash_item {
+ long long key;
+ UT_hash_handle hh;
+};
+
+static inline struct hash_item *hash_find_item(struct hash_item **obj,
+ long long key) {
+ struct hash_item *p_entry = NULL;
+ HASH_FIND(hh, *obj, &key, sizeof(key), p_entry);
+ return p_entry;
+}
+
+bool hash_add_item(struct hash_item **obj, long long key) {
+ if (hash_find_item(obj, key))
+ return false;
+ struct hash_item *p_entry =
+ (struct hash_item *)malloc(sizeof(struct hash_item));
+ p_entry->key = key;
+ HASH_ADD(hh, *obj, key, sizeof(key), p_entry);
+ return true;
+}
+
+void hash_free(struct hash_item **obj) {
+ struct hash_item *curr, *tmp;
+ HASH_ITER(hh, *obj, curr, tmp) {
+ HASH_DEL(*obj, curr);
+ free(curr);
+ }
+ *obj = NULL;
+}
+
+int **rotation(int **grid, int m, int n, int *new_m, int *new_n) {
+ *new_m = n;
+ *new_n = m;
+ int **res = (int **)malloc(n * sizeof(int *));
+ int *data = (int *)malloc(n * m * sizeof(int));
+ for (int i = 0; i < n; i++)
+ res[i] = data + i * m;
+ for (int i = 0; i < m; i++)
+ for (int j = 0; j < n; j++)
+ res[j][m - 1 - i] = grid[i][j];
+ return res;
+}
+
+void free_grid(int **grid, int n) {
+ if (grid && grid[0])
+ free(grid[0]);
+ free(grid);
+}
+
+static inline bool check(struct hash_item **exist, int **curr, int curr_m,
+ int **original) {
+ hash_free(exist);
+ if (curr != original)
+ free_grid(curr, curr_m);
+ return true;
+}
+
+static inline void rotate_update(int ***curr_grid, int *curr_m, int *curr_n,
+ int **original) {
+ int new_m, new_n;
+ int **new_grid = rotation(*curr_grid, *curr_m, *curr_n, &new_m, &new_n);
+ if (*curr_grid != original)
+ free_grid(*curr_grid, *curr_m);
+ *curr_grid = new_grid;
+ *curr_m = new_m;
+ *curr_n = new_n;
+}
+
+bool canPartitionGrid(int **grid, int gridSize, int *gridColSize) {
+ const 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];
+ int curr_m = m, curr_n = n, **curr_grid = grid;
+ for (int k = 0; k < 4; k++) {
+ struct hash_item *exist = NULL;
+ hash_add_item(&exist, 0LL);
+ long long sum = 0;
+ if (curr_m < 2 || curr_n == 1) {
+ if (curr_n == 1 && curr_m >= 2)
+ for (int i = 0; i < curr_m - 1; i++) {
+ sum += curr_grid[i][0];
+ long long tag = sum * 2 - total;
+ if (!tag || tag == curr_grid[0][0] || tag == curr_grid[i][0])
+ return check(&exist, curr_grid, curr_m, grid);
+ }
+ rotate_update(&curr_grid, &curr_m, &curr_n, grid);
+ hash_free(&exist);
+ continue;
+ }
+ for (int i = 0; i < curr_m - 1; i++) {
+ for (int j = 0; j < curr_n; j++) {
+ hash_add_item(&exist, (long long)curr_grid[i][j]);
+ sum += curr_grid[i][j];
+ }
+ long long tag = sum * 2 - total;
+ if (!i) {
+ if (!tag || tag == curr_grid[0][0] || tag == curr_grid[0][curr_n - 1])
+ return check(&exist, curr_grid, curr_m, grid);
+ continue;
+ }
+ if (hash_find_item(&exist, tag))
+ return check(&exist, curr_grid, curr_m, grid);
+ }
+ rotate_update(&curr_grid, &curr_m, &curr_n, grid);
+ hash_free(&exist);
+ }
+ if (curr_grid != grid)
+ free_grid(curr_grid, curr_m);
+ return false;
+}
+
+int main() {
+ int g1i[2][2] = {{1, 4}, {2, 3}};
+ int g2i[2][2] = {{1, 2}, {3, 4}};
+ int g3i[2][3] = {{1, 2, 4}, {2, 3, 5}};
+ int g4i[2][3] = {{4, 1, 8}, {3, 2, 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);
+ struct two_d_arr *g3 =
+ two_d_arr_init(ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i);
+ struct two_d_arr *g4 =
+ two_d_arr_init(ARRAY_SIZE(g4i), ARRAY_SIZE(g4i[0]), g4i);
+ bool r1 = canPartitionGrid(g1->arr, g1->row_size, g1->col_size);
+ bool r2 = canPartitionGrid(g2->arr, g2->row_size, g2->col_size);
+ bool r3 = canPartitionGrid(g3->arr, g3->row_size, g3->col_size);
+ bool r4 = canPartitionGrid(g4->arr, g4->row_size, g4->col_size);
+ printf("%d\n", r1);
+ assert(r1 == true);
+ printf("%d\n", r2);
+ assert(r2 == true);
+ printf("%d\n", r3);
+ assert(r3 == false);
+ printf("%d\n", r4);
+ assert(r4 == false);
+ two_d_arr_free(g1);
+ two_d_arr_free(g2);
+ two_d_arr_free(g3);
+ two_d_arr_free(g4);
+}
diff --git a/equal_sum_grid_partition2.py b/equal_sum_grid_partition2.py
@@ -0,0 +1,68 @@
+# 3548. Equal Sum Grid Partition II
+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, the sum of the elements in both sections is equal or can be made
+equal by discounting at most one single cell in total, and if a cell is
+discounted, the rest of the section must remain connected. return 'true' if
+such a partition exists, otherwise return false.
+"""
+
+
+class Solution:
+ def canPartitionGrid(self, grid: List[List[int]]) -> bool:
+ m, n = len(grid), len(grid[0])
+ total = 0
+ for i in range(m):
+ for j in range(n):
+ total += grid[i][j]
+ for _ in range(4):
+ exist = set()
+ exist.add(0)
+ sum_val = 0
+ m = len(grid)
+ n = len(grid[0])
+ if m < 2:
+ grid = self.rotation(grid)
+ continue
+ if n == 1:
+ for i in range(m - 1):
+ sum_val += grid[i][0]
+ tag = sum_val * 2 - total
+ if tag == 0 or tag == grid[0][0] or tag == grid[i][0]:
+ return True
+ grid = self.rotation(grid)
+ continue
+ for i in range(m - 1):
+ for j in range(n):
+ exist.add(grid[i][j])
+ sum_val += grid[i][j]
+ tag = sum_val * 2 - total
+ if i == 0:
+ if tag == 0 or tag == grid[0][0] or tag == grid[0][n - 1]:
+ return True
+ continue
+ if tag in exist:
+ return True
+ grid = self.rotation(grid)
+ return False
+
+ def rotation(self, grid: List[List[int]]) -> List[List[int]]:
+ m = len(grid)
+ n = len(grid[0])
+ tmp = [[0] * m for _ in range(n)]
+ for i in range(m):
+ for j in range(n):
+ tmp[j][m - 1 - i] = grid[i][j]
+ return tmp
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.canPartitionGrid(grid=[[1, 4], [2, 3]]))
+ print(obj.canPartitionGrid(grid=[[1, 2], [3, 4]]))
+ print(obj.canPartitionGrid(grid=[[1, 2, 4], [2, 3, 5]]))
+ print(obj.canPartitionGrid(grid=[[4, 1, 8], [3, 2, 6]]))
