Watch 6 video solutions for Maximum Value Sum by Placing Three Rooks II, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by Tech Courses has 867 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem Overview: You are given an m x n matrix where each cell has a value. Place exactly three rooks so that no two share the same row or column. The goal is to maximize the total value of the three chosen cells.
Approach 1: Brute Force with Pruning (O((m*n)^3) time, O(1) space)
The direct strategy enumerates combinations of three cells and checks whether their rows and columns are all distinct. Maintain the current best sum while iterating through candidate triples. Pruning helps reduce work: if two cells already share a row or column, skip immediately before checking the third. Another optimization tracks partial sums so combinations that cannot beat the current best are discarded early. This approach is straightforward and useful for validating correctness, but worst‑case complexity grows quickly because the search space is cubic in the number of cells.
Approach 2: Greedy Row and Column Independence (O(m*n log n) time, O(n) space)
A key observation is that each rook must occupy a unique row and column, which creates independence between row selection and column conflicts. Iterate rows while keeping candidate column values sorted by value. For each row, track the best columns that can participate in a valid three‑rook configuration. When combining rows, ensure columns are distinct and compute the best achievable triple using top candidates rather than scanning the entire matrix again. Sorting or maintaining priority structures allows quick access to the highest cell values per row while avoiding column collisions. This reduces the search to a small set of promising candidates instead of all cells.
The algorithm essentially performs controlled enumeration of row combinations while using greedy selection on columns. Some implementations also maintain prefix or suffix best values to quickly form pairs and triples, which resembles a lightweight dynamic programming pattern over rows. Because each row contributes only a few candidate cells, the overall work stays close to linear in the matrix size.
Recommended for interviews: Start by explaining the brute force idea to demonstrate understanding of the constraints: three cells with distinct rows and columns. Then move to the greedy row‑column independence optimization. Interviewers expect you to reduce the search space using matrix structure and careful matrix traversal. Showing the transition from naive enumeration to a pruned greedy solution highlights strong problem‑solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Pruning | O((m*n)^3) | O(1) | Useful for small matrices or validating logic during development |
| Greedy Row and Column Independence | O(m*n log n) | O(n) | Best practical solution; reduces candidate cells and avoids full cubic enumeration |