Two Rooks Maximum Non-Attacking Sum

An electronic market routing optimization challenge at Hudson River Trading (HRT) models order routing allocations across an $M \times N$ grid of latency-yield scores grid.

You must place two non-attacking rooks on two distinct cells $(r_1, c_1)$ and $(r_2, c_2)$ of the grid such that they do not share the same row or column: $r_1 \ne r_2 \quad \text{and} \quad c_1 \ne c_2$

Your Task

Implement two_rooks_max_sum(grid: list[list[int]]) -> int that returns the maximum possible sum of yields $grid[r_1][c_1] + grid[r_2][c_2]$ in $\mathcal{O}(M \cdot N)$ time.

Constraints

• $2 \le M, N \le 1000$
• $0 \le grid[i][j] \le 10^9$

Examples

grid = [
    [1, 4, 3],
    [2, 5, 6],
    [3, 8, 2]
]
# Best pair: (2, 1) with value 8, and (1, 2) with value 6.
# Rows 2 != 1 and Columns 1 != 2.
# Sum = 8 + 6 = 14
# Output: 14