Maximum Value Sum by Placing Three Rooks I

Hard

#2890Time: O(m³ * n³). There are `O(m³)` ways to choose 3 rows and `O(n³)` ways to choose 3 columns. The inner calculations are constant time.Space: O(1) extra space.

Patterns

Dynamic Programming Enumeration

Data structures

Array Matrix

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 <= 100
3 <= n == board[i].length <= 100
-10⁹ <= board[i][j] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach explores every possible valid placement of three rooks. A valid placement requires the three rooks to be in distinct rows and distinct columns. The algorithm iterates through all combinations of three different rows and three different columns, then checks all possible non-attacking configurations within that 3x3 selection, updating the maximum sum found.

Algorithm

Initialize a variable maxSum to a very small value (e.g., Long.MIN_VALUE).
Use six nested loops to iterate through all possible combinations of three distinct row indices r1, r2, r3 and three distinct column indices c1, c2, c3.
To avoid redundant checks and reduce iterations slightly, ensure r1 < r2 < r3 and c1 < c2 < c3 in the loops.
For each combination of three rows and three columns, we have a 3x3 subgrid. There are 3! = 6 ways to place three non-attacking rooks within this subgrid.
Calculate the sum of values for each of these 6 placements.
- sum1 = board[r1][c1] + board[r2][c2] + board[r3][c3]
- sum2 = board[r1][c1] + board[r2][c3] + board[r3][c2]
- ... and so on for all 6 permutations of columns (c1, c2, c3) for rows (r1, r2, r3).
Update maxSum with the maximum sum found among these 6 possibilities.
After all loops complete, maxSum will hold the maximum possible sum.

Walkthrough

The most straightforward way to solve the problem is to exhaustively check every single combination of three cells that satisfy the non-attacking condition. We can structure this by first selecting three distinct rows, then selecting three distinct columns. This defines a 3x3 subgrid of cells. Within this subgrid, there are 3! = 6 ways to place the three rooks such that they don't attack each other (one in each row and column of the subgrid). We calculate the sum for each of these 6 placements and find the maximum. By repeating this for all possible 3-row and 3-column combinations, we can find the global maximum sum.

1class Solution {2    public long maximumValueSum(int[][] board) {3        int m = board.length;4        int n = board[0].length;5        long maxSum = Long.MIN_VALUE;6 7        if (m < 3 || n < 3) {8            return 0; // Not possible to place 3 non-attacking rooks9        }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 (int c1 = 0; c1 < n; c1++) {15                        for (int c2 = c1 + 1; c2 < n; c2++) {16                            for (int c3 = c2 + 1; c3 < n; c3++) {17                                // Rows: r1, r2, r318                                // Cols: c1, c2, c319                                // Check all 6 permutations for placing rooks20                                long currentMax = 0;21                                long v11 = board[r1][c1], v12 = board[r1][c2], v13 = board[r1][c3];22                                long v21 = board[r2][c1], v22 = board[r2][c2], v23 = board[r2][c3];23                                long v31 = board[r3][c1], v32 = board[r3][c2], v33 = board[r3][c3];24 25                                currentMax = Math.max(currentMax, v11 + v22 + v33);26                                currentMax = Math.max(currentMax, v11 + v23 + v32);27                                currentMax = Math.max(currentMax, v12 + v21 + v33);28                                currentMax = Math.max(currentMax, v12 + v23 + v31);29                                currentMax = Math.max(currentMax, v13 + v21 + v32);30                                currentMax = Math.max(currentMax, v13 + v22 + v31);31 32                                maxSum = Math.max(maxSum, currentMax);33                            }34                        }35                    }36                }37            }38        }39        return maxSum;40    }41}

Complexity

Time

O(m³ * n³). There are `O(m³)` ways to choose 3 rows and `O(n³)` ways to choose 3 columns. The inner calculations are constant time.

Space

O(1) extra space.

Trade-offs

Pros

Conceptually simple and easy to understand.
Correctly solves the problem for very small boards.

Cons

The time complexity is extremely high, making it infeasible for the given constraints.
It will result in a 'Time Limit Exceeded' (TLE) error on most platforms.

This optimized approach significantly reduces the complexity by breaking the problem down. We iterate through all combinations of three rows (or columns, whichever dimension is smaller). For each fixed set of three rows, we then use dynamic programming to efficiently find the optimal placement of rooks in three distinct columns. This avoids the costly cubic iteration over the second dimension.

Algorithm

First, check if m > n. If so, it's more efficient to iterate through combinations of columns instead of rows. For simplicity, we can transpose the board so that the number of rows m is always less than or equal to the number of columns n.
Initialize maxSum to a very small value.
Iterate through all combinations of three distinct rows: r1, r2, r3. This takes O(m³) time.
For each combination of three rows, solve a subproblem: find the maximum sum by picking three distinct columns. This subproblem can be solved in O(n) time using dynamic programming.
DP Subproblem:
- Let dp[mask] be the maximum sum using popcount(mask) rooks, placed in some subset of columns, occupying the rows specified by mask. mask is a 3-bit integer where the i-th bit corresponds to the i-th chosen row.
- Initialize dp array of size 8 with dp[0] = 0 and all other dp[mask] = -infinity.
- Iterate through each column j from 0 to n-1.
- In each iteration, create a next_dp array from the current dp array. For each mask, try to place a rook in column j in an unused row i (where the i-th bit in mask is 0). Update next_dp[mask | (1<<i)].
- After iterating through all columns, dp[7] (mask 111 in binary) will hold the maximum sum for the chosen three rows.
Update the global maxSum with the result from the DP subproblem.
Return maxSum.

Walkthrough

The key insight is that once we fix the three rows, say r1, r2, r3, the problem reduces to selecting three distinct columns c1, c2, c3 and a permutation to maximize the sum. This subproblem can be solved much faster than brute force.

We can define a dynamic programming state dp[mask] representing the maximum sum achievable using a subset of columns processed so far, where mask indicates which of the three chosen rows (r1, r2, r3) are occupied. The mask is a 3-bit integer. For example, mask = 5 (binary 101) means rooks have been placed in rows r1 and r3.

We iterate through each column of the board one by one. For each column, we update our dp table. We can either skip the current column or place a rook in it in one of the three chosen rows (if that row is not already occupied). After iterating through all columns, dp[7] (binary 111) will give the maximum sum for the fixed set of rows, as all three rows are now occupied.

The overall algorithm iterates through all O(m³) combinations of rows and solves the O(n) DP subproblem for each, leading to a total time complexity of O(m³ * n). To optimize, we can ensure m <= n by transposing the board if m > n, making the complexity O(min(m,n)³ * max(m,n)), which is efficient enough for the given constraints.

1import java.util.Arrays;2 3class Solution {4    public long maximumValueSum(int[][] board) {5        int m = board.length;6        int n = board[0].length;7 8        if (m < n) {9            // Transpose the board to ensure m >= n, so we iterate over the smaller dimension cubically.10            int[][] transposedBoard = new int[n][m];11            for (int i = 0; i < m; i++) {12                for (int j = 0; j < n; j++) {13                    transposedBoard[j][i] = board[i][j];14                }15            }16            board = transposedBoard;17            int temp = m;18            m = n;19            n = temp;20        }21        // Now m >= n, we will iterate O(n^3) and DP on m rows.22 23        long maxSum = Long.MIN_VALUE;24 25        for (int c1 = 0; c1 < n; c1++) {26            for (int c2 = c1 + 1; c2 < n; c2++) {27                for (int c3 = c2 + 1; c3 < n; c3++) {28                    int[] cols = {c1, c2, c3};29                    30                    // DP to find best 3 rows for these 3 columns31                    long[] dp = new long[1 << 3];32                    Arrays.fill(dp, Long.MIN_VALUE);33                    dp[0] = 0;34 35                    for (int r = 0; r < m; r++) {36                        long[] next_dp = dp.clone();37                        for (int mask = 0; mask < (1 << 3); mask++) {38                            if (dp[mask] == Long.MIN_VALUE) continue;39                            for (int i = 0; i < 3; i++) {40                                if ((mask & (1 << i)) == 0) { // if i-th rook is not placed41                                    int new_mask = mask | (1 << i);42                                    long val = board[r][cols[i]];43                                    if (next_dp[new_mask] == Long.MIN_VALUE || dp[mask] + val > next_dp[new_mask]) {44                                        next_dp[new_mask] = dp[mask] + val;45                                    }46                                }47                            }48                        }49                        dp = next_dp;50                    }51                    if (dp[7] != Long.MIN_VALUE) {52                        maxSum = Math.max(maxSum, dp[7]);53                    }54                }55            }56        }57 58        return maxSum;59    }60}

Complexity

Time

O(min(m, n)³ * max(m, n)). By ensuring the cubic iteration happens over the smaller dimension, we optimize the performance. For a square board, it's O(n⁴).

Space

O(1) or O(2^k) where k=3. The DP table size is constant (8), so it's O(1) extra space.

Trade-offs

Pros

Significantly more efficient than the brute-force approach.
Guaranteed to pass within the time limits for the given constraints.
It's a standard technique for this type of selection problem (fixing some parameters and using DP for the rest).

Cons

The implementation is more complex than the brute-force approach.
Requires careful handling of DP states and transitions.

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