// Package q3548 implements a solution for https://leetcode.com/problems/equal-sum-grid-partition-ii/
package q3548

func findNumber(
	num int,
	r1, c1, r2, c2 int,
	byVal map[int][][2]int32,
	grid [][]int,
) bool {
	w, h := c2-c1+1, r2-r1+1
	if w == 1 || h == 1 {
		return grid[r1][c1] == num || grid[r2][c2] == num
	}
	for _, coord := range byVal[num] {
		r, c := int(coord[0]), int(coord[1])
		if r >= r1 && r <= r2 && c >= c1 && c <= c2 {
			return true
		}
	}
	return false
}

func canPartitionGrid(grid [][]int) bool {
	w, h := len(grid[0]), len(grid)
	hSums, vSums := make([]int, w), make([]int, h)
	sumAll := 0
	byVal := make(map[int][][2]int32, w*h)

	for r := range h {
		for c := range w {
			val := grid[r][c]
			hSums[c] += val
			vSums[r] += val
			sumAll += val
			byVal[val] = append(byVal[val], [2]int32{int32(r), int32(c)})
		}
	}

	// Check vertical cuts
	sum := 0
	for i := range w - 1 {
		sum += hSums[i]
		rem := sumAll - sum
		if sum > rem {
			if findNumber(sum-rem, 0, 0, h-1, i, byVal, grid) {
				return true
			}
		} else if sum < rem {
			if findNumber(rem-sum, 0, i+1, h-1, w-1, byVal, grid) {
				return true
			}
		} else {
			return true
		}
	}

	// Check horizontal cuts
	sum = 0
	for i := range h - 1 {
		sum += vSums[i]
		rem := sumAll - sum
		if sum > rem {
			if findNumber(sum-rem, 0, 0, i, w-1, byVal, grid) {
				return true
			}
		} else if sum < rem {
			if findNumber(rem-sum, i+1, 0, h-1, w-1, byVal, grid) {
				return true
			}
		} else {
			return true
		}
	}

	return false
}

var _ = canPartitionGrid