Maximum Value Sum by Placing Three Rooks I

Maximum Value Sum by Placing Three Rooks I - Problem

You are given an 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.

Input & Output

Example 1 — Basic 3×3 Board

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

› Output: 15

💡 Note: Place rooks at (0,0), (1,1), (2,2): values 1+5+9=15. This is optimal since rooks are on different rows and columns.

Example 2 — Negative Values

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

› Output: 4

💡 Note: Place rooks at (0,1), (1,3), (2,1): values 1+1+2=4. Avoid negative values (-3) when possible.

Example 3 — All Same Values

$ Input: board = [[5,5,5],[5,5,5],[5,5,5]]

› Output: 15

💡 Note: Any valid placement gives the same sum: 5+5+5=15 since all cells have value 5.

Constraints

3 ≤ m, n ≤ 100
-10⁶ ≤ board[i][j] ≤ 10⁶
It's guaranteed that a solution exists

Visualization

Tap to expand

Understanding the Visualization

Input

3×3 chessboard with values [[1,2,3],[4,5,6],[7,8,9]]

Constraint

3 rooks must be on different rows AND different columns

Output

Maximum sum = 15 from positions (0,0)+(1,1)+(2,2) = 1+5+9

Key Takeaway

🎯 Key Insight: Rooks attack along rows and columns, so three non-attacking rooks need different rows AND different columns

Asked in

G Google 15 M Microsoft 12 A Amazon 8 f Meta 6

The key insight is that three non-attacking rooks must be placed on different rows AND different columns. The brute force approach tries all possible cell combinations while the optimized approach first selects row and column combinations, then finds the optimal assignment. Best approach: Row-Column Selection with Time: O(m³n³), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Row Selection with Column Optimization	O(m³ × n³)	O(1)	Choose 3 rows first, then find optimal column assignment for those rows
Brute Force Enumeration	O((mn)³)	O(1)	Try all possible combinations of 3 cells and check if they form valid rook placement

Row Selection with Column Optimization — Algorithm Steps

Choose all combinations of 3 rows from m rows
For each row combination, choose 3 different columns
Use optimal assignment to maximize sum for selected rows and columns

Visualization

Tap to expand

Step-by-Step Walkthrough

Select Rows

Choose 3 different rows (0,1,2)

Select Columns

Choose 3 different columns (0,1,2)

Optimize Assignment

Try all 6 ways to assign columns to rows

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** board, int m, int n) {
    int maxSum = INT_MIN;
    int perms[6][3] = {{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
    
    // Choose 3 rows
    for (int r1 = 0; r1 < m - 2; r1++) {
        for (int r2 = r1 + 1; r2 < m - 1; r2++) {
            for (int r3 = r2 + 1; r3 < m; r3++) {
                int rows[3] = {r1, r2, r3};
                
                // Choose 3 columns
                for (int c1 = 0; c1 < n - 2; c1++) {
                    for (int c2 = c1 + 1; c2 < n - 1; c2++) {
                        for (int c3 = c2 + 1; c3 < n; c3++) {
                            int cols[3] = {c1, c2, c3};
                            
                            // Try all permutations
                            for (int p = 0; p < 6; p++) {
                                int sum = board[rows[0]][cols[perms[p][0]]] +
                                         board[rows[1]][cols[perms[p][1]]] +
                                         board[rows[2]][cols[perms[p][2]]];
                                if (sum > maxSum) {
                                    maxSum = sum;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    return maxSum;
}

int main() {
    int board[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    int* boardPtrs[3] = {board[0], board[1], board[2]};
    
    int result = solution(boardPtrs, 3, 3);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m³ × n³)

C(m,3) row combinations × C(n,3) column combinations, each taking O(1)

⚠ Quadratic Growth

Space Complexity

O(1)

Only using variables to track combinations and maximum sum

✓ Linear Space

8.9K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Row Selection with Column Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler