leetcode

commit 387b3ecf24e20ffaaafcf111654b04e14ffd7704
parent b45100910d72e0ba3d6e359357a629bd34635a13
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon, 29 Dec 2025 17:15:47 -0700

840. magic squares in grid

Diffstat:
M
magic_squares_grid.c
 | 
65
+++++++++++++++++++++++++++++++++--------------------------------

1 file changed, 33 insertions(+), 32 deletions(-)
diff --git a/magic_squares_grid.c b/magic_squares_grid.c
@@ -9,50 +9,51 @@
  * 'grid' may contain numbers up to 15.
  */
 
-bool check(int **grid, int row, int col, int *map) {
-  for (int i = 0; i < 3; i++)
-    for (int j = 0; j < 3; j++) {
-      map[grid[row + i][col + j]]++;
-      if (map[grid[row + i][col + j]] > 1 || grid[row + i][col + j] > 9 ||
-          grid[row + i][col + j] == 0)
+bool valid(int i, int j, int **grid) {
+  int cnt[10] = {0};
+  for (int x = 0; x < 3; ++x)
+    for (int y = 0; y < 3; ++y) {
+      int curr = grid[i + x][j + y];
+      if (curr < 1 || curr > 9 || cnt[curr] > 0)
         return false;
+      cnt[curr]++;
     }
-  int a = grid[row][col] + grid[row][col + 1] + grid[row][col + 2];
-  int b = grid[row + 1][col] + grid[row + 1][col + 1] + grid[row + 1][col + 2];
-  int c = grid[row + 2][col] + grid[row + 2][col + 1] + grid[row + 2][col + 2];
-  if (a != 15 || b != 15 || c != 15)
+  int sum = grid[i][j] + grid[i][j + 1] + grid[i][j + 2];
+  for (int x = 0; x < 3; ++x)
+    if (sum != (grid[i + x][j] + grid[i + x][j + 1] + grid[i + x][j + 2]))
+      return false;
+  for (int y = 0; y < 3; ++y)
+    if (sum != (grid[i][j + y] + grid[i + 1][j + y] + grid[i + 2][j + y]))
+      return false;
+  if (sum != (grid[i][j] + grid[i + 1][j + 1] + grid[i + 2][j + 2]))
     return false;
-  int d = grid[row][col] + grid[row + 1][col] + grid[row + 2][col];
-  int e = grid[row][col + 1] + grid[row + 1][col + 1] + grid[row + 2][col + 1];
-  int f = grid[row][col + 2] + grid[row + 1][col + 2] + grid[row + 2][col + 2];
-  if (d != 15 || e != 15 || f != 15)
-    return false;
-  int g = grid[row][col] + grid[row + 1][col + 1] + grid[row + 2][col + 2];
-  int h = grid[row][col + 2] + grid[row + 1][col + 1] + grid[row + 2][col];
-  if (g != 15 || h != 15)
+  if (sum != (grid[i + 2][j] + grid[i + 1][j + 1] + grid[i][j + 2]))
     return false;
   return true;
 }
 
 int numMagicSquaresInside(int **grid, int gridSize, int *gridColSize) {
-  if (gridSize < 3 || gridColSize[0] < 3)
+  int cnt = 0, n = gridSize, m = gridColSize[0];
+  if (n < 3 || m < 3)
     return 0;
-  int *map = (int *)calloc(16, sizeof(int)), cnt = 0;
-  for (int i = 0; i + 2 < gridSize; i++)
-    for (int j = 0; j + 2 < gridColSize[0]; j++) {
-      if (check(grid, i, j, map))
+  for (int i = 0; i <= n - 3; ++i)
+    for (int j = 0; j <= m - 3; ++j)
+      if (valid(i, j, grid))
         cnt++;
-      memset(map, 0, 16 * sizeof(int));
-    }
-  free(map);
   return cnt;
 }
 
 int main() {
-  int g1[3][4] = {{4, 3, 8, 4}, {9, 5, 1, 9}, {2, 7, 6, 2}}, g2[1][1] = {{8}},
-      gcs1 = 3, gcs2 = 1;
-  printf("%d\n",
-         numMagicSquaresInside((int **)g1, ARRAY_SIZE(g1), &gcs1)); // expect: 1
-  printf("%d\n",
-         numMagicSquaresInside((int **)g2, ARRAY_SIZE(g2), &gcs2)); // expect: 0
+  int g1i[3][4] = {{4, 3, 8, 4}, {9, 5, 1, 9}, {2, 7, 6, 2}};
+  int g2i[1][1] = {{8}};
+  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);
+  printf("%d\n", numMagicSquaresInside(g1->arr, g1->row_size,
+                                       g1->col_size)); // expect: 1
+  printf("%d\n", numMagicSquaresInside(g2->arr, g2->row_size,
+                                       g2->col_size)); // expect: 1
+  two_d_arr_free(g1);
+  two_d_arr_free(g2);
 }