What is the maximum sum of squares of two non-attacking rooks placed on a matrix?

Question

There is a m x n matrix given each with integer elements. The problem says that we have to place two rooks on that matrix, such that they don't attack each other and the sum of the elements on which the rooks are placed is maximum.

Example: Let's say matrix is

2 5
1 3

Then non-attacking rooks can be placed only on 2,3 or 1,5 element positions. But the maximum sum is found in case of 1,5, so the function should return 1 + 5 = 6.

I thought that we could go through all the pairs of the array one by one and then return the maximum sum that we found, but I can't seem to find a better or efficient approach for this. My solution would be O(m * m * n * n) in terms of complexity.

What would be a better approach? I would appreciate any help.

Answer 1

A different solution would be to select n+m biggest elements from the table and then go through all of their pairs to select the best one. While going through the pairs, since they are sorted, we only need to find one pair and that will be the maximal element.

If you think about it: the solution has to be one of the "maximal" pairs. By selecting the n+m biggest elements you ensure that they can't be arranged onto the same row and column (pigeon hole principle). Now, given the first rook, the second must be the next biggest rook which doesn't share the row and the column with the first one.

The time complexity is O(n m + n m ln(n m) + (n+m)^2 - (n+m)) = O(n m ln(n m))): flatten data, sort, run through pairs. The additional log complexity that we obtained here can be relaxed by actually selecting the n+m biggest elements instead of running the full sort. EDIT: using min-heap it can be brought down to O(n m ln(max(n, m))), so unfortunately the algorithm is not optimal.

Code in C++:

const int N = 500;

int solution (vectors vector<int> > &A) {
    int n = A.size();
    int m = A[0].size();

    int s = n + m;
    tuple<int, int, int> flat[N * N];
    for (int i = 0; i < n; ++i){
        for (int j=0; j<m; ++j){
            flat[i*m + j] = {A[i][j], i, j};
        }
    }
    
    sort(begin(flat), begin(flat) + n*m, 
        [] (const auto& a, const auto&b) {return get<0>(a) > get<0>(b);});


    int best = 0;
    for (int i=0; i<s; ++i){
        auto rook1 = flat[i];
        int j = i+1;
        while (j < s && (get<1>(rook1) == get<1>(flat[j]) 
                        || get<2>(rook1) == get<2>(flat[j]))){
            ++j;
        }
        if (j < s){
            best = max(best, get<0>(rook1) + get<0>(flat[j]));
        }
    }

    return best;
}

solution({{2, 4}, {8, 5}});

Answer 2

I started with the algorithm suggested by Andreas and tweaked it a bit for minor improvements as explained in my comment below Andreas answer. Here is the code that I came up with. I have tested it for accuracy but not performance.

public static int solution(int[][] A) {

    int[][] rTop2 = new int[A.length][2];

    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < A[i].length; j++) {
            if (A[i][j] >= A[i][rTop2[i][1]] || rTop2[i][1]==rTop2[i][0]) {
                rTop2[i][1] = j;

                if (A[i][rTop2[i][1]] > A[i][rTop2[i][0]]) {

                    rTop2[i][0] += rTop2[i][1];
                    rTop2[i][1] = rTop2[i][0] - rTop2[i][1];
                    rTop2[i][0] = rTop2[i][0] - rTop2[i][1];
                }
            }
        }
    }

    int maxSum = 0;
    for (int i=0; i < rTop2.length; i++) {
        for (int s=0; s < 2; s++) {

            for (int j=i+1; j < rTop2.length; j++) {

                if (rTop2[j][0] == rTop2[i][s]) {
                    maxSum = Math.max(maxSum, (A[i][rTop2[i][s]] + A[j][rTop2[j][1]]));
                } else {
                    maxSum = Math.max(maxSum, (A[i][rTop2[i][s]] + A[j][rTop2[j][0]]));
                }
            }
        }
    }
    return maxSum;
}

Answer 3

I attempted this in JavaScript. While it may not be the most efficient approach, I'm open to any suggestions for enhancing performance. Your insights are greatly welcomed.

function solution(A) {
    let max = 0;
    let a = {};
    let b = [];

    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < A[i].length; j++) {
            a['' + i + j] = A[i][j];
            b.push([i, j]);
        }
    }

    for (let i = 0; i < b.length; i++) {
        for (let j = i + 1; j < b.length; j++) {
            let sum = a[b[i].join('')] + a[b[j].join('')];
            if (b[i][0] !== b[j][0] && b[i][1] !== b[j][1] && max < sum) {
                max = sum;
            }
        }
    }

    return max;
}

console.log(solution([[2, 4], [8, 5]]))

Answer 4

based on @Andreas comment above here is the code :

int solution(vector<vector<int>>& board) {
    int n = board.size();
    int m = board[0].size();

    vector<vector<int>> row(n);
    vector<vector<int>> col(m);

    for (int i = 0 ; i < n ; i++) {
        int mx = 0  , mxc  , smx = 0  , smxc;
        for (int j = 0 ; j < m ; j++) {
            if (board[i][j] >= mx) {
                smx = mx ;
                smxc = mxc;

                mx = board[i][j];
                mxc = j;
            }
            else if (board[i][j] >= smx){
                smx = board[i][j];
                smxc = j;
            }
        }
        row[i].push_back(mxc);
        row[i].push_back(smxc);
    }
    for (int j = 0 ; j < m ; j++) {
        int mx = 0 , mxr  , smx = 0  , smxr ;
        for (int i = 0 ; i < n ; i++) {
            if (board[i][j] >= mx) {
                smx = mx ;
                smxr = mxr;

                mx = board[i][j];
                mxr = i;
            }
            else if (board[i][j] >= smx) {
                smx = board[i][j];
                smxr = i;
            }
        }
        col[j].push_back(mxr);
        col[j].push_back(smxr);
    }
    int ans = 0 ;
    for (int i = 0 ; i < n ; i++) {
        int r = i  , c =  row[i][0];
        for (int  j = 0 ; j < m ; j++) {
            if (j != c) {
                if (col[j][0] != r)
                    ans =  max(ans , board[r][c] + board[col[j][0]][j]);
                else
                    ans =  max(ans , board[r][c] + board[col[j][1]][j]);
            }
        }
    }
    for (int j = 0 ; j < m ; j++) {
        int c = j  , r = col[j][0];
        for (int i = 0 ; i < n ; i++) {
            if (i != r) {
                if (row[i][0] != c)
                    ans = max(ans , board[r][c] + board[i][row[i][0]]);
                else
                    ans = max(ans , board[r][c] + board[i][row[i][1]]);
            }
        }
    }
    return ans ;
}

Answer 5

1. For each row, find the top 2 values and remember the column where they were found. O(mn)

2. For each column, find the top 2 values and remember the row where they were found. O(mn)

3. The the remaining operations, we only use the two lists built above. We will not look at the matrix again:

   1. For each row, pretend to place a rook in that row and in the column with the highest value. For each column, sum that top value with the top value for the column, except for the column where the rook is, where we sum with the second highest value. Remember the row of the pretend rook and the column with the highest sum. O(mn)

   2. Repeat, but use the second highest value. O(mn)

Operation complete. O(mn) + O(mn) + O(mn) + O(mn) = O(mn)