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.
This approach involves experimenting with different placements of the rooks, ensuring that at no point are two rooks placed in the same row or column. We check each possible combination of 3-rook placements, keeping track of the positions already taken, and calculate the sum for each valid combination, returning the maximum found.
The function maxRookSum uses a helper function backtrack to explore different ways of placing three rooks. We use bitmasking to keep track of which columns have been occupied. This allows for efficient constraints checking and maximum sum computation.
Time Complexity: O((m choose 3) * n^3), where m and n are the number of rows and columns.
Space Complexity: O(m), due to the recursion stack.
This approach simplifies the problem by generating candidates for rows and columns based on their maximum value contributions, without direct permutations. We then attempt to select the top combinations.
The function maxRookSum selects the top 3 rows and columns based on their maximum value to form a subset of potential rook positions. It then checks combinations, avoiding selections in the same row or column twice.
Time Complexity: O(m*n + 3^3), dominated by sorting.
Space Complexity: O(m + n), for storing row and column data.
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O((m choose 3) * n^3), where m and n are the number of rows and columns. |
| Greedy Selection with Row and Column Constraints | Time Complexity: O(m*n + 3^3), dominated by sorting. |
| 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 |
A, B, C | Leetcode Biweekly Contest 137 Editorials | Maximum Value Sum by Placing Three Rooks • Abhinav Awasthi • 5,517 views views
Watch 5 more video solutions →Practice Maximum Value Sum by Placing Three Rooks I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor