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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

Output: 4

Explanation:

![](https://assets.leetcode.com/uploads/2024/08/08/rooks2.png)

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

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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 <= 500
  • 3 <= n == board[i].length <= 500
  • -109 <= board[i][j] <= 10^9

Solution

Method 1 – Dynamic Programming with Bitmask

Intuition

Instead of brute-forcing all placements, we use dynamic programming with bitmasking to efficiently track which rows and columns are used. For each combination of three rows and three columns, we try all permutations and use DP to avoid redundant calculations.

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. Use memoization to avoid recalculating for the same set of rows/columns.
  3. 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.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int maxValueSum(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size(), ans = INT_MIN;
        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;
    }
};
Go
 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

func maxValueSum(board [][]int) int {
    m, n := len(board), len(board[0])
    ans := -1 << 31
    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
}
Java
 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;
    }
}
Kotlin
 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
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def max_value_sum(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
Rust
 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
    }
}
TypeScript
 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;
    }
}