Get Biggest Three Rhombus Sums in a Grid LeetCode solution in Python

1
class Solution:
2
    def getBiggestThree(self, grid: List[List[int]]) -> List[int]:
3

4
        def calc(l, r, u, d):
5
            sc = 0
6
            c1 = c2 = (l + r) // 2
7
            expand = True
8
            for row in range(u, d + 1):
9
                if c1 == c2:
10
                    sc += grid[row][c1]
11
                else:
12
                    sc += grid[row][c1] + grid[row][c2]
13

14
                if c1 == l:
15
                    expand = False
16

17
                if expand:
18
                    c1 -= 1
19
                    c2 += 1
20
                else:
21
                    c1 += 1
22
                    c2 -= 1
23
            return sc
24

25
        m = len(grid)
26
        n = len(grid[0])
27
        heap = []
28
        for i in range(m):
29
            for j in range(n):
30
                l = r = j
31
                d = i
32
                while l >= 0 and r <= n - 1 and d <= m - 1:
33
                    sc = calc(l, r, i, d)
34
                    l -= 1
35
                    r += 1
36
                    d += 2
37
                    if len(heap) < 3:
38
                        if sc not in heap:
39
                            heapq.heappush(heap, sc)
40
                    else:
41
                        if sc not in heap and sc > heap[0]:
42
                            heapq.heappop(heap)
43
                            heapq.heappush(heap, sc)
44

45
        heap.sort(reverse=True)
46
        return heap