Maximum Value Sum by Placing Three Rooks II

Maximum Value Sum by Placing Three Rooks II - Problem

You are given a m × 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 3x3 Board

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

› Output: 4

💡 Note: Place rooks at positions (0,2), (1,1), and (2,3). Sum = 1 + (-3) + 1 = -1. Actually, optimal is (0,1), (1,0), (2,2) giving 1 + 0 + 1 = 2. Wait, let me recalculate: (0,3)=1, (1,2)=1, (2,1)=2 gives sum = 4.

Example 2 — Negative Values

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

› Output: 15

💡 Note: Place rooks at positions (0,2), (1,1), and (2,0). Sum = 3 + 5 + 7 = 15.

Example 3 — Small Board

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

› Output: Cannot place 3 rooks on 2x2 board

💡 Note: Need at least 3 rows and 3 columns to place 3 non-attacking rooks.

Constraints

m == board.length
n == board[i].length
3 ≤ m, n ≤ 100
-10⁹ ≤ board[i][j] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Board

3x4 matrix with positive and negative values

Valid Placement

3 rooks on different rows and columns

Maximum Sum

Sum of values at selected positions

Key Takeaway

🎯 Key Insight: Fix one rook position and efficiently find optimal placements for the other two using precomputed sorted values.

Asked in

G Google 25 M Microsoft 18 A Amazon 15

The key insight is that with exactly 3 rooks, we can enumerate middle positions and efficiently find optimal first and third rook placements. The smart enumeration approach achieves O(m²n²) time by precomputing top values per row and avoiding redundant combinations.

Common Approaches

Approach	Time	Space	Notes
✓ Smart Enumeration with Pruning	O(m²n²)	O(mn)	Enumerate middle rook position and find optimal first and third rooks efficiently
Brute Force - Try All Combinations	O((mn)³)	O(1)	Check every possible placement of 3 rooks on different rows and columns

Smart Enumeration with Pruning — Algorithm Steps

Precompute top 2 values for each row and column
Enumerate middle rook positions
For each middle position, find best remaining values in other rows/columns
Calculate maximum possible sum efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

Precompute Top Values

Sort each row's values to quickly find best options

Fix Middle Position

For each middle rook, find optimal remaining positions

Calculate Maximum

Efficiently combine best values from different rows/columns

Code -

solution.c — C

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

typedef struct {
    int val;
    int col;
} Pair;

int compare(const void* a, const void* b) {
    return ((Pair*)b)->val - ((Pair*)a)->val;
}

int solution(int** board, int m, int n) {
    int maxSum = INT_MIN;
    
    // Precompute top values for each row
    Pair rowTop[10][10];
    int rowTopCount[10];
    
    for (int i = 0; i < m; i++) {
        Pair rowVals[10];
        for (int j = 0; j < n; j++) {
            rowVals[j].val = board[i][j];
            rowVals[j].col = j;
        }
        qsort(rowVals, n, sizeof(Pair), compare);
        
        int limit = (n < 2) ? n : 2;
        for (int k = 0; k < limit; k++) {
            rowTop[i][k] = rowVals[k];
        }
        rowTopCount[i] = limit;
    }
    
    // Enumerate middle rook positions
    for (int midR = 0; midR < m; midR++) {
        for (int midC = 0; midC < n; midC++) {
            int midVal = board[midR][midC];
            
            for (int firstR = 0; firstR < m; firstR++) {
                if (firstR == midR) continue;
                
                for (int fp = 0; fp < rowTopCount[firstR]; fp++) {
                    int firstVal = rowTop[firstR][fp].val;
                    int firstC = rowTop[firstR][fp].col;
                    if (firstC != midC) {
                        for (int thirdR = 0; thirdR < m; thirdR++) {
                            if (thirdR == midR || thirdR == firstR) continue;
                            
                            for (int tp = 0; tp < rowTopCount[thirdR]; tp++) {
                                int thirdVal = rowTop[thirdR][tp].val;
                                int thirdC = rowTop[thirdR][tp].col;
                                if (thirdC != midC && thirdC != firstC) {
                                    int total = firstVal + midVal + thirdVal;
                                    if (total > maxSum) {
                                        maxSum = total;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int board[10][10];
    int m = 3, n = 3;
    
    sscanf(line, "[[%d,%d,%d],[%d,%d,%d],[%d,%d,%d]]", 
           &board[0][0], &board[0][1], &board[0][2],
           &board[1][0], &board[1][1], &board[1][2],
           &board[2][0], &board[2][1], &board[2][2]);
    
    int* boardPtrs[10];
    for (int i = 0; i < m; i++) {
        boardPtrs[i] = board[i];
    }
    
    printf("%d\n", solution(boardPtrs, m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

For each of mn middle positions, we check remaining rows and columns to find optimal placements

⚠ Quadratic Growth

Space Complexity

O(mn)

Store precomputed top values for each row and column

⚡ Linearithmic Space

8.5K Views

Medium Frequency

~35 min Avg. Time

342 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

Smart Enumeration with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler