Watch 6 video solutions for Maximum Value Sum by Placing Three Rooks I, a hard level problem involving Array, Dynamic Programming, Matrix. This walkthrough by Abhinav Awasthi has 5,517 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 <= 1003 <= n == board[i].length <= 100-109 <= board[i][j] <= 109Problem Overview: You are given an matrix where each cell has a value. Place exactly three rooks such that no two share the same row or column. The goal is to maximize the sum of the selected cells.
Approach 1: Backtracking with Row and Column Tracking (O(m^3 * n^3) time, O(1) space)
This approach tries every valid configuration of three rooks using enumeration. You recursively choose cells while maintaining two sets that track used rows and columns. Each recursive step places a rook only if its row and column are still free. Once three rooks are placed, update the maximum sum. The search explores combinations of cells across the grid, which leads to roughly O((m*n)^3) possibilities in the worst case. Backtracking is straightforward and useful for understanding the constraint that rooks cannot share rows or columns.
Approach 2: Greedy Selection with Row Enumeration (O(m^3) time, O(m) space)
A more efficient strategy observes that exactly three distinct rows and three distinct columns must be used. Instead of exploring every cell combination, first enumerate all triplets of rows. For each selected row, keep the top few candidate columns with the largest values. Now try combinations of one column per row while ensuring the columns are distinct. Because only a small constant number of top candidates per row are considered, the column combinations remain limited. This reduces the search dramatically compared to naive backtracking. The algorithm effectively combines greedy selection (keeping top candidates) with structured enumeration over row triplets.
The optimization works because only the highest-value cells per row can realistically contribute to the optimal answer. Checking all columns is unnecessary once you preserve the best candidates. The problem naturally mixes ideas from arrays, grid traversal, and constrained enumeration.
Recommended for interviews: Start by explaining the brute-force backtracking approach to demonstrate understanding of the row and column constraints. Then move to the optimized enumeration strategy that keeps only the best column candidates per row. Interviewers usually expect the optimized approach because it cuts the search space from exploring every cell combination to only evaluating row triplets with a small constant number of column choices.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with Row/Column Constraints | O((m*n)^3) | O(1) | Understanding the constraint logic or when grid size is very small |
| Greedy Selection with Row Enumeration | O(m^3) | O(m) | Recommended approach for interviews and large matrices |