// Package q1878 implements a solution for https://leetcode.com/problems/get-biggest-three-rhombus-sums-in-a-grid/
package q1878

import "slices"

func getBiggestThree(grid [][]int) []int {
	w, h := len(grid[0]), len(grid)
	sums := make([][][2]int, h)
	sums[0] = make([][2]int, w*h)
	for s := h - 1; s >= 0; s-- {
		sums[s] = sums[0][s*w : (s+1)*w]
	}

	for r := range h {
		for c := range w {
			pR, pC := r-1, c-1
			if pR >= 0 && pC >= 0 {
				sums[r][c][0] = sums[pR][pC][0] + grid[r][c]
			} else {
				sums[r][c][0] = grid[r][c]
			}

			pR, pC = r-1, c+1
			if pR >= 0 && pC < w {
				sums[r][c][1] = sums[pR][pC][1] + grid[r][c]
			} else {
				sums[r][c][1] = grid[r][c]
			}
		}
	}

	biggest := []int{0, 0, 0, 0}
	var addResult = func(val int) {
		for i := 1; i <= 3; i++ {
			if biggest[i] == val {
				return
			}
		}
		biggest[0] = val
		slices.Sort(biggest)
	}

	var isValid = func(coord [2]int) bool {
		return coord[0] >= 0 && coord[1] >= 0 && coord[0] < h && coord[1] < w
	}

	for r := range h {
		for c := range w {
			addResult(grid[r][c])

			for edge := 2; ; edge++ {
				left := [2]int{r + edge - 1, c - edge + 1}
				right := [2]int{r + edge - 1, c + edge - 1}
				bottom := [2]int{r + (edge-1)*2, c}
				if !isValid(left) || !isValid(right) || !isValid(bottom) {
					break
				}

				e1 := sums[left[0]][left[1]][1] - sums[r][c][1]
				e2 := sums[bottom[0]][bottom[1]][0] - sums[left[0]][left[1]][0]
				e3 := sums[bottom[0]][bottom[1]][1] - sums[right[0]][right[1]][1]
				e4 := sums[right[0]][right[1]][0] - sums[r][c][0]
				addResult(e1 + e2 + e3 + e4 - grid[bottom[0]][bottom[1]] + grid[r][c])
			}
		}
	}

	for biggest = biggest[1:]; biggest[0] == 0; {
		biggest = biggest[1:]
	}
	slices.Reverse(biggest)
	return biggest
}

var _ = getBiggestThree