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.
This approach involves trying all possible combinations of placing three rooks on the board using a brute-force method with pruning strategies to eliminate impossible solutions early. We'll pick one cell from each pair-wise distinct row and column to place the rooks, ensuring they don't attack each other, and then calculate the sum of the values on these cells to find the maximum sum.
The above C code leverages a brute-force approach by iterating over all possible ways to place the three rooks. Nested loops ensure that a cell from each distinct row and column is selected as a rook position. A check is performed to avoid placing rooks in the same row or column. The complexity is reduced using pruning strategies, such as skipping unnecessary iterations.
Time Complexity: O(m^3 * n^3), as three nested loops are run on both row and column dimensions of the board.
Space Complexity: O(1), it operates in constant space usage as no additional data structures are used, except for basic variables.
This approach utilizes a greedy strategy based on selecting independent maximums from distinct rows and columns. For each row, identify the maximum value and its column, ensuring no two rooks are placed in the same column. This requires maintaining selected columns in a set to avoid reuse and iteratively build up the best potential sum without causing rook conflicts.
This Java solution employs a greedy approach by selecting the maximum possible values from different rows while ensuring distinct columns for rook placement. The used columns are tracked to prevent column collisions, mimicking a zero-sum game on rook placements to optimize the value sum without any direct conflicts.
Java
JavaScript
Time Complexity: O(m * n * 3) = O(m * n), as it inspects cells multiple times for potential maximum values, but in a reduced complexity compared to brute force.
Space Complexity: O(n) due to the array tracking used columns.
| Approach | Complexity |
|---|---|
| Brute Force with Pruning | Time Complexity: O(m^3 * n^3), as three nested loops are run on both row and column dimensions of the board. |
| Greedy Row and Column Independence | Time Complexity: O(m * n * 3) = O(m * n), as it inspects cells multiple times for potential maximum values, but in a reduced complexity compared to brute force. |
| 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 |
Maximum Value Sum by Placing Three Rooks | I & II | Leetcode 3256 | 3257 • Tech Courses • 867 views views
Watch 5 more video solutions →Practice Maximum Value Sum by Placing Three Rooks II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor