Skip to main content
Talentd

Maximum Value Sum by Placing Three Rooks II - Solution & Explanation

HardArrayDynamic ProgrammingMatrixEnumeration7 min read
Practice this problem

Problem Statement

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 <= 500
  • 3 <= n == board[i].length <= 500
  • -109 <= board[i][j] <= 109

Approach Overview

Problem 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 1: Brute Force with Pruning

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.

Code

CPython

C

Python

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Row and Column Independence

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1), it operates in constant space usage as no additional data structures are used, except for basic variables.

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.
Space Complexity: O(n) due to the array tracking used columns.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with PruningO((m*n)^3)O(1)Useful for small matrices or validating logic during development
Greedy Row and Column IndependenceO(m*n log n)O(n)Best practical solution; reduces candidate cells and avoids full cubic enumeration

Video Solution

Maximum Value Sum by Placing Three Rooks | I & II | Leetcode 3256 | 3257 • Tech Courses • 877 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum Value Sum by Placing Three Rooks II easy or hard?
Maximum Value Sum by Placing Three Rooks II is classified as Hard. The challenge comes from balancing row and column constraints while maximizing the total value, which requires reducing a potentially cubic search space using pruning, enumeration strategies, or greedy selection.
Maximum Value Sum by Placing Three Rooks II Python/Java solution
Python and Java implementations usually follow the greedy row-column independence idea. Iterate rows, store the best column candidates per row, and combine them while enforcing distinct columns. Python often uses heaps or sorted lists, while Java implementations rely on priority queues or arrays.
How to solve Maximum Value Sum by Placing Three Rooks II in O(n)?
A near-linear strategy scans the matrix row by row while keeping only the highest-value column candidates for each row. By combining rows and verifying column uniqueness among a small candidate set, the algorithm avoids scanning the full matrix repeatedly. In practice the complexity becomes close to O(m*n) with small additional overhead for ordering candidates.
What is the best approach for Maximum Value Sum by Placing Three Rooks II?
The most practical approach uses greedy row and column independence. Instead of checking every possible triple of cells, the algorithm keeps the best candidate columns for each row and combines them while ensuring column uniqueness. This reduces the search space significantly and runs around O(m*n log n) time with O(n) auxiliary space.
Is Maximum Value Sum by Placing Three Rooks II asked at Google/Amazon/Meta?
Hard matrix optimization problems like this commonly appear in interviews at large tech companies such as Google, Amazon, and Meta. The question tests reasoning about constraints, pruning large search spaces, and combining enumeration with greedy or dynamic programming ideas.
What data structure is used in Maximum Value Sum by Placing Three Rooks II?
Typical solutions rely on arrays for matrix traversal and priority structures or sorted lists to track the highest-value columns for each row. Some optimized implementations also use prefix/suffix arrays or small candidate buffers to quickly compute the best triple without scanning the entire grid.
What is the time complexity of Maximum Value Sum by Placing Three Rooks II?
The optimized greedy solution typically runs in O(m*n log n) time because it sorts or maintains top column candidates for each row and then evaluates valid combinations. The brute force approach can reach O((m*n)^3) time since it checks every triple of cells with distinct rows and columns.

Ready to solve this problem?

Practice Maximum Value Sum by Placing Three Rooks II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Available Captures for Rook