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 <= 5003 <= n == board[i].length <= 500-109 <= board[i][j] <= 109In #3257 Maximum Value Sum by Placing Three Rooks II, the goal is to place three rooks on a matrix so that no two share the same row or column while maximizing the total value of the chosen cells. Because only three rooks are placed, an important optimization is that each row only needs to consider its top few candidate cells (commonly the top 3 values with their column indices). Any optimal configuration must come from these strongest candidates.
After extracting these candidates for every row, we can enumerate combinations of three distinct rows. For each row triple, test the candidate cells while ensuring their column indices are all different. Since each row contributes only a few candidates, the number of combinations per row triple remains small and manageable.
This pruning drastically reduces the search space compared to checking all matrix cells. The strategy effectively combines enumeration with greedy pruning based on row-wise maximum values. Time complexity is significantly reduced compared to brute force, while space complexity remains minimal since only a few candidates per row are stored.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Row Candidate Pruning + Enumeration | O(R^3 * K^3) where K ≈ 3 candidates per row | O(R * K) |
| Matrix Preprocessing (finding top candidates per row) | O(R * C) | O(R * K) |
CrioDo
Use these hints if you're stuck. Try solving on your own first.
Save the top 3 largest values in each row.
Select any row, and select any of the three values stored in it.
Get the top 4 values from all of the other 3 largest values of the other rows, which do not share the same column as the selected value.
Brute force the selection of 2 positions from the top 4 now.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Since only three rooks are placed overall, at most three columns will be used. Keeping the top three values per row guarantees that any optimal solution must come from these candidates, allowing us to safely ignore weaker cells and reduce computation.
Problems involving rook placement and maximizing sums with row and column constraints are common variations in coding interviews. While this exact problem may not appear, the techniques—matrix optimization, pruning, and combinational enumeration—are frequently tested in FAANG-style interviews.
The optimal approach prunes the search space by keeping only the top few candidate cells per row, usually the top three values with their column indices. Then it enumerates combinations of three different rows and checks candidate placements while ensuring all columns are distinct. This significantly reduces the number of configurations compared to brute force.
Arrays or lists are sufficient to store the top candidate cells for each row. During enumeration, simple loops or small collections can be used to verify column uniqueness among the chosen candidates.