Skip to main content
Talentd

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

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

Approach Overview

Problem 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 1: Backtracking Approach

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy Selection with Row and Column Constraints

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(m*n + 3^3), dominated by sorting.
Space Complexity: O(m + n), for storing row and column data.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Backtracking Approach

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.

Greedy Selection with Row and Column Constraints

Time Complexity: O(m*n + 3^3), dominated by sorting.
Space Complexity: O(m + n), for storing row and column data.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Backtracking with Row/Column ConstraintsO((m*n)^3)O(1)Understanding the constraint logic or when grid size is very small
Greedy Selection with Row EnumerationO(m^3)O(m)Recommended approach for interviews and large matrices

Video Solution

A, B, C | Leetcode Biweekly Contest 137 Editorials | Maximum Value Sum by Placing Three Rooks • Abhinav Awasthi • 5,539 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Maximum Value Sum by Placing Three Rooks I easy or hard?
Maximum Value Sum by Placing Three Rooks I is classified as a Hard problem because it requires reducing a large combinational search space. The challenge is recognizing that only a few high-value cells per row need to be considered, allowing enumeration of row triplets with efficient pruning.
Maximum Value Sum by Placing Three Rooks I Python/Java solution
Python and Java implementations typically follow the same logic: enumerate row triplets, collect the top column values for each row, and check combinations that use distinct columns. Python solutions often rely on sorting or heap operations, while Java implementations use arrays and priority queues for candidate selection.
How to solve Maximum Value Sum by Placing Three Rooks I in O(n)?
An O(n) solution is not feasible because the algorithm must evaluate combinations of rows and columns to enforce the rook constraints. The best practical strategy is O(m^3) by enumerating row triplets and testing only the highest-value columns per row. This drastically prunes the search while guaranteeing correctness.
What is the best approach for Maximum Value Sum by Placing Three Rooks I?
The most practical approach enumerates all triplets of rows and then greedily selects the best column candidates for each row while ensuring columns remain distinct. This reduces the search space significantly compared to brute force. The resulting complexity is around O(m^3) with small constant checks for column combinations.
Is Maximum Value Sum by Placing Three Rooks I asked at Google/Amazon/Meta?
Grid optimization problems with row and column constraints appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving rook placement, matrix selection, or constrained maximum sums are common because they test enumeration strategies and pruning techniques.
What data structure is used in Maximum Value Sum by Placing Three Rooks I?
The solution primarily uses arrays to store the matrix and track candidate column values per row. Some implementations maintain small lists or heaps of top elements in each row to quickly evaluate valid combinations while avoiding column conflicts.
What is the time complexity of Maximum Value Sum by Placing Three Rooks I?
A naive backtracking solution can reach O((m*n)^3) because it explores combinations of three cells across the grid. The optimized approach enumerates three rows and tests a limited set of top column candidates, reducing the complexity to roughly O(m^3). Space usage remains small, typically O(m) or constant depending on implementation.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Available Captures for Rook