# Maximum Value Sum by Placing Three Rooks II
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-value-sum-by-placing-three-rooks-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximum-value-sum-by-placing-three-rooks-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Matrix
---
## Problem
You are given a `m x n` 2D array `board` representing a chessboard, where `board[i][j]` represents the **value** of the cell `(i, j)`.

Rooks in the **same** row or column **attack** each other. You need to place _three_ rooks on the chessboard such that the rooks **do not** **attack** each other.

Return the **maximum** sum of the cell **values** on which the rooks are placed.

**Example 1:**

**Input:** board = \[\[-3,1,1,1\],\[-3,1,-3,1\],\[-3,2,1,1\]\]

**Output:** 4

**Explanation:**

![](https://assets.glich.co/dsa/maximum-value-sum-by-placing-three-rooks-ii/image0.png)

We can place the rooks in the cells `(0, 2)`, `(1, 3)`, and `(2, 1)` for a sum of `1 + 1 + 2 = 4`.

**Example 2:**

**Input:** board = \[\[1,2,3\],\[4,5,6\],\[7,8,9\]\]

**Output:** 15

**Explanation:**

We can place the rooks in the cells `(0, 0)`, `(1, 1)`, and `(2, 2)` for a sum of `1 + 5 + 9 = 15`.

**Example 3:**

**Input:** board = \[\[1,1,1\],\[1,1,1\],\[1,1,1\]\]

**Output:** 3

**Explanation:**

We can place the rooks in the cells `(0, 2)`, `(1, 1)`, and `(2, 0)` for a sum of `1 + 1 + 1 = 3`.

**Constraints:**

* `3 <= m == board.length <= 500`
* `3 <= n == board[i].length <= 500`
* `-109 <= board[i][j] <= 109`

# Approaches
## Brute-force by Iterating Through Three Rows
This approach uses brute force by systematically checking every possible valid placement of three rooks. Since the rooks cannot attack each other, they must be in distinct rows and distinct columns. The algorithm iterates through all possible combinations of three distinct rows. For each combination of rows, it then finds the optimal placement of rooks in three distinct columns to maximize the sum.
**Time:** O(m^3 * n) · **Space:** O(n)
**Pros:** The logic is straightforward and easy to understand.; It correctly explores all valid configurations of rooks.
**Cons:** The time complexity is very high, making it impractical for the given constraints.; It is highly inefficient as it recomputes information repeatedly.
### Explanation
The core idea is to break down the problem by first choosing the rows for the three rooks. There are `O(m^3)` ways to choose three distinct rows. For each set of three rows, say `r1`, `r2`, and `r3`, we need to choose three distinct columns `c1`, `c2`, and `c3` to maximize `board[r1][c1] + board[r2][c2] + board[r3][c3]` (or any permutation of columns). This is an assignment problem on a `3 x n` matrix, which can be solved efficiently.

For a fixed set of three rows, we can find the best combination of three columns in `O(n)` time. One way to do this is to find the columns with the top few largest values for each of the three rows and then test their combinations. For instance, finding the top 3 columns for each of the three rows takes `O(n)`. Then, we can check the `3 * 3 * 3 = 27` possible pairings to find the one with distinct columns that yields the maximum sum.

Combining these, the total time complexity becomes `O(m^3 * n)`.

```java
class Solution {
    public long maximumValueSum(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        long maxSum = 0;

        if (m < 3 || n < 3) {
            return 0;
        }

        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                for (int r3 = r2 + 1; r3 < m; r3++) {
                    // For fixed r1, r2, r3, find max sum with distinct columns
                    long currentMax = findMaxSumForThreeRows(board, r1, r2, r3);
                    maxSum = Math.max(maxSum, currentMax);
                }
            }
        }
        return maxSum;
    }

    private long findMaxSumForThreeRows(int[][] board, int r1, int r2, int r3) {
        int n = board[0].length;
        // Find top 3 columns for each row
        Pair[] top_r1 = getTopN(board[r1], 3);
        Pair[] top_r2 = getTopN(board[r2], 3);
        Pair[] top_r3 = getTopN(board[r3], 3);

        long max = 0;
        for (Pair p1 : top_r1) {
            for (Pair p2 : top_r2) {
                for (Pair p3 : top_r3) {
                    if (p1.index != p2.index && p1.index != p3.index && p2.index != p3.index) {
                        max = Math.max(max, p1.value + p2.value + p3.value);
                    }
                }
            }
        }
        return max;
    }

    private Pair[] getTopN(int[] row, int N) {
        java.util.PriorityQueue<Pair> pq = new java.util.PriorityQueue<>((a, b) -> Long.compare(a.value, b.value));
        for (int i = 0; i < row.length; i++) {
            pq.offer(new Pair(row[i], i));
            if (pq.size() > N) {
                pq.poll();
            }
        }
        Pair[] result = new Pair[pq.size()];
        int i = 0;
        while(!pq.isEmpty()) {
            result[i++] = pq.poll();
        }
        return result;
    }

    class Pair {
        long value;
        int index;
        Pair(long value, int index) {
            this.value = value;
            this.index = index;
        }
    }
}
```
### Algorithm
1. Initialize a variable `maxSum` to a very small number.
2. Iterate through all possible combinations of three distinct rows `r1`, `r2`, and `r3` from `0` to `m-1`. This can be done with three nested loops.
3. For each combination of three rows, we solve a subproblem: find the maximum sum by picking three rooks, one from each of these rows, such that they are in distinct columns.
4. Let the three chosen rows be `r1`, `r2`, `r3`. We define three arrays `A[c] = board[r1][c]`, `B[c] = board[r2][c]`, and `C[c] = board[r3][c]` for `c` from `0` to `n-1`.
5. The subproblem is now to find `max_{i, j, k are distinct} (A[i] + B[j] + C[k])`.
6. This subproblem can be solved in `O(n)` time. A simple way is to find the top 3 columns for each of the three rows. Let's say for row `r1`, the top 3 columns are `c11, c12, c13`. Similarly for `r2` and `r3`. Then, we can check all `3*3*3 = 27` combinations of these top columns, and for each combination where the column indices are distinct, we calculate the sum and update the maximum.
7. After checking all combinations of three rows, `maxSum` will hold the result.

## Iterating over Two Rows
This approach improves upon the brute-force method by reducing the number of nested loops. Instead of iterating through three rows, we iterate through all possible pairs of two rows. For each pair of rows, we determine the best possible third rook and the best columns for the chosen two rows. This reduces one dimension of the search space, leading to a better time complexity.
**Time:** O(m^2 * n) (assuming m <= n) · **Space:** O(m*n) or O(n) depending on precomputation strategy.
**Pros:** Significantly more efficient than the `O(m^3 * n)` brute-force approach.; Reduces the problem to a well-defined subproblem (3-array sum).
**Cons:** Still too slow for the given constraints of `m, n <= 500`.; The implementation is more complex than the brute-force approach.
### Explanation
We fix two rows, `r1` and `r2`, for the first two rooks. There are `O(m^2)` such pairs. For each pair, we need to select two distinct columns `c1` and `c2` for these rooks, and a third rook at `(r3, c3)` where `r3` is not `r1` or `r2`, and `c3` is not `c1` or `c2`.

The problem for a fixed `(r1, r2)` is to maximize `board[r1][c1] + board[r2][c2] + board[r3][c3]`. This can be viewed as a 3-array sum problem. Let `A[c] = board[r1][c]`, `B[c] = board[r2][c]`, and `C[c] = max_{k \notin \{r1,r2\}} board[k][c]`. We need to find `max_{i,j,k \text{ distinct}} (A[i] + B[j] + C[k])`.

To compute the array `C` efficiently, we can precompute the top 3 values for each column of the board. This precomputation takes `O(m*n)`. Then, for each pair `(r1, r2)`, we can construct `C` in `O(n)` time. The 3-array sum problem can be solved in `O(n)`. Thus, the total complexity is dominated by iterating through pairs of rows, resulting in `O(m^2 * n)`.

```java
// This is a conceptual illustration. A full implementation would be lengthy.
// The core logic relies on solving the 3-array sum problem efficiently.
class Solution {
    // Assuming a helper function solve3ArraySum(long[] A, long[] B, long[] C) exists,
    // which solves max(A[i] + B[j] + C[k]) over distinct i,j,k in O(n) time.
    public long maximumValueSum(int[][] board) {
        int m = board.length;
        int n = board[0].length;
        long maxSum = 0;

        // Precompute top 3 values for each column
        // colTop3[c] would store pairs of (value, rowIndex)
        Pair[][] colTop3 = new Pair[n][3];
        // ... O(m*n) precomputation logic ...

        for (int r1 = 0; r1 < m; r1++) {
            for (int r2 = r1 + 1; r2 < m; r2++) {
                long[] A = new long[n];
                long[] B = new long[n];
                long[] C = new long[n];
                for(int c=0; c<n; c++) {
                    A[c] = board[r1][c];
                    B[c] = board[r2][c];
                    // Build C[c] using precomputed colTop3
                    // Find max in col c, excluding r1 and r2
                    long maxVal = Long.MIN_VALUE;
                    for(Pair p : colTop3[c]) {
                        if (p.index != r1 && p.index != r2) {
                            maxVal = p.value;
                            break;
                        }
                    }
                    C[c] = maxVal;
                }
                // maxSum = Math.max(maxSum, solve3ArraySum(A, B, C));
            }
        }
        return maxSum;
    }
    // Pair class and solve3ArraySum implementation would be needed.
}
```
### Algorithm
1. The problem is symmetric with respect to rows and columns. Assume `m <= n` without loss of generality, and we will iterate over rows. If `n < m`, we can transpose the board or iterate over columns instead.
2. Precompute for each column `c`, the top 3 values and their corresponding row indices. This takes `O(m*n)` time.
3. Initialize `maxSum` to a very small number.
4. Iterate through all pairs of distinct rows `r1` and `r2`. This is `O(m^2)` combinations.
5. For each pair of rows `(r1, r2)`, we want to find the best third rook `(r3, c3)` and the best columns `c1, c2` for rows `r1, r2`.
6. The sum is `board[r1][c1] + board[r2][c2] + board[r3][c3]`. We can rearrange this as `board[r1][c1] + board[r2][c2] + max_{r3' \notin \{r1,r2\}} board[r3'][c3]`, where `c1, c2, c3` must be distinct.
7. For the fixed `r1, r2`, create a third array `C` where `C[c] = max_{k \notin \{r1,r2\}} board[k][c]`. This array can be constructed in `O(n)` using the precomputed column-wise top-3 values.
8. Now, solve the 3-array sum problem for `A=board[r1]`, `B=board[r2]`, and `C`. This can be done in `O(n)` time.
9. Update `maxSum` with the result from the subproblem.
10. The total time complexity will be `O(m*n + m^2 * n) = O(m^2 * n)`.

## Dynamic Programming by Fixing the Middle Rook's Row
This is the most efficient approach, which uses dynamic programming and a clever partitioning of the problem. Instead of fixing the rooks themselves, we fix the row of one of the rooks and realize that the other two must be on opposite sides of it (one in a row with a smaller index, one with a larger index). This insight allows us to precompute necessary maximums and solve the problem in linear time with respect to the number of cells.
**Time:** O(m*n) · **Space:** O(m*n) for the precomputed `top` and `bottom` tables.
**Pros:** Optimal time complexity, making it very fast for the given constraints.; The DP state transition is clean and builds upon precomputed values efficiently.
**Cons:** The implementation is complex, requiring careful handling of indices and edge cases.; Requires significant auxiliary space for the precomputed tables.
### Explanation
The algorithm iterates through each possible row `r` (from `1` to `m-2`) that could serve as the row for the middle rook. For a fixed `r`, one rook must be placed in a row `i < r` and the other in a row `j > r`. The columns for these three rooks, `c_i`, `c_r`, `c_j`, must be distinct.

To find the optimal placement for a given `r`, we want to maximize `board[i][c_i] + board[r][c_r] + board[j][c_j]`. This can be decoupled as `(max_{i<r} board[i][c_i]) + board[r][c_r] + (max_{j>r} board[j][c_j])`.

We can precompute `top[r][c] = max_{i<r} board[i][c]` and `bottom[r][c] = max_{j>r} board[j][c]` for all `r, c` in `O(m*n)`. 

Now, for each middle row `r`, we solve: `max_{c1,c2,c3 distinct} (top[r][c1] + board[r][c2] + bottom[r][c3])`. This is a 3-array sum problem that can be solved in `O(n)`. We iterate through `c2` from `0` to `n-1`. For each `c2`, we need to find the best `c1` and `c3` from the remaining columns. This subproblem `max_{c1,c3 != c2, c1!=c3} (top[r][c1] + bottom[r][c3])` can be solved in `O(1)` by precomputing prefix/suffix top-2 values for the `top[r]` and `bottom[r]` arrays.

Since we do this for each of the `m` rows, the total time complexity is `O(m*n)`. 

```java
class Solution {
    class Pair {
        long val;
        int idx;
        Pair(long val, int idx) {
            this.val = val;
            this.idx = idx;
        }
    }

    public long maximumValueSum(int[][] board) {
        int m = board.length;
        int n = board[0].length;

        long[][] top = new long[m][n];
        for (int c = 0; c < n; c++) top[0][c] = Long.MIN_VALUE;
        for (int r = 1; r < m; r++) {
            for (int c = 0; c < n; c++) {
                top[r][c] = Math.max(top[r - 1][c], board[r - 1][c]);
            }
        }

        long[][] bottom = new long[m][n];
        for (int c = 0; c < n; c++) bottom[m - 1][c] = Long.MIN_VALUE;
        for (int r = m - 2; r >= 0; r--) {
            for (int c = 0; c < n; c++) {
                bottom[r][c] = Math.max(bottom[r + 1][c], board[r + 1][c]);
            }
        }

        long maxSum = 0;

        for (int r = 1; r < m - 1; r++) {
            maxSum = Math.max(maxSum, solve3ArraySum(top[r], board[r], bottom[r]));
        }

        return maxSum;
    }

    private long solve3ArraySum(long[] A, int[] B_int, long[] C) {
        int n = A.length;
        long[] B = new long[n];
        for(int i=0; i<n; i++) B[i] = B_int[i];

        Pair[] prefA = getPrefixTop2(A);
        Pair[] suffA = getSuffixTop2(A);
        Pair[] prefC = getPrefixTop2(C);
        Pair[] suffC = getSuffixTop2(C);

        long max = 0;
        for (int j = 1; j < n - 1; j++) {
            Pair topA1 = prefA[j - 1];
            Pair topA2 = suffA[j + 1];
            Pair topC1 = prefC[j - 1];
            Pair topC2 = suffC[j + 1];

            long currentMax = 0;
            if (topA1.idx != topC1.idx) {
                currentMax = Math.max(currentMax, topA1.val + topC1.val);
            }
            if (topA1.idx != topC2.idx) {
                currentMax = Math.max(currentMax, topA1.val + topC2.val);
            }
            if (topA2.idx != topC1.idx) {
                currentMax = Math.max(currentMax, topA2.val + topC1.val);
            }
            if (topA2.idx != topC2.idx) {
                currentMax = Math.max(currentMax, topA2.val + topC2.val);
            }
            max = Math.max(max, B[j] + currentMax);
        }
        return max;
    }

    private Pair[] getPrefixTop2(long[] arr) { // Simplified logic, real one needs top 2
        int n = arr.length;
        Pair[] res = new Pair[n];
        res[0] = new Pair(arr[0], 0);
        for (int i = 1; i < n; i++) {
            if (arr[i] > res[i - 1].val) {
                res[i] = new Pair(arr[i], i);
            } else {
                res[i] = res[i - 1];
            }
        }
        return res;
    }

    private Pair[] getSuffixTop2(long[] arr) { // Simplified logic, real one needs top 2
        int n = arr.length;
        Pair[] res = new Pair[n];
        res[n - 1] = new Pair(arr[n - 1], n - 1);
        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] > res[i + 1].val) {
                res[i] = new Pair(arr[i], i);
            } else {
                res[i] = res[i + 1];
            }
        }
        return res;
    }
}
```
*Note: The provided Java code for the `O(m*n)` approach is a simplified illustration. A full implementation of `getPrefixTop2` and `solve3ArraySum` would need to handle finding and merging the top two distinct elements, which adds complexity.*
### Algorithm
1. The key idea is to iterate through the row of the *middle* rook. Any placement of three rooks in distinct rows `r_a < r_b < r_c` can be categorized by its middle row `r_b`.
2. We iterate a row index `r` from `1` to `m-2`. This `r` will be the row of one of the rooks.
3. For each `r`, one rook must be in a row `r_top < r` and another in a row `r_bottom > r`.
4. Precompute two tables: `top[m][n]` and `bottom[m][n]`.
   - `top[r][c]` stores the maximum value in column `c` for all rows above `r` (i.e., `max_{i<r} board[i][c]`).
   - `bottom[r][c]` stores the maximum value in column `c` for all rows below `r` (i.e., `max_{i>r} board[i][c]`).
   - These tables can be filled in `O(m*n)` time using dynamic programming.
5. For each middle row `r`:
   - We have three arrays to consider: `A[c] = top[r][c]`, `B[c] = board[r][c]`, and `C[c] = bottom[r][c]`.
   - The problem reduces to finding `max_{c1, c2, c3 are distinct} (A[c1] + B[c2] + C[c3])`.
   - This 3-array sum problem can be solved in `O(n)` time.
6. To solve the 3-array sum problem in `O(n)`:
   - Iterate through the column `c2` for the middle rook (from array `B`).
   - For each `c2`, we need to find `max_{c1, c3 != c2, c1 != c3} (A[c1] + C[c3])`.
   - This can be done in `O(1)` if we have precomputed prefix and suffix top-2 values for arrays `A` and `C`.
   - The prefix/suffix top-2 precomputation for `A` and `C` takes `O(n)` for each `r`.
7. The total time complexity is `O(m*n)` for the initial `top`/`bottom` precomputation, plus `m` iterations of an `O(n)` subproblem, leading to a total of `O(m*n)`.