How hard is LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid?

LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid is rated Medium on LeetCode.

What is the time complexity of LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid?

The Python solution on this page runs in O(m \times n \times \min(m, n)).

What is the space complexity of LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid?

The Python solution on this page uses O(m \times n) auxiliary space.

What topics does LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid cover?

LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid is tagged Array, Math, Matrix, Prefix Sum, Sorting and Heap (Priority Queue) on LeetCode.

Get Biggest Three Rhombus Sums in a Grid — LeetCode 1878 Python Solution

MediumArrayMathMatrixPrefix SumSortingHeap (Priority Queue)

Problem: #1878
Pattern: Prefix Sum
Reading time: 5 min
Source: leetcode.com

The problem

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.

Example

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]
Explanation: The rhombus shapes for the three biggest distinct rhombus sums are depicted above.

Python solution

Python

class Solution:
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        s1 = [[0] * (n + 2) for _ in range(m + 1)]
        s2 = [[0] * (n + 2) for _ in range(m + 1)]
        for i, row in enumerate(grid, 1):
            for j, x in enumerate(row, 1):
                s1[i][j] = s1[i - 1][j - 1] + x
                s2[i][j] = s2[i - 1][j + 1] + x
        ss = SortedSet()
        for i, row in enumerate(grid, 1):
            for j, x in enumerate(row, 1):
                l = min(i - 1, m - i, j - 1, n - j)
                ss.add(x)
                for k in range(1, l + 1):
                    a = s1[i + k][j] - s1[i][j - k]
                    b = s1[i][j + k] - s1[i - k][j]
                    c = s2[i][j - k] - s2[i - k][j]
                    d = s2[i + k][j] - s2[i][j + k]
                    ss.add(
                        a + b + c + d - grid[i + k - 1][j - 1] + grid[i - k - 1][j - 1]
                    )
                while len(ss) > 3:
                    ss.remove(ss[0])
        return list(ss)[::-1]

Complexity

Measure	Complexity
Time	O(m \times n \times \min(m, n))
Space	O(m \times n) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid?: LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid is rated Medium on LeetCode.
What is the time complexity of LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid?: The Python solution on this page runs in O(m \times n \times \min(m, n)).
What is the space complexity of LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid?: The Python solution on this page uses O(m \times n) auxiliary space.
What topics does LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid cover?: LeetCode 1878. Get Biggest Three Rhombus Sums in a Grid is tagged Array, Math, Matrix, Prefix Sum, Sorting and Heap (Priority Queue) on LeetCode.