Get Biggest Three Rhombus Sums in a Grid - Practice Coding Problems

Get Biggest Three Rhombus Sums in a Grid - Problem

Array Math Sorting Heap (Priority Queue) Matrix Prefix Sum Medium

You are given an m x n integer matrix grid.

A rhombus sum is the sum of the elements that form the border of a 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.

A rhombus can have an area of 0 (single cell), which means it consists of just one cell. The rhombus border includes all cells that form the diamond shape outline.

Return the biggest three distinct rhombus sums in the grid in descending order. If there are less than three distinct values, return all of them.

Input & Output

Example 1 — Basic Grid with Multiple Rhombuses

$ Input: 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]]

› Output: [228,216,211]

💡 Note: The largest rhombus sum is 228 (border of large diamond), followed by 216 and 211. We return the three biggest distinct values in descending order.

Example 2 — Small Grid

$ Input: grid = [[1,2,3],[4,5,6],[7,8,9]]

› Output: [20,16,13]

💡 Note: In a 3x3 grid, we can form various rhombuses. The largest sum is 20 from the border 2+6+8+4, then 16 and 13 from other diamond patterns.

Example 3 — Single Row

$ Input: grid = [[7,7,7]]

› Output: [7]

💡 Note: With only single cells possible, all rhombuses have the same sum of 7. We return only one distinct value.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 50
1 ≤ grid[i][j] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Grid

5x5 matrix with various integer values

Rhombus Formation

Diamond shapes with different centers and radii

Border Sum

Sum values along diamond borders, return top 3 distinct

Key Takeaway

🎯 Key Insight: Systematically enumerate all rhombus centers and radii to find diamond-shaped border sums

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that a rhombus is defined by its center point and radius. We systematically check every possible center and radius combination, calculate the border sum by tracing the diamond shape, and use a set to collect distinct values. Best approach uses set-based optimization with automatic duplicate handling. Time: O(m×n×min(m,n)), Space: O(k) where k is number of distinct sums.

Common Approaches

Approach	Time	Space	Notes
✓ Optimized with Set and Early Termination	O(m×n×min(m,n))	O(k)	Use set to avoid duplicate sums and optimize border calculation
Brute Force - Check All Rhombuses	O(m×n×min(m,n))	O(k)	Generate all possible rhombuses and calculate their border sums

Optimized with Set and Early Termination — Algorithm Steps

Step 1: Use set to store distinct sums automatically
Step 2: Optimize rhombus border traversal with single loop
Step 3: Calculate maximum possible radius per center efficiently
Step 4: Convert set to sorted array and take top 3

Visualization

Tap to expand

Step-by-Step Walkthrough

Set Storage

Use set to automatically eliminate duplicates

Optimized Border

More efficient rhombus border calculation

Direct Sort

Convert set to sorted array, take top 3

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SUMS 10000

int compare(const void *a, const void *b) {
    return (*(int*)b - *(int*)a);
}

int* solution(int** grid, int gridSize, int* gridColSize, int* returnSize) {
    if (gridSize == 0 || gridColSize[0] == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    int m = gridSize, n = gridColSize[0];
    int sums[MAX_SUMS];
    int sumCount = 0;
    
    // For each possible center
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // Calculate maximum radius from this center
            int maxR = i;
            if (j < maxR) maxR = j;
            if (m-1-i < maxR) maxR = m-1-i;
            if (n-1-j < maxR) maxR = n-1-j;
            
            for (int r = 0; r <= maxR; r++) {
                if (r == 0) {
                    // Single cell rhombus
                    sums[sumCount++] = grid[i][j];
                } else {
                    // Calculate rhombus sum for radius r
                    int total = 0;
                    // Four sides of the rhombus
                    for (int k = 0; k < r; k++) {
                        // Top side
                        total += grid[i-r+k][j+k];
                        // Right side
                        total += grid[i+k][j+r-k];
                        // Bottom side
                        total += grid[i+r-k][j-k];
                        // Left side
                        total += grid[i-k][j-r+k];
                    }
                    sums[sumCount++] = total;
                }
            }
        }
    }
    
    // Remove duplicates and sort
    qsort(sums, sumCount, sizeof(int), compare);
    
    int* result = (int*)malloc(3 * sizeof(int));
    int uniqueCount = 0;
    int prev = sums[0] + 1; // Different from first element
    
    for (int i = 0; i < sumCount && uniqueCount < 3; i++) {
        if (sums[i] != prev) {
            result[uniqueCount++] = sums[i];
            prev = sums[i];
        }
    }
    
    *returnSize = uniqueCount;
    return result;
}

int main() {
    // Simple test case
    int grid[3][5] = {{3,4,5,1,3},{3,3,4,2,3},{20,30,200,40,10}};
    int* gridPtr[3];
    int gridColSize[3];
    
    for (int i = 0; i < 3; i++) {
        gridPtr[i] = grid[i];
        gridColSize[i] = 5;
    }
    
    int returnSize;
    int* result = solution(gridPtr, 3, gridColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n×min(m,n))

Same as brute force but with optimized constants

✓ Linear Growth

Space Complexity

O(k)

Set stores distinct sums, at most k unique values

✓ Linear Space

23.0K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized with Set and Early Termination — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler