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.

Swot

Answer 1

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)

Geosyncline

I implemented this algo, thanks for the idea. I found a couple of minor improvements in it - (1) Did not implement Step 2 (Finding Top 2 values for each column). I think thats redundant. (2) For each row, pretend to place a rook in that row and in the column with the highest value. Then, For each HIGHER ROW, sum that top value with the top value for the row, if the COLUMN for that cell is != the COLUMN for the set Pretend ROOK, ELSE, use the SECOND value from that ROW. Remember the row of the pretend rook and the column with the highest sum. – Hovis

Answer 2

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 ;
}

Dodgem

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]]))

Evolutionist

Answer 4

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;
}

Hovis