Algorithm
Get Biggest Three Rhombus Sums in a Grid
Solution
for r in range(m):
for c in range(n):
ans.put(grid[r][c]) # Size 0 rhombus
# Expand size L
for L in range(1, min(m, n)):
# Check if the shape fits in the grid
if r + 2 * L >= m or c - L < 0 or c + L >= n:
break
# Calculate the 4 edges instantly using prefix sums
edge1 = sum2[r + L + 1][c - L + 1] - sum2[r + 1][c + 1] # Top -> Left
edge2 = sum1[r + 2 * L + 1][c + 1] - sum1[r + L + 1][c - L + 1] # Left -> Bottom
edge3 = sum1[r + L + 1][c + L + 1] - sum1[r + 1][c + 1] # Top -> Right
edge4 = sum2[r + 2 * L + 1][c + 1] - sum2[r + L + 1][c + L + 1] # Right -> Bottom
# Total = all edges + Top point - Bottom point
total = edge1 + edge2 + edge3 + edge4 + grid[r][c] - grid[r + 2 * L][c]
ans.put(total)
return ans.get()Video GuideLeetcode Daily
Time Complexity
O(m * n * min(m, n)
Space Complexity
O(m * n)
