LeetCode 3256 - Maximum Value Sum by Placing Three Rooks I

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 square in the same row and the same column.

leetcodehardarraydynamic-programmingmatrixenumeration

LeetCode Problem 3256

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 square in the same row and the same column. Therefore, for three rooks to be valid:

  • No two rooks can share the same row
  • No two rooks can share the same column

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

In other words, we want to select three distinct rows and three distinct columns, then pair them so that each selected row gets exactly one selected column, producing the maximum possible total value.

The constraints are important:

  • m, n <= 100
  • Cell values can be as small as -10^9

Since the board can contain negative values, we cannot assume that picking more cells always improves the answer. We are forced to place exactly three rooks, even if some selected values are negative.

A naive solution that tries every possible placement of three rooks would be extremely expensive. A 100 x 100 board has 10,000 cells, and choosing three non-conflicting cells by brute force would involve an enormous number of combinations.

Important edge cases include:

  • Boards where every value is negative
  • Boards where the best cells share rows or columns, forcing tradeoffs
  • Smallest valid boards, such as 3 x 3
  • Multiple optimal solutions with the same maximum sum
  • Large positive and negative mixtures

The problem guarantees:

  • At least 3 rows and 3 columns exist
  • A valid placement of three non-attacking rooks is always possible

Approaches

Brute Force Approach

The most direct solution is to enumerate every possible placement of three rooks.

We can:

  1. Choose any three cells from the board
  2. Check whether all rows are distinct
  3. Check whether all columns are distinct
  4. Compute the sum if valid
  5. Track the maximum

If the board has m * n cells, then the number of triples is:

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

With 100 x 100 = 10,000 cells, this becomes completely infeasible.

Even if we optimize slightly by iterating row-by-row, the complexity is still far too large for the constraints.

Key Insight

We only need three rooks.

That changes the problem dramatically.

Instead of considering all cells globally, we can think about selecting:

  • One row for the first rook
  • One row for the second rook
  • One row for the third rook

Then we only need to choose distinct columns for those rows.

The crucial observation is that for each row, only a few large values actually matter. A very small value is unlikely to appear in an optimal solution.

We can keep only the top few candidates from each row. Since we only place three rooks, keeping the top 3 columns per row is sufficient.

Why?

Because at most two columns can become unavailable due to conflicts with previously chosen rooks. If we keep the best three columns in each row, at least one valid candidate will always remain.

This reduces the search space enormously.

We can:

  1. Precompute the top 3 cells for every row
  2. Enumerate every combination of 3 rows
  3. Try all candidate combinations from those rows
  4. Ensure columns are distinct
  5. Compute the best sum

The resulting complexity becomes manageable.

Approach Comparison

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

Algorithm Walkthrough

Step 1: Compute the best candidates for each row

For every row, we find the top 3 cells with the highest values.

Each candidate stores:

  • The cell value
  • Its column index

We only keep three because:

  • We place exactly three rooks
  • At most two columns can become blocked
  • One valid choice must still remain

Example:

Row: [4, 9, 2, 7]

Top 3:
(9, col=1)
(7, col=3)
(4, col=0)

Step 2: Enumerate all triples of rows

We choose every combination of three distinct rows:

r1 < r2 < r3

Since m <= 100, iterating over all row triples is feasible.

The number of combinations is at most:

$$\binom{100}{3} \approx 161,700$$

Step 3: Try candidate combinations

For each row triple:

  • Try every candidate from row r1
  • Try every candidate from row r2
  • Try every candidate from row r3

Since each row has only 3 candidates:

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

possibilities exist for each row triple.

Step 4: Enforce column uniqueness

Before computing the sum, verify:

c1 != c2
c1 != c3
c2 != c3

This guarantees the rooks do not attack each other.

Step 5: Update the answer

Compute:

value1 + value2 + value3

Update the global maximum.

Why it works

The algorithm works because an optimal solution never needs a row candidate outside the top 3 values of that row.

When placing three rooks, at most two columns become unavailable for any row due to conflicts with the other rooks. Therefore, among the top three candidates in that row, at least one column must remain usable.

By enumerating all row triples and all top-candidate combinations, we guarantee that every optimal configuration is considered.

Python Solution

from typing import List

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

        # Store top 3 candidates for each row
        # Each candidate is (value, column)
        top_candidates = []

        for row in board:
            candidates = []

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

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

        answer = float("-inf")

        # Enumerate all triples of rows
        for r1 in range(m):
            for r2 in range(r1 + 1, m):
                for r3 in range(r2 + 1, m):

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

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

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

        return answer

The implementation begins by preprocessing each row independently. For every row, we collect all (value, column) pairs and sort them in descending order by value. Only the top three are retained.

The main computation then iterates through every triple of rows. Since rooks cannot share rows, this guarantees row uniqueness automatically.

For each selected row triple, we enumerate every combination of candidates from the three rows. Because each row contributes at most three candidates, only 27 combinations must be checked.

Before computing a sum, we verify that all chosen columns are distinct. This ensures the rooks do not attack each other.

Finally, the maximum valid sum is returned.

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
	}

	// Top 3 candidates for each row
	topCandidates := make([][]Pair, m)

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

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

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

		topCandidates[i] = candidates[:3]
	}

	const NEG_INF int64 = -1 << 60
	answer := NEG_INF

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

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

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

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

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

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

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

	return answer
}

The Go implementation follows the same logic as the Python version. A small Pair struct stores the cell value and column index.

One important difference is integer handling. Since board values can be as large as 10^9, the total sum can exceed the range of a 32-bit integer. Therefore, the final answer and all computed sums use int64.

The rest of the implementation mirrors the Python solution closely.

Worked Examples

Example 1

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

Step 1: Top candidates per row

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

Step 2: Choose rows (0,1,2)

Now enumerate candidate combinations.

Row 0 Row 1 Row 2 Valid? Sum
(1,1) (1,1) (2,1) No -
(1,1) (1,3) (2,1) No -
(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 Top Candidates
0 (3,2), (2,1), (1,0)
1 (6,2), (5,1), (4,0)
2 (9,2), (8,1), (7,0)

Trying combinations:

Selection Columns Distinct? Sum
3 + 6 + 9 No -
3 + 5 + 7 Yes 15
2 + 6 + 7 Yes 15

Maximum answer:

15

Example 3

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

Any valid placement works.

One choice:

Row Column Value
0 0 1
1 1 1
2 2 1

Total:

3

Complexity Analysis

Measure Complexity Explanation
Time O(m³) Enumerating row triples dominates
Space O(m) Stores top 3 candidates per row

The preprocessing step sorts each row, costing:

$$O(m \cdot n \log n)$$

Since n <= 100, this is small.

The dominant part is iterating over all triples of rows:

$$O(m^3)$$

For each row triple, only 27 candidate combinations are tested, which is constant time.

The memory usage is linear because we store only three candidates 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])

        top_candidates = []

        for row in board:
            candidates = []

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

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

        answer = float("-inf")

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

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

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

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

        return answer

sol = Solution()

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

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

# Provided example 3
assert sol.maximumValueSum([
    [1,1,1],
    [1,1,1],
    [1,1,1]
]) == 3

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

# Best values share columns, forcing tradeoff
assert sol.maximumValueSum([
    [100,1,1],
    [100,1,1],
    [100,1,1]
]) == 102

# Minimum board size
assert sol.maximumValueSum([
    [5,1,1],
    [1,5,1],
    [1,1,5]
]) == 15

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

# Mixed positive and negative
assert sol.maximumValueSum([
    [8,-100,3],
    [4,5,-100],
    [-100,6,7]
]) == 20

# Multiple optimal solutions
assert sol.maximumValueSum([
    [5,5,1],
    [5,5,1],
    [1,1,5]
]) == 15

Test Summary

Test Why
Example 1 Validates handling of negatives and column conflicts
Example 2 Standard increasing matrix
Example 3 All equal values
All negative values Ensures exactly three rooks are still placed
Shared best columns Forces algorithm to avoid conflicts
Minimum board size Smallest valid dimensions
Large values Validates overflow safety
Mixed positive/negative Tests realistic tradeoffs
Multiple optimal solutions Ensures algorithm does not depend on uniqueness

Edge Cases

All Values Are Negative

A common mistake is assuming we can skip placing a rook when values are negative. The problem requires exactly three rooks.

For example:

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

The algorithm still enumerates every valid configuration and returns the least negative valid sum. Initializing the answer to negative infinity ensures correctness.

Best Cells Share the Same Column

Consider:

[
  [100,1,1],
  [100,1,1],
  [100,1,1]
]

A greedy algorithm that independently picks the best value from each row would fail because all three selections use the same column.

Our implementation explicitly checks column uniqueness before accepting a configuration, guaranteeing valid rook placement.

Multiple Candidates Have Equal Values

Some rows may contain repeated values:

[1,1,1,1]

If we only stored a single best value per row, we could incorrectly discard useful columns.

By storing the top three (value, column) pairs, the algorithm preserves alternative columns even when values are tied, ensuring that valid combinations are not missed.