Get Biggest Three Rhombus Sums in a Grid

Medium
1566.

Get Biggest Three Rhombus Sums in a Grid

Get Biggest Three Rhombus Sums in a Grid is a medium coding problem on arrays, sorting and matrix, asked in Amazon and Google interviews.

You are given an m x n integer matrix grid. A rhombus is a square rotated 45° whose four corners sit at the centres of grid cells; a single cell counts as a rhombus of size 0. A rhombus with top corner (i, j) and size k has its other corners at (i+k, j+k), (i+2k, j) and (i+k, j-k), and must lie entirely inside the grid.

The rhombus sum is the sum of the cells on the rhombus's border only (the cells its four edges pass through), not the cells inside.

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

Example 1

Input
grid = [[5,1,2],[3,9,4],[1,6,7]]
Output
[14,9,7]
Explanation
The only rhombus of size 1 passes through 1, 4, 6 and 3 for a sum of 14; the largest single cells are 9 and 7.

Example 2

Input
grid = [[4,4,4]]
Output
[4]
Explanation
Every rhombus sum is 4, and duplicates count once.

Example 3

Input
grid = [[3,8]]
Output
[8,3]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number[]}
 */
var getBiggestThree = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Get Biggest Three Rhombus Sums in a Grid — Solution

Get Biggest Three Rhombus Sums in a Grid solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Get Biggest Three Rhombus Sums in a Grid is a medium coding problem on arrays, sorting and matrix, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Matrix, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an m x n integer matrix grid. A rhombus is a square rotated 45° whose four corners sit at the centres of grid cells; a single cell counts as a rhombus of size 0. A rhombus with top corner (i, j) and size k has its other corners at (i+k, j+k), (i+2k, j) and (i+k, j-k), and must lie entirely inside the grid.

The rhombus sum is the sum of the cells on the rhombus's border only (the cells its four edges pass through), not the cells inside.

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

Example 1

Input: grid = [[5,1,2],[3,9,4],[1,6,7]]
Output: [14,9,7]
Explanation: The only rhombus of size 1 passes through 1, 4, 6 and 3 for a sum of 14; the largest single cells are 9 and 7.

Example 2

Input: grid = [[4,4,4]]
Output: [4]
Explanation: Every rhombus sum is 4, and duplicates count once.

Example 3

Input: grid = [[3,8]]
Output: [8,3]

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 1 <= grid[i][j] <= 10^5

Hints for Get Biggest Three Rhombus Sums in a Grid

  1. Hint 1

    A rhombus is fixed by its top cell (i, j) and its size k; it fits when i + 2k < m, j - k >= 0 and j + k < n.

  2. Hint 2

    Its border has exactly 4k cells (1 when k = 0): walk the four edges, each k steps, without counting a corner twice.

  3. Hint 3

    Keep only the three largest distinct sums seen so far — no need to store them all.

How to solve Get Biggest Three Rhombus Sums in a Grid

Enumerate every rhombus by top corner and size, sum its border by walking four diagonal edges, and keep a running top-three of distinct values.

Approach

  1. For each cell (i, j), offer grid[i][j] (the size-0 rhombus).
  2. For k = 1, 2, … while i + 2k < m, j - k >= 0 and j + k < n: for t from 0 to k - 1 add grid[i+t][j+t] (top→right), grid[i+k+t][j+k-t] (right→bottom), grid[i+2k-t][j-t] (bottom→left) and grid[i+k-t][j-k+t] (left→top).
  3. Offer the sum to the top-three list: ignore it if already present, otherwise insert it in order and drop anything beyond three.
  4. Return the list.

Why it works

Each edge walk starts at one corner and stops just before the next, so the four walks cover the 4k border cells exactly once. Every rhombus inside the grid has a unique top corner and size, so all of them are offered, and the bounded list keeps exactly the three largest distinct values.

Complexity

  • Time — O(m · n · min(m, n)²) — diagonal prefix sums bring it to O(m · n · min(m, n))
  • Space — O(1)

Pitfalls

  • Corners belong to two edges; walk each edge half-open so they are counted once.
  • Sums must be distinct — equal sums from different rhombi count once.
  • A single cell is a valid rhombus of size 0.

Reference solution

Python

from typing import List

def getBiggestThree(grid: List[List[int]]) -> List[int]:
    m, n = len(grid), len(grid[0])
    top = []

    def offer(v):
        if v in top:
            return
        top.append(v)
        top.sort(reverse=True)
        if len(top) > 3:
            top.pop()

    for i in range(m):
        for j in range(n):
            offer(grid[i][j])
            k = 1
            while i + 2 * k < m and j - k >= 0 and j + k < n:
                s = 0
                for t in range(k):
                    s += grid[i + t][j + t]
                    s += grid[i + k + t][j + k - t]
                    s += grid[i + 2 * k - t][j - t]
                    s += grid[i + k - t][j - k + t]
                offer(s)
                k += 1
    return top

Java

public static int[] getBiggestThree(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    TreeSet<Integer> top = new TreeSet<>();
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            top.add(grid[i][j]);
            if (top.size() > 3) top.pollFirst();
            for (int k = 1; i + 2 * k < m && j - k >= 0 && j + k < n; k++) {
                int s = 0;
                for (int t = 0; t < k; t++) {
                    s += grid[i + t][j + t];
                    s += grid[i + k + t][j + k - t];
                    s += grid[i + 2 * k - t][j - t];
                    s += grid[i + k - t][j - k + t];
                }
                top.add(s);
                if (top.size() > 3) top.pollFirst();
            }
        }
    }
    int[] out = new int[top.size()];
    int idx = 0;
    for (int v : top.descendingSet()) out[idx++] = v;
    return out;
}

C++

vector<int> getBiggestThree(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    set<int> top;
    auto offer = [&](int v) {
        top.insert(v);
        if (top.size() > 3) top.erase(top.begin());
    };
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            offer(grid[i][j]);
            for (int k = 1; i + 2 * k < m && j - k >= 0 && j + k < n; k++) {
                int s = 0;
                for (int t = 0; t < k; t++) {
                    s += grid[i + t][j + t];
                    s += grid[i + k + t][j + k - t];
                    s += grid[i + 2 * k - t][j - t];
                    s += grid[i + k - t][j - k + t];
                }
                offer(s);
            }
        }
    }
    return vector<int>(top.rbegin(), top.rend());
}

JavaScript

var getBiggestThree = function(grid) {
    var m = grid.length, n = grid[0].length, top = [];
    var offer = function(v) {
        if (top.indexOf(v) >= 0) return;
        top.push(v);
        top.sort(function(a, b) { return b - a; });
        if (top.length > 3) top.pop();
    };
    for (var i = 0; i < m; i++) {
        for (var j = 0; j < n; j++) {
            offer(grid[i][j]);
            for (var k = 1; i + 2 * k < m && j - k >= 0 && j + k < n; k++) {
                var s = 0;
                for (var t = 0; t < k; t++) {
                    s += grid[i + t][j + t];
                    s += grid[i + k + t][j + k - t];
                    s += grid[i + 2 * k - t][j - t];
                    s += grid[i + k - t][j - k + t];
                }
                offer(s);
            }
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms