commit c41c6f3448287f1a9db53c866f67ce7bce59b5a3
parent 9728c041cb2afd801c7a9c3c760fd374dcb8b35a
Author: Jack Sangdahl <jack@pngu.org>
Date: Sun, 15 Mar 2026 21:01:45 -0600
1878. get biggest three rhombus sums in a grid
Diffstat:
2 files changed, 157 insertions(+), 0 deletions(-)
diff --git a/biggest_three_rhombus_sum.c b/biggest_three_rhombus_sum.c
@@ -0,0 +1,98 @@
+// 1878. Get Biggest Three Rhombus Sums in a Grid
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' integer matrix 'grid'. a rhombus sum is the sum of
+ * the elements that form the border of regular rhombus shape in 'grid'. the
+ * rhombus must have the shape of a square rotated 45 degrees with each of the
+ * corners centered in a grid cell.
+ */
+
+void add_val(int *top, int val) {
+ if (val == top[0] || val == top[1] || val == top[2])
+ return;
+ if (val > top[0]) {
+ top[2] = top[1];
+ top[1] = top[0];
+ top[0] = val;
+ } else if (val > top[1]) {
+ top[2] = top[1];
+ top[1] = val;
+ } else if (val > top[2])
+ top[2] = val;
+}
+
+int *getBiggestThree(int **grid, int gridSize, int *gridColSize,
+ int *returnSize) {
+ int m = gridSize, n = gridColSize[0];
+ int top[3] = {-1, -1, -1};
+ for (int r = 0; r < m; ++r)
+ for (int c = 0; c < n; ++c) {
+ add_val(top, grid[r][c]);
+ int l = 1;
+ while (r + 2 * l < m && c - l >= 0 && c + l < n) {
+ int s = 0;
+ for (int i = 0; i < l; i++)
+ s += grid[r + i][c + i];
+ for (int i = 0; i < l; i++)
+ s += grid[r + l + i][c + l + i];
+ for (int i = 0; i < l; i++)
+ s += grid[r + 2 * l - i][c - i];
+ for (int i = 0; i < l; i++)
+ s += grid[r + l - i][c - l + i];
+ add_val(top, s);
+ l++;
+ }
+ }
+ int cnt = 0;
+ for (int i = 0; i < 3; i++)
+ if (top[i] != -1)
+ cnt++;
+ *returnSize = cnt;
+ int *ans = (int *)malloc(cnt * sizeof(int));
+ memcpy(ans, top, cnt * sizeof(int));
+ return ans;
+}
+
+int main() {
+ int g1i[6][6] = {{3, 4, 5, 1, 3},
+ {3, 3, 4, 2, 3},
+ {20, 30, 200, 40, 10},
+ {1, 5, 5, 4, 1},
+ {4, 3, 2, 2, 5}};
+ int g2i[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
+ int g3i[1][3] = {{7, 7, 7}};
+ int r1[] = {228, 219, 216}, rs1;
+ int r2[] = {20, 9, 8}, rs2;
+ int r3[] = {7}, rs3;
+ 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);
+ int *gbt1 = getBiggestThree(g1->arr, g1->row_size, g1->col_size, &rs1);
+ int *gbt2 = getBiggestThree(g2->arr, g2->row_size, g2->col_size, &rs2);
+ int *gbt3 = getBiggestThree(g3->arr, g3->row_size, g3->col_size, &rs3);
+ for (int i = 0; i < rs1; i++) {
+ printf("%d ", gbt1[i]);
+ assert(gbt1[i] == r1[i]);
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ printf("%d ", gbt2[i]);
+ assert(gbt2[i] == r2[i]);
+ }
+ printf("\n");
+ for (int i = 0; i < rs3; i++) {
+ printf("%d ", gbt3[i]);
+ assert(gbt3[i] == r3[i]);
+ }
+ printf("\n");
+ free(gbt1);
+ free(gbt2);
+ free(gbt3);
+ two_d_arr_free(g1);
+ two_d_arr_free(g2);
+ two_d_arr_free(g3);
+}
diff --git a/biggest_three_rhombus_sum.py b/biggest_three_rhombus_sum.py
@@ -0,0 +1,59 @@
+# 1878. Get Biggest Three Rhombus Sums in a Grid
+import heapq
+from typing import List
+
+"""
+you are given an 'm x n' integer matrix 'grid'. a rhombus sum is the sum of
+the elements that form the border of regular rhombus shape in 'grid'. the
+rhombus must have the shape of a square rotated 45 degrees with each of the
+corners centered in a grid cell.
+"""
+
+
+class Solution:
+ def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
+ m, n = len(grid), len(grid[0])
+ max_length = min((m - 1) // 2, (n - 1) // 2)
+ best = []
+ heapq.heapify(best)
+
+ def rhombus_sum(r, c, k):
+ result = grid[r][c]
+ for s in range(k):
+ r += 1
+ result += grid[r][c + s + 1]
+ result += grid[r][c - s - 1]
+ for s in range(k - 1, -1, -1):
+ r += 1
+ result += grid[r][c + s]
+ if s > 0:
+ result += grid[r][c - s]
+ return result
+
+ for r in range(m):
+ for c in range(n):
+ for k in range(max_length + 1):
+ if c >= k and c + k < n and r + 2 * k < m:
+ candidate = rhombus_sum(r, c, k)
+ if candidate not in set(best):
+ heapq.heappush(best, candidate)
+ if len(best) > 3:
+ heapq.heappop(best)
+ return sorted(best, reverse=True)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(
+ obj.getBiggestThree(
+ grid=[
+ [3, 4, 5, 1, 3],
+ [3, 3, 4, 2, 3],
+ [20, 30, 200, 40, 10],
+ [1, 5, 5, 4, 1],
+ [4, 3, 2, 2, 5],
+ ]
+ )
+ )
+ print(obj.getBiggestThree(grid=[[1, 2, 3], [4, 5, 6], [7, 8, 9]]))
+ print(obj.getBiggestThree(grid=[[7, 7, 7]]))
