# Maximum Value Sum by Placing Three Rooks I **Difficulty:** HARD [External](https://leetcode.com/problems/maximum-value-sum-by-placing-three-rooks-i) Canonical: https://scaleengineer.com/dsa/problems/maximum-value-sum-by-placing-three-rooks-i **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration) **Data structures:** Array, Matrix --- ## 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. **Example 1:** **Input:** board = \[\[-3,1,1,1\],\[-3,1,-3,1\],\[-3,2,1,1\]\] **Output:** 4 **Explanation:** ![](https://assets.glich.co/dsa/maximum-value-sum-by-placing-three-rooks-i/image0.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:** **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:** **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 <= 100` * `3 <= n == board[i].length <= 100` * `-109 <= board[i][j] <= 109` # Approaches ## Brute Force Enumeration This approach explores every possible valid placement of three rooks. A valid placement requires the three rooks to be in distinct rows and distinct columns. The algorithm iterates through all combinations of three different rows and three different columns, then checks all possible non-attacking configurations within that 3x3 selection, updating the maximum sum found. **Time:** O(m³ * n³). There are `O(m³)` ways to choose 3 rows and `O(n³)` ways to choose 3 columns. The inner calculations are constant time. · **Space:** O(1) extra space. **Pros:** Conceptually simple and easy to understand.; Correctly solves the problem for very small boards. **Cons:** The time complexity is extremely high, making it infeasible for the given constraints.; It will result in a 'Time Limit Exceeded' (TLE) error on most platforms. ### Explanation The most straightforward way to solve the problem is to exhaustively check every single combination of three cells that satisfy the non-attacking condition. We can structure this by first selecting three distinct rows, then selecting three distinct columns. This defines a 3x3 subgrid of cells. Within this subgrid, there are `3! = 6` ways to place the three rooks such that they don't attack each other (one in each row and column of the subgrid). We calculate the sum for each of these 6 placements and find the maximum. By repeating this for all possible 3-row and 3-column combinations, we can find the global maximum sum. ```java class Solution { public long maximumValueSum(int[][] board) { int m = board.length; int n = board[0].length; long maxSum = Long.MIN_VALUE; if (m < 3 || n < 3) { return 0; // Not possible to place 3 non-attacking rooks } 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++) { // Rows: r1, r2, r3 // Cols: c1, c2, c3 // Check all 6 permutations for placing rooks long currentMax = 0; long v11 = board[r1][c1], v12 = board[r1][c2], v13 = board[r1][c3]; long v21 = board[r2][c1], v22 = board[r2][c2], v23 = board[r2][c3]; long v31 = board[r3][c1], v32 = board[r3][c2], v33 = board[r3][c3]; currentMax = Math.max(currentMax, v11 + v22 + v33); currentMax = Math.max(currentMax, v11 + v23 + v32); currentMax = Math.max(currentMax, v12 + v21 + v33); currentMax = Math.max(currentMax, v12 + v23 + v31); currentMax = Math.max(currentMax, v13 + v21 + v32); currentMax = Math.max(currentMax, v13 + v22 + v31); maxSum = Math.max(maxSum, currentMax); } } } } } } return maxSum; } } ``` ### Algorithm * Initialize a variable `maxSum` to a very small value (e.g., `Long.MIN_VALUE`). * Use six nested loops to iterate through all possible combinations of three distinct row indices `r1, r2, r3` and three distinct column indices `c1, c2, c3`. * To avoid redundant checks and reduce iterations slightly, ensure `r1 < r2 < r3` and `c1 < c2 < c3` in the loops. * For each combination of three rows and three columns, we have a 3x3 subgrid. There are `3! = 6` ways to place three non-attacking rooks within this subgrid. * Calculate the sum of values for each of these 6 placements. * `sum1 = board[r1][c1] + board[r2][c2] + board[r3][c3]` * `sum2 = board[r1][c1] + board[r2][c3] + board[r3][c2]` * ... and so on for all 6 permutations of columns `(c1, c2, c3)` for rows `(r1, r2, r3)`. * Update `maxSum` with the maximum sum found among these 6 possibilities. * After all loops complete, `maxSum` will hold the maximum possible sum. ## Dynamic Programming over a Fixed Set of Rows/Columns This optimized approach significantly reduces the complexity by breaking the problem down. We iterate through all combinations of three rows (or columns, whichever dimension is smaller). For each fixed set of three rows, we then use dynamic programming to efficiently find the optimal placement of rooks in three distinct columns. This avoids the costly cubic iteration over the second dimension. **Time:** O(min(m, n)³ * max(m, n)). By ensuring the cubic iteration happens over the smaller dimension, we optimize the performance. For a square board, it's O(n⁴). · **Space:** O(1) or O(2^k) where k=3. The DP table size is constant (8), so it's O(1) extra space. **Pros:** Significantly more efficient than the brute-force approach.; Guaranteed to pass within the time limits for the given constraints.; It's a standard technique for this type of selection problem (fixing some parameters and using DP for the rest). **Cons:** The implementation is more complex than the brute-force approach.; Requires careful handling of DP states and transitions. ### Explanation The key insight is that once we fix the three rows, say `r1, r2, r3`, the problem reduces to selecting three distinct columns `c1, c2, c3` and a permutation to maximize the sum. This subproblem can be solved much faster than brute force. We can define a dynamic programming state `dp[mask]` representing the maximum sum achievable using a subset of columns processed so far, where `mask` indicates which of the three chosen rows (`r1, r2, r3`) are occupied. The mask is a 3-bit integer. For example, `mask = 5` (binary `101`) means rooks have been placed in rows `r1` and `r3`. We iterate through each column of the board one by one. For each column, we update our `dp` table. We can either skip the current column or place a rook in it in one of the three chosen rows (if that row is not already occupied). After iterating through all columns, `dp[7]` (binary `111`) will give the maximum sum for the fixed set of rows, as all three rows are now occupied. The overall algorithm iterates through all `O(m³)` combinations of rows and solves the `O(n)` DP subproblem for each, leading to a total time complexity of `O(m³ * n)`. To optimize, we can ensure `m <= n` by transposing the board if `m > n`, making the complexity `O(min(m,n)³ * max(m,n))`, which is efficient enough for the given constraints. ```java import java.util.Arrays; class Solution { public long maximumValueSum(int[][] board) { int m = board.length; int n = board[0].length; if (m < n) { // Transpose the board to ensure m >= n, so we iterate over the smaller dimension cubically. int[][] transposedBoard = new int[n][m]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { transposedBoard[j][i] = board[i][j]; } } board = transposedBoard; int temp = m; m = n; n = temp; } // Now m >= n, we will iterate O(n^3) and DP on m rows. long maxSum = Long.MIN_VALUE; for (int c1 = 0; c1 < n; c1++) { for (int c2 = c1 + 1; c2 < n; c2++) { for (int c3 = c2 + 1; c3 < n; c3++) { int[] cols = {c1, c2, c3}; // DP to find best 3 rows for these 3 columns long[] dp = new long[1 << 3]; Arrays.fill(dp, Long.MIN_VALUE); dp[0] = 0; for (int r = 0; r < m; r++) { long[] next_dp = dp.clone(); for (int mask = 0; mask < (1 << 3); mask++) { if (dp[mask] == Long.MIN_VALUE) continue; for (int i = 0; i < 3; i++) { if ((mask & (1 << i)) == 0) { // if i-th rook is not placed int new_mask = mask | (1 << i); long val = board[r][cols[i]]; if (next_dp[new_mask] == Long.MIN_VALUE || dp[mask] + val > next_dp[new_mask]) { next_dp[new_mask] = dp[mask] + val; } } } } dp = next_dp; } if (dp[7] != Long.MIN_VALUE) { maxSum = Math.max(maxSum, dp[7]); } } } } return maxSum; } } ``` ### Algorithm * First, check if `m > n`. If so, it's more efficient to iterate through combinations of columns instead of rows. For simplicity, we can transpose the board so that the number of rows `m` is always less than or equal to the number of columns `n`. * Initialize `maxSum` to a very small value. * Iterate through all combinations of three distinct rows: `r1`, `r2`, `r3`. This takes `O(m³)` time. * For each combination of three rows, solve a subproblem: find the maximum sum by picking three distinct columns. This subproblem can be solved in `O(n)` time using dynamic programming. * **DP Subproblem:** * Let `dp[mask]` be the maximum sum using `popcount(mask)` rooks, placed in some subset of columns, occupying the rows specified by `mask`. `mask` is a 3-bit integer where the i-th bit corresponds to the i-th chosen row. * Initialize `dp` array of size 8 with `dp[0] = 0` and all other `dp[mask] = -infinity`. * Iterate through each column `j` from `0` to `n-1`. * In each iteration, create a `next_dp` array from the current `dp` array. For each `mask`, try to place a rook in column `j` in an unused row `i` (where the i-th bit in `mask` is 0). Update `next_dp[mask | (1<