Maximum Value Sum by Placing Three Rooks II

Hard

#2891Time: O(m^3 * n)Space: O(n)

Patterns

Data structures

Prompt

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:

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
-10⁹ <= board[i][j] <= 10⁹

Approaches

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

Initialize a variable maxSum to a very small number.
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.
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.
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.
The subproblem is now to find max_{i, j, k are distinct} (A[i] + B[j] + C[k]).
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.
After checking all combinations of three rows, maxSum will hold the result.

Walkthrough

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).

1class Solution {2    public long maximumValueSum(int[][] board) {3        int m = board.length;4        int n = board[0].length;5        long maxSum = 0;6 7        if (m < 3 || n < 3) {8            return 0;9        }10 11        for (int r1 = 0; r1 < m; r1++) {12            for (int r2 = r1 + 1; r2 < m; r2++) {13                for (int r3 = r2 + 1; r3 < m; r3++) {14                    // For fixed r1, r2, r3, find max sum with distinct columns15                    long currentMax = findMaxSumForThreeRows(board, r1, r2, r3);16                    maxSum = Math.max(maxSum, currentMax);17                }18            }19        }20        return maxSum;21    }22 23    private long findMaxSumForThreeRows(int[][] board, int r1, int r2, int r3) {24        int n = board[0].length;25        // Find top 3 columns for each row26        Pair[] top_r1 = getTopN(board[r1], 3);27        Pair[] top_r2 = getTopN(board[r2], 3);28        Pair[] top_r3 = getTopN(board[r3], 3);29 30        long max = 0;31        for (Pair p1 : top_r1) {32            for (Pair p2 : top_r2) {33                for (Pair p3 : top_r3) {34                    if (p1.index != p2.index && p1.index != p3.index && p2.index != p3.index) {35                        max = Math.max(max, p1.value + p2.value + p3.value);36                    }37                }38            }39        }40        return max;41    }42 43    private Pair[] getTopN(int[] row, int N) {44        java.util.PriorityQueue<Pair> pq = new java.util.PriorityQueue<>((a, b) -> Long.compare(a.value, b.value));45        for (int i = 0; i < row.length; i++) {46            pq.offer(new Pair(row[i], i));47            if (pq.size() > N) {48                pq.poll();49            }50        }51        Pair[] result = new Pair[pq.size()];52        int i = 0;53        while(!pq.isEmpty()) {54            result[i++] = pq.poll();55        }56        return result;57    }58 59    class Pair {60        long value;61        int index;62        Pair(long value, int index) {63            this.value = value;64            this.index = index;65        }66    }67}

Complexity

Time

O(m^3 * n)

Space

O(n)

Trade-offs

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.

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.

Algorithm

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.
Precompute for each column c, the top 3 values and their corresponding row indices. This takes O(m*n) time.
Initialize maxSum to a very small number.
Iterate through all pairs of distinct rows r1 and r2. This is O(m^2) combinations.
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.
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.
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.
Now, solve the 3-array sum problem for A=board[r1], B=board[r2], and C. This can be done in O(n) time.
Update maxSum with the result from the subproblem.
The total time complexity will be O(m*n + m^2 * n) = O(m^2 * n).

Walkthrough

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).

1// This is a conceptual illustration. A full implementation would be lengthy.2// The core logic relies on solving the 3-array sum problem efficiently.3class Solution {4    // Assuming a helper function solve3ArraySum(long[] A, long[] B, long[] C) exists,5    // which solves max(A[i] + B[j] + C[k]) over distinct i,j,k in O(n) time.6    public long maximumValueSum(int[][] board) {7        int m = board.length;8        int n = board[0].length;9        long maxSum = 0;10 11        // Precompute top 3 values for each column12        // colTop3[c] would store pairs of (value, rowIndex)13        Pair[][] colTop3 = new Pair[n][3];14        // ... O(m*n) precomputation logic ...15 16        for (int r1 = 0; r1 < m; r1++) {17            for (int r2 = r1 + 1; r2 < m; r2++) {18                long[] A = new long[n];19                long[] B = new long[n];20                long[] C = new long[n];21                for(int c=0; c<n; c++) {22                    A[c] = board[r1][c];23                    B[c] = board[r2][c];24                    // Build C[c] using precomputed colTop325                    // Find max in col c, excluding r1 and r226                    long maxVal = Long.MIN_VALUE;27                    for(Pair p : colTop3[c]) {28                        if (p.index != r1 && p.index != r2) {29                            maxVal = p.value;30                            break;31                        }32                    }33                    C[c] = maxVal;34                }35                // maxSum = Math.max(maxSum, solve3ArraySum(A, B, C));36            }37        }38        return maxSum;39    }40    // Pair class and solve3ArraySum implementation would be needed.41}

Complexity

Time

O(m^2 * n) (assuming m <= n)

Space

O(m*n) or O(n) depending on precomputation strategy.

Trade-offs

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.

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.

Algorithm

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.
We iterate a row index r from 1 to m-2. This r will be the row of one of the rooks.
For each r, one rook must be in a row r_top < r and another in a row r_bottom > r.
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.
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.
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.
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).

Walkthrough

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).

1class Solution {2    class Pair {3        long val;4        int idx;5        Pair(long val, int idx) {6            this.val = val;7            this.idx = idx;8        }9    }10 11    public long maximumValueSum(int[][] board) {12        int m = board.length;13        int n = board[0].length;14 15        long[][] top = new long[m][n];16        for (int c = 0; c < n; c++) top[0][c] = Long.MIN_VALUE;17        for (int r = 1; r < m; r++) {18            for (int c = 0; c < n; c++) {19                top[r][c] = Math.max(top[r - 1][c], board[r - 1][c]);20            }21        }22 23        long[][] bottom = new long[m][n];24        for (int c = 0; c < n; c++) bottom[m - 1][c] = Long.MIN_VALUE;25        for (int r = m - 2; r >= 0; r--) {26            for (int c = 0; c < n; c++) {27                bottom[r][c] = Math.max(bottom[r + 1][c], board[r + 1][c]);28            }29        }30 31        long maxSum = 0;32 33        for (int r = 1; r < m - 1; r++) {34            maxSum = Math.max(maxSum, solve3ArraySum(top[r], board[r], bottom[r]));35        }36 37        return maxSum;38    }39 40    private long solve3ArraySum(long[] A, int[] B_int, long[] C) {41        int n = A.length;42        long[] B = new long[n];43        for(int i=0; i<n; i++) B[i] = B_int[i];44 45        Pair[] prefA = getPrefixTop2(A);46        Pair[] suffA = getSuffixTop2(A);47        Pair[] prefC = getPrefixTop2(C);48        Pair[] suffC = getSuffixTop2(C);49 50        long max = 0;51        for (int j = 1; j < n - 1; j++) {52            Pair topA1 = prefA[j - 1];53            Pair topA2 = suffA[j + 1];54            Pair topC1 = prefC[j - 1];55            Pair topC2 = suffC[j + 1];56 57            long currentMax = 0;58            if (topA1.idx != topC1.idx) {59                currentMax = Math.max(currentMax, topA1.val + topC1.val);60            }61            if (topA1.idx != topC2.idx) {62                currentMax = Math.max(currentMax, topA1.val + topC2.val);63            }64            if (topA2.idx != topC1.idx) {65                currentMax = Math.max(currentMax, topA2.val + topC1.val);66            }67            if (topA2.idx != topC2.idx) {68                currentMax = Math.max(currentMax, topA2.val + topC2.val);69            }70            max = Math.max(max, B[j] + currentMax);71        }72        return max;73    }74 75    private Pair[] getPrefixTop2(long[] arr) { // Simplified logic, real one needs top 276        int n = arr.length;77        Pair[] res = new Pair[n];78        res[0] = new Pair(arr[0], 0);79        for (int i = 1; i < n; i++) {80            if (arr[i] > res[i - 1].val) {81                res[i] = new Pair(arr[i], i);82            } else {83                res[i] = res[i - 1];84            }85        }86        return res;87    }88 89    private Pair[] getSuffixTop2(long[] arr) { // Simplified logic, real one needs top 290        int n = arr.length;91        Pair[] res = new Pair[n];92        res[n - 1] = new Pair(arr[n - 1], n - 1);93        for (int i = n - 2; i >= 0; i--) {94            if (arr[i] > res[i + 1].val) {95                res[i] = new Pair(arr[i], i);96            } else {97                res[i] = res[i + 1];98            }99        }100        return res;101    }102}

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.

Complexity

Time

O(m*n)

Space

O(m*n) for the precomputed `top` and `bottom` tables.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem