Skip to content

Practice Maximum Value Sum by Placing Three Rooks I

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Hard#3256
LeetCode Problem

Maximum Value Sum by Placing Three Rooks I

Problem Statement

Place exactly three rooks on board. Their cells must occupy three different rows and three different columns. Return the largest sum of the three cell values, including when every possible sum is negative. Choosing fewer than three rooks is not allowed. Approach: Keep each row's three highest-valued cells, including their column numbers. Enumerate every triple of rows and every combination of their retained cells, rejecting repeated columns. Keeping three candidates per row is sufficient: the other two rooks can forbid at most two columns, so any discarded choice can be replaced by an available retained one without decreasing the score. This takes O(m*n + m^3) time with a small constant and O(m) auxiliary space. Use a wide integer for the sum. Worked example: The diagonal cells in the first board total 9+8+7=24. In the second board, the best legal placement still totals -6; zero is not a valid answer.

Source: Maximum Value Sum by Placing Three Rooks I on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
board = [[9,0,0],[0,8,0],[0,0,7]]
Output
24

# Example 2

Input
board = [[-1,-5,-5],[-5,-2,-5],[-5,-5,-3]]
Output
-6

Constraints

The board has 3 to 100 rows and 3 to 100 columns.
Every cell is an integer between -1,000,000,000 and 1,000,000,000.

How to solve Maximum Value Sum by Placing Three Rooks I

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

In any row only its three largest cells can matter, because the other two rooks block at most two columns, so at least one of the row's top three stays usable and can replace whatever cell a solution used there without lowering the sum. The search shrinks from n cells per row to 3, then to a small enumeration over row triples.

Why brute force is not enough

Trying every triple of cells on the board is O((m * n)^3), about 10^12 for a 100 by 100 board; fixing three rows and trying all n^3 column choices is still around 10^12.

Approach

  1. For each row, keep its three highest-valued cells with their column indices, found in one O(n) pass with a small running top-three list.
  2. Justify the cut: in any valid placement the two rooks outside a row occupy two columns, so at most two of that row's top three are blocked, and swapping to an unblocked top-three cell cannot decrease the total.
  3. Enumerate all triples of distinct rows in increasing order and, for each, every combination of one retained cell per row, at most 27, keeping only those with pairwise distinct columns.
  4. Track the best sum starting from negative infinity, not zero, since every cell may be negative; the tracked value is the best valid placement among triples examined so far.

Walkthrough of Example 2

board = [[-1,-5,-5],[-5,-2,-5],[-5,-5,-3]] → -6

  1. Row 0 is [-1, -5, -5]: top three are -1 at column 0, then -5 at columns 1 and 2.
  2. Row 1 is [-5, -2, -5]: -2 at column 1, then -5 at columns 0 and 2. Row 2 is [-5, -5, -3]: -3 at column 2, then -5 at columns 0 and 1.
  3. The only row triple is (0, 1, 2); the combination -1 (column 0), -2 (column 1), -3 (column 2) has distinct columns and sums to -6.
  4. Every other column-distinct combination includes a -5, such as -1 + -2 + -5 = -8.
  5. The answer is -6, negative because three rooks are mandatory.

Time and space

Time O(m * n + m^3) · Space O(m). Selecting top three per row touches all m * n cells; the enumeration visits about m^3 / 6 row triples with at most 27 constant-time checks each. Only three cells per row are stored.

Interview pitfalls

  • Initializing the best sum to 0, which returns 0 on an all-negative board instead of -6.
  • Keeping only the top two cells per row; two blocking rooks can eliminate both.
  • Checking column distinctness for only two of the three pairs.
  • Summing values up to 10^9 in magnitude with 32-bit integers; three of them exceed the signed range.

Follow-up questions interviewers ask

  • How would you reach O(m * n) by fixing the middle rook and keeping prefix and suffix best candidates with column exclusion?
  • How does the approach scale if k rooks must be placed, and at what k does top-k-per-row stop being practical?
  • What changes if rooks may share rows but not columns, or if some cells are forbidden?

Related LeetCode Problems

Practice more problems similar to Maximum Value Sum by Placing Three Rooks I.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.