Problem

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.

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|c|} \hline -3 & 1 & \fbox{1} ♖ & 1 \\ \hline -3 & 1 & -3 & \fbox{1} ♖ \\ \hline -3 & \fbox{2} ♖ & 1 & 1 \\ \hline \end{array} $$

1
2
3
4

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`.

Selected rook cells: (0,2), (1,3), (2,1) → sum = $1 + 1 + 2 = 4$.

Example 2

$$ \Huge \begin{array}{|c|c|c|} \hline \fbox{1} & 2 & 3 \\ \hline 4 & \fbox{5} & 6 \\ \hline 7 & 8 & \fbox{9} \\ \hline \end{array} $$

1
2
3
4

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`.

Selected rook cells: (0,0), (1,1), (2,2) → sum = $1 + 5 + 9 = 15$.

Example 3

$$ \Huge \begin{array}{|c|c|c|} \hline 1 & 1 & \fbox{1} \\ \hline 1 & \fbox{1} & 1 \\ \hline \fbox{1} & 1 & 1 \\ \hline \end{array} $$

1
2
3
4

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`.

Selected rook cells: (0,2), (1,1), (2,0) → sum = $1 + 1 + 1 = 3$.

Constraints

  • 3 <= m == board.length <= 100
  • 3 <= n == board[i].length <= 100
  • -10^9 <= board[i][j] <= 10^9
Similar Problems

Solution

Method 1 – Enumeration of All Valid Placements

Intuition

To maximize the sum, we need to place three rooks on the board such that no two share a row or column. This is equivalent to choosing three distinct rows and three distinct columns, and summing the values at those intersections. Enumerating all such combinations gives the optimal answer.

Approach

  1. For all combinations of three distinct rows and three distinct columns:
    • For each permutation of columns, sum the values at (row[i], col[perm[i]]).
    • Track the maximum sum found.
  2. Return the maximum sum.

Complexity

  • ⏰ Time complexity: O(m^3 * n^3 * 6) — All combinations of rows and columns, and all permutations (6) for each.
  • 🧺 Space complexity: O(1) — Only variables for tracking maximum sum.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int maxValueSum(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size(), ans = INT_MIN;
        vector<int> rows(m), cols(n);
        iota(rows.begin(), rows.end(), 0);
        iota(cols.begin(), cols.end(), 0);
        for (int r1 = 0; r1 < m; ++r1)
        for (int r2 = r1+1; r2 < m; ++r2)
        for (int r3 = r2+1; r3 < m; ++r3)
        for (int c1 = 0; c1 < n; ++c1)
        for (int c2 = c1+1; c2 < n; ++c2)
        for (int c3 = c2+1; c3 < n; ++c3) {
            vector<int> r = {r1, r2, r3}, c = {c1, c2, c3};
            sort(c.begin(), c.end());
            do {
                int sum = 0;
                for (int i = 0; i < 3; ++i) sum += board[r[i]][c[i]];
                ans = max(ans, sum);
            } while (next_permutation(c.begin(), c.end()));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func maxValueSum(board [][]int) int {
    m, n := len(board), len(board[0])
    ans := -1 << 31
    rows := make([]int, m)
    cols := make([]int, n)
    for i := range rows { rows[i] = i }
    for i := range cols { cols[i] = i }
    for r1 := 0; r1 < m; r1++ {
        for r2 := r1+1; r2 < m; r2++ {
            for r3 := r2+1; r3 < m; r3++ {
                for c1 := 0; c1 < n; c1++ {
                    for c2 := c1+1; c2 < n; c2++ {
                        for c3 := c2+1; c3 < n; c3++ {
                            c := []int{c1, c2, c3}
                            perm := [][]int{{c[0],c[1],c[2]},{c[0],c[2],c[1]},{c[1],c[0],c[2]},{c[1],c[2],c[0]},{c[2],c[0],c[1]},{c[2],c[1],c[0]}}
                            r := []int{r1, r2, r3}
                            for _, p := range perm {
                                sum := 0
                                for i := 0; i < 3; i++ { sum += board[r[i]][p[i]] }
                                if sum > ans { ans = sum }
                            }
                        }
                    }
                }
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int maxValueSum(int[][] board) {
        int m = board.length, n = board[0].length, ans = Integer.MIN_VALUE;
        for (int r1 = 0; r1 < m; ++r1)
        for (int r2 = r1+1; r2 < m; ++r2)
        for (int r3 = r2+1; r3 < m; ++r3)
        for (int c1 = 0; c1 < n; ++c1)
        for (int c2 = c1+1; c2 < n; ++c2)
        for (int c3 = c2+1; c3 < n; ++c3) {
            int[] r = {r1, r2, r3}, c = {c1, c2, c3};
            int[][] perm = {{c[0],c[1],c[2]},{c[0],c[2],c[1]},{c[1],c[0],c[2]},{c[1],c[2],c[0]},{c[2],c[0],c[1]},{c[2],c[1],c[0]}};
            for (int[] p : perm) {
                int sum = 0;
                for (int i = 0; i < 3; ++i) sum += board[r[i]][p[i]];
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    fun maxValueSum(board: Array<IntArray>): Int {
        val m = board.size
        val n = board[0].size
        var ans = Int.MIN_VALUE
        for (r1 in 0 until m)
        for (r2 in r1+1 until m)
        for (r3 in r2+1 until m)
        for (c1 in 0 until n)
        for (c2 in c1+1 until n)
        for (c3 in c2+1 until n) {
            val r = listOf(r1, r2, r3)
            val c = listOf(c1, c2, c3)
            val perm = listOf(
                listOf(c[0],c[1],c[2]), listOf(c[0],c[2],c[1]), listOf(c[1],c[0],c[2]),
                listOf(c[1],c[2],c[0]), listOf(c[2],c[0],c[1]), listOf(c[2],c[1],c[0])
            )
            for (p in perm) {
                var sum = 0
                for (i in 0..2) sum += board[r[i]][p[i]]
                ans = maxOf(ans, sum)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from typing import List

class Solution:
    def maximumValueSum(self, board: List[List[int]]) -> int:
        from itertools import combinations, permutations
        m, n = len(board), len(board[0])
        ans = float('-inf')
        for rows in combinations(range(m), 3):
            for cols in combinations(range(n), 3):
                for perm in permutations(cols):
                    s = sum(board[rows[i]][perm[i]] for i in range(3))
                    ans = max(ans, s)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

impl Solution {
    pub fn max_value_sum(board: Vec<Vec<i32>>) -> i32 {
        let m = board.len();
        let n = board[0].len();
        let mut ans = i32::MIN;
        for r1 in 0..m {
            for r2 in r1+1..m {
                for r3 in r2+1..m {
                    for c1 in 0..n {
                        for c2 in c1+1..n {
                            for c3 in c2+1..n {
                                let r = [r1, r2, r3];
                                let c = [c1, c2, c3];
                                let perms = [
                                    [c[0],c[1],c[2]],[c[0],c[2],c[1]],[c[1],c[0],c[2]],
                                    [c[1],c[2],c[0]],[c[2],c[0],c[1]],[c[2],c[1],c[0]]
                                ];
                                for p in &perms {
                                    let sum = (0..3).map(|i| board[r[i]][p[i]]).sum();
                                    ans = ans.max(sum);
                                }
                            }
                        }
                    }
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    maxValueSum(board: number[][]): number {
        const m = board.length, n = board[0].length;
        let ans = -Infinity;
        for (let r1 = 0; r1 < m; ++r1)
        for (let r2 = r1+1; r2 < m; ++r2)
        for (let r3 = r2+1; r3 < m; ++r3)
        for (let c1 = 0; c1 < n; ++c1)
        for (let c2 = c1+1; c2 < n; ++c2)
        for (let c3 = c2+1; c3 < n; ++c3) {
            const r = [r1, r2, r3], c = [c1, c2, c3];
            const perms = [
                [c[0],c[1],c[2]],[c[0],c[2],c[1]],[c[1],c[0],c[2]],
                [c[1],c[2],c[0]],[c[2],c[0],c[1]],[c[2],c[1],c[0]]
            ];
            for (const p of perms) {
                let sum = 0;
                for (let i = 0; i < 3; ++i) sum += board[r[i]][p[i]];
                ans = Math.max(ans, sum);
            }
        }
        return ans;
    }
}