0888MediumArrayMathSortingHeap (Priority Queue)MatrixPrefix Sum

Three Best Diamond Outlines on a Board

Tracked in this browser only

Trains the technique from

LeetCode 1878Get Biggest Three Rhombus Sums in a Grid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A board of numbers is given as grid.

A diamond is picked by naming a top cell and a size. At size zero the diamond is that single cell. At size d the four corners sit at the top cell, d steps down-right of it, 2d steps straight down, and d steps down-left, and the diamond is the outline joining those four corners along the diagonals. A diamond counts only when it fits inside the board.

Each diamond has a weight: the total of the cells on its outline, corners counted once. Return the three largest distinct weights, largest first. Return every distinct weight, still largest first, when fewer than three exist.

Examples

Example 1

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, 6, 8]]
Output: [228, 216, 211]

The heaviest single cell is 200, then 40 and then 30, and no diamond outline of size one or more beats those three, so the three largest distinct weights come from single cells.

Example 2

Input: grid = [[6, 6, 6], [6, 6, 6], [6, 6, 6]]
Output: [24, 6]

Every cell holds 6, so the only weights are 6 from a single cell and 24 from the one outline of size one that fits. Two distinct weights exist, so both are returned.

Example 3

Input: grid = [[7]]
Output: [7]

A single cell is the only diamond on the board.

Constraints

1 <= grid.length <= 50
1 <= grid[i].length <= 50
Every row of grid has the same length
1 <= grid[i][j] <= 10^5

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def get_biggest_three(grid: list[list[int]]) -> list[int]:

Java

public int[] getBiggestThree(int[][] grid)

The intended approach

Time O(m * n * min(m, n)) for an m by n board: each diamond costs a constant amount of work.Space O(m * n) for the two running totals and the set of weights.

There are only about as many diamonds as cells times the largest size that fits, so they can all be looked at; the cost to avoid is walking each outline cell by cell. An outline is four diagonal runs, so build two running totals over the board, one along the down-right direction and one along the down-left. With those, any diagonal run's total is one subtraction, and an outline is four of them less the four corners, which each run counts twice. Collect every weight into a set so repeats collapse, then sort what is left downwards and take up to three.

Pythonentry point: get_biggest_three

def get_biggest_three(grid):
    m = len(grid)
    n = len(grid[0])
    # dr[i][j] totals the down-right run ending at grid[i - 1][j - 1]
    dr = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dr[i][j] = grid[i - 1][j - 1] + dr[i - 1][j - 1]
    # dl[i][j] totals the down-left run ending at grid[i - 1][j - 1]
    dl = [[0] * (n + 2) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            dl[i][j] = grid[i - 1][j - 1] + dl[i - 1][j + 1]

    def down_right(r1, c1, r2, c2):
        return dr[r2 + 1][c2 + 1] - dr[r1][c1]

    def down_left(r1, c1, r2, c2):
        return dl[r2 + 1][c2 + 1] - dl[r1][c1 + 2]

    weights = set()
    for r in range(m):
        for c in range(n):
            weights.add(grid[r][c])
            d = 1
            while r + 2 * d < m and c - d >= 0 and c + d < n:
                total = (down_right(r, c, r + d, c + d)
                         + down_left(r, c, r + d, c - d)
                         + down_left(r + d, c + d, r + 2 * d, c)
                         + down_right(r + d, c - d, r + 2 * d, c)
                         - grid[r][c] - grid[r + 2 * d][c]
                         - grid[r + d][c + d] - grid[r + d][c - d])
                weights.add(total)
                d += 1
    ranked = sorted(weights, reverse=True)
    return ranked[:3]

The obvious version

Look at every diamond and add up its outline one cell at a time, walking the four sides. Keeps every distinct weight, sorts them downwards and takes three. No running totals at all.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_get_biggest_three(grid):
    m = len(grid)
    n = len(grid[0])
    weights = set()
    for r in range(m):
        for c in range(n):
            weights.add(grid[r][c])
            d = 1
            while r + 2 * d < m and c - d >= 0 and c + d < n:
                total = 0
                for k in range(d):
                    total += grid[r + k][c + k]
                    total += grid[r + d + k][c + d - k]
                    total += grid[r + 2 * d - k][c - k]
                    total += grid[r + d - k][c - d + k]
                weights.add(total)
                d += 1
    ranked = sorted(weights, reverse=True)
    return ranked[:3]

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in