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] <= 109This 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.
Python
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.
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. |
How many LeetCode problems should you solve? #leetcode #techinterview #developer #softwareengineer • CrioDo • 304,699 views views
Watch 9 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