The question is like this..
There is an NxN chessboard. Each square on the chessboard can be either empty or can have a rook. A rook as we know can attack either horizontally or vertically. Given a 2D matrix where 0 represents an empty square and 1 represents a rook, we have to fill in all the cells in the matrix with 1 which represent squares that can be attacked by any rook present on the chessboard.
Now, I could do this easily in O(n^3) time and constant space complexity. And then in O(n^2) time and O(2*n) space complexity. But I need to figure out a solution in O(n^2) time and constant space. Somebody please help.
Assume that you knew that all your rooks were either in the first column or in the first row. Then you would have a O(n^2) solution with no space overhead by just traversing the first row/column and filling you matrix every time you see a rook (except for filling the first row / first column, that you treat in a last step). The same holds if all rooks are in the last column / last row, first column / last row, and last column / first row.
Now take your initial matrix and iterate over it until it contains a rook. Let i be the index of the row of this rook and j be the index of its column. Continue iterating over the matrix and for each rook that you find at position (i',j'), remove it replace it with a rook at position (i,j') and another rook at position (i',j).
The matrix you end up with will have ones only along the i-th row and the j-th column. Let A_1 be the submatrix of A formed by its i first rows and j first columns. Then A_1 has the property that it contains ones only on its last row / las column and thus you can solve for A_1 without space overhead. Do the same for the three other submatrices of A (the one with the n-i+1 last rows and j first colummns, and so on).
If this is not clear please tell me and I will give more details.