LeetCode 3257 - Maximum Value Sum by Placing Three Rooks II

We are given an m x n matrix called board, where each cell contains an integer value. We must place exactly three rooks on the board. A rook attacks every cell in the same row and the same column.

leetcodehardarraydynamic-programmingmatrixenumeration

LeetCode Problem 3257

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Matrix, Enumeration

Solution

Problem Understanding

We are given an m x n matrix called board, where each cell contains an integer value. We must place exactly three rooks on the board.

A rook attacks every cell in the same row and the same column. Therefore, for three rooks to be valid, no two rooks can share either a row or a column.

The goal is to maximize the sum of the values of the three chosen cells.

In other words, we want to select three positions:

  • (r1, c1)
  • (r2, c2)
  • (r3, c3)

such that:

  • r1, r2, and r3 are all different
  • c1, c2, and c3 are all different

and the sum:

$$board[r1][c1] + board[r2][c2] + board[r3][c3]$$

is as large as possible.

The constraints are important:

  • m, n <= 500
  • Values may be negative
  • We must place exactly three rooks

A 500 x 500 board contains 250,000 cells, so any solution that tries all triples of cells is completely infeasible.

The presence of negative values is also important. We cannot greedily take only positive cells because sometimes every valid placement may include negative numbers. Since we must place exactly three rooks, the algorithm must always return some valid triple even if the total is negative.

Another subtle issue is that choosing the three individually largest cells does not necessarily work because they may conflict in rows or columns.

Approaches

Brute Force

The most direct approach is to try every possible combination of three cells.

For each triple of cells, we would check:

  • whether all rows are distinct
  • whether all columns are distinct

If valid, compute the sum and update the answer.

This works because it explicitly examines every legal placement.

However, the board can contain up to:

$$500 \times 500 = 250000$$

cells.

Trying all triples would require:

$$O((mn)^3)$$

operations, which is astronomically too large.

Even a heavily optimized brute-force solution cannot handle this input size.

Key Insight

We only need three rooks.

That changes the problem dramatically.

For any row, only a very small number of columns are actually relevant. If a column is not among the largest values in that row, it is extremely unlikely to participate in the optimal answer.

The crucial observation is:

For a solution using only three rows and three columns, we only need to consider the top few candidates from each row.

Specifically:

  • For each row, keep only its top 3 values and corresponding columns.
  • Then enumerate combinations of three rows.
  • For those rows, try all combinations of their candidate columns.
  • Keep only combinations with distinct columns.

Why does this work?

Because each row contributes only one rook. If a row uses a column outside its top 3 choices, then at least three better choices existed in that row. Since only two columns can be blocked by the other rooks, at least one better column would still remain available. Therefore an optimal solution never needs a column outside the top 3 for a row.

This reduces the search space enormously.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O((mn)^3) O(1) Tries every triple of cells
Optimal O(mn + m^3) O(m) Keeps only top 3 cells per row

Algorithm Walkthrough

Step 1: Compute the top 3 cells for every row

For each row:

  • scan all columns
  • keep the three largest (value, column) pairs

We only need three because:

  • one column may conflict with rook #2
  • one column may conflict with rook #3
  • at least one top choice will still remain

This dramatically reduces the candidate space.

For each row we store:

[(value1, col1), (value2, col2), (value3, col3)]

sorted from largest to smallest value.

Step 2: Enumerate all triples of rows

Since rooks cannot share rows, we choose three distinct rows.

We iterate through:

r1 < r2 < r3

There are at most:

$$\binom{500}{3} \approx 20.7 \text{ million}$$

triples.

That sounds large, but the work per triple is tiny and bounded.

Step 3: Try all candidate column combinations

Each row has at most 3 candidate columns.

Therefore:

  • row 1 contributes at most 3 choices
  • row 2 contributes at most 3 choices
  • row 3 contributes at most 3 choices

Total combinations per row triple:

$$3 \times 3 \times 3 = 27$$

For every combination:

  • check whether the columns are distinct
  • if valid, compute the sum
  • update the answer

Step 4: Return the maximum sum

Because we examine every valid combination among the necessary candidate cells, the maximum encountered sum is the answer.

Why it works

For any row in an optimal solution, suppose the chosen column is not among the row's top 3 values.

Then there exist at least three strictly better columns in that row.

At most two columns are forbidden by the other two rooks. Therefore at least one better column remains available.

Replacing the chosen column with that better available column would improve the solution, contradicting optimality.

Thus every rook in an optimal solution must come from the top 3 values of its row.

Since the algorithm exhaustively checks all such possibilities, it must find the optimal answer.

Python Solution

from typing import List

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        m = len(board)
        n = len(board[0])

        # top3[row] = list of (value, col)
        top3 = []

        for row in board:
            candidates = []

            for col, value in enumerate(row):
                candidates.append((value, col))

            candidates.sort(reverse=True)
            top3.append(candidates[:3])

        answer = -10**18

        for r1 in range(m):
            for r2 in range(r1 + 1, m):
                for r3 in range(r2 + 1, m):

                    for v1, c1 in top3[r1]:
                        for v2, c2 in top3[r2]:
                            if c1 == c2:
                                continue

                            for v3, c3 in top3[r3]:
                                if c1 == c3 or c2 == c3:
                                    continue

                                answer = max(answer, v1 + v2 + v3)

        return answer

The implementation starts by preprocessing each row independently.

For every row, we collect all (value, column) pairs and sort them in descending order. We then keep only the top three entries.

The nested loops over r1, r2, and r3 enumerate all valid row selections because rooks cannot share rows.

For each row triple, the algorithm tries every combination among the top three candidates of those rows. Since there are only 27 combinations, this portion is very small.

The column checks ensure that no two rooks attack each other. If all three columns are distinct, the sum is computed and used to update the global maximum.

The answer is initialized to a very negative number because board values may all be negative.

Go Solution

package main

import "sort"

func maximumValueSum(board [][]int) int64 {
	m := len(board)
	n := len(board[0])

	type Pair struct {
		value int
		col   int
	}

	top3 := make([][]Pair, m)

	for r := 0; r < m; r++ {
		candidates := make([]Pair, 0, n)

		for c := 0; c < n; c++ {
			candidates = append(candidates, Pair{
				value: board[r][c],
				col:   c,
			})
		}

		sort.Slice(candidates, func(i, j int) bool {
			return candidates[i].value > candidates[j].value
		})

		top3[r] = candidates[:3]
	}

	var answer int64 = -1 << 60

	for r1 := 0; r1 < m; r1++ {
		for r2 := r1 + 1; r2 < m; r2++ {
			for r3 := r2 + 1; r3 < m; r3++ {

				for _, p1 := range top3[r1] {
					for _, p2 := range top3[r2] {

						if p1.col == p2.col {
							continue
						}

						for _, p3 := range top3[r3] {

							if p1.col == p3.col || p2.col == p3.col {
								continue
							}

							sum := int64(p1.value + p2.value + p3.value)

							if sum > answer {
								answer = sum
							}
						}
					}
				}
			}
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python solution.

One important difference is integer handling. Since board values can be as large as 1e9, the total sum can reach 3e9, which exceeds 32-bit signed integer range. Therefore the final answer uses int64.

Slices are used to store the top three candidates per row. The sort.Slice function sorts each row's candidate list in descending order.

Worked Examples

Example 1

board =
[
  [-3, 1, 1, 1],
  [-3, 1, -3, 1],
  [-3, 2, 1, 1]
]

Step 1: Top 3 values per row

Row Top 3 Candidates
0 (1,1) (1,2) (1,3)
1 (1,1) (1,3) (-3,0)
2 (2,1) (1,2) (1,3)

Step 2: Only one row triple exists

(0,1,2)

Step 3: Try candidate combinations

Row 0 Row 1 Row 2 Valid? Sum
(1,1) (1,1) (2,1) No -
(1,1) (1,3) (1,2) Yes 3
(1,2) (1,3) (2,1) Yes 4

Maximum becomes 4.

Final answer:

4

Example 2

board =
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

Top candidates

Row Candidates
0 (3,2) (2,1) (1,0)
1 (6,2) (5,1) (4,0)
2 (9,2) (8,1) (7,0)

Trying valid combinations:

Columns Sum
(2,1,0) 3+5+7=15
(1,0,2) 2+4+9=15

Maximum:

15

Example 3

board =
[
  [1,1,1],
  [1,1,1],
  [1,1,1]
]

Any permutation of three distinct columns works.

One valid placement:

Position Value
(0,2) 1
(1,1) 1
(2,0) 1

Total:

3

Complexity Analysis

Measure Complexity Explanation
Time O(mn + m^3) Preprocessing rows plus enumerating row triples
Space O(m) Stores only top 3 candidates per row

The preprocessing step scans every cell once, costing O(mn).

The dominant portion is enumerating triples of rows. There are:

$$O(m^3)$$

such triples.

For each triple we perform at most 27 constant-time checks, so the inner work is constant.

The memory usage is small because we store only three candidate cells per row.

Test Cases

from typing import List

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        m = len(board)
        n = len(board[0]

        top3 = []

        for row in board:
            candidates = []

            for col, value in enumerate(row):
                candidates.append((value, col))

            candidates.sort(reverse=True)
            top3.append(candidates[:3])

        answer = -10**18

        for r1 in range(m):
            for r2 in range(r1 + 1, m):
                for r3 in range(r2 + 1, m):

                    for v1, c1 in top3[r1]:
                        for v2, c2 in top3[r2]:
                            if c1 == c2:
                                continue

                            for v3, c3 in top3[r3]:
                                if c1 == c3 or c2 == c3:
                                    continue

                                answer = max(answer, v1 + v2 + v3)

        return answer

sol = Solution()

assert sol.maximumValueSum([
    [-3,1,1,1],
    [-3,1,-3,1],
    [-3,2,1,1]
]) == 4  # provided example with negatives

assert sol.maximumValueSum([
    [1,2,3],
    [4,5,6],
    [7,8,9]
]) == 15  # increasing values

assert sol.maximumValueSum([
    [1,1,1],
    [1,1,1],
    [1,1,1]
]) == 3  # all equal values

assert sol.maximumValueSum([
    [-1,-2,-3],
    [-4,-5,-6],
    [-7,-8,-9]
]) == -15  # all negative values

assert sol.maximumValueSum([
    [100,1,1],
    [1,100,1],
    [1,1,100]
]) == 300  # diagonal optimal

assert sol.maximumValueSum([
    [10,9,8],
    [10,1,1],
    [10,1,1]
]) == 20  # must avoid same column

assert sol.maximumValueSum([
    [5,4,3,2],
    [9,8,7,6],
    [1,2,3,4]
]) == 17  # mixed choices

assert sol.maximumValueSum([
    [10**9,1,1],
    [1,10**9,1],
    [1,1,10**9]
]) == 3 * 10**9  # large values

Test Summary

Test Why
Mixed positive and negative values Verifies valid placement selection
Strictly increasing matrix Tests obvious diagonal optimum
All equal values Confirms any valid placement works
All negative values Ensures algorithm still places exactly 3 rooks
Large diagonal values Tests maximum selection
Shared best column Ensures conflict handling works
Mixed rectangular board Validates general correctness
Very large values Tests integer overflow handling

Edge Cases

All values are negative

This is a common source of bugs because some implementations incorrectly assume that skipping placements is allowed. The problem requires placing exactly three rooks, even if the total becomes negative.

The implementation handles this correctly by initializing the answer to a very small number and always evaluating valid triples.

Multiple rows prefer the same column

Several rows may have their largest value in the same column. A greedy algorithm that independently chooses the maximum value from each row would fail.

The implementation explicitly checks column conflicts before accepting a combination, ensuring that all three columns are distinct.

Many duplicate values

When rows contain repeated values, there may be many equally optimal solutions. Some algorithms accidentally discard duplicates incorrectly during preprocessing.

This implementation keeps (value, column) pairs, not just values, so duplicate values in different columns remain distinguishable and valid placements are preserved.