Interview Question Software Engineer / Developers
Yes O(n^2) is possible.
The T and B above.
Preprocess the B to be able to give range max queries in O(1) time (this is possible in O(d)).
Now given T[i]. In the range [i, T[i]] find max of B.
Say B[j1] If B[j1] >= -i, now find max of B in [j1, T[i]]. Say B[j2]. If B[j2] >= -i, continue till you get j.
So once you find the pair (i,j), you can ignore the array B[1...j] as the maximum square for a subsequent i cannot be paired with the current j we found.
Thus we only consider O(n) elements of B and thus this is O(n^2) total.
The above solution, the tree approach is not clear, but does look do-able using 2D range searching algorithms: basically treat B as the 2D points (j, B[j]), now you are looking to find the rightmost point in the region i <= x <= T[i] and y >= -i.
A tough question for an interview.
I am not sure how this is possible
"We preprocess in O(n^2) time, filling each entry with max possible lengths of the top-left and bottom right square."
If the matrix is nxn. Just visiting all elements is n^2. Now if you want to find the max TL it will be another N. So isn't the preprocessing phase already O(n^3)
At each entry you find the longest possible sequence of 1s which go up, right, down and left. This can be done in O(n^2) by considering each direction and making 4 passes over the whole matrix.
The max for top-left of an entry will be min(right, bottom).
It's hard for me to get how it's O(n^2) indeed. Preprocessing longest run of 1's in either of 4 direction can be done in O(n^2) - I know.
But, let's index (i,j) is the left-upper point of the resultant submatrix with boarders all 1s. And let's L is the max length on horizontal and H is the max length on vertical axis. Now starting index (i,j), the right-lower point could be anything in this range [(i+1),(i+2),...(i+L-1)],[(j+1),(j+2),...(j+H-1)]. How could you check in O(1) which range on x and y axis gives largest submatrix range,i.e. if the solution is (i+X),(j+Y), how could you find this X (in range of 1...L-1) and Y (in range of 1...H-1) such that boarders are all 1s and X*Y is largest. I'd appreciate if you work with the given example to clarify your thoughts on the issue I'm asking, i.e. O(1) time for each of n^2 left-upper points.
The T and B are arrays along a specific _diagonal_. There are 2n-1 diagonal(in nxn case). Using Range Maximum Preprocessing on B makes it O(d) for each diagonal,where d is the length of the diagonal. Hence total it is O(n^2).
Thanks. But, still few confusions!
1. Isn't ur approach would find max-subsqure matrix then rather than max-subrectangle? How do you find it here ?
1 0 1 1 1
0 1 1 1 1
0 1 0 1 1
1 1 1 1 1
2. Do u mean 2n-1 is the length of diagonal in n x n given matrix? Or, do u mean possible starting-ending point for the diagonals?
The question asks for max sub-square, not rectangle.
No, 2n-1 the _number_ of diagonal_s_. One big diagonal of size n, 2 of size n-1 just next to it and so on...
I think you are wrong to interpret the question. Read again pls. It asks for max submatrix (matrix never means 2 dimension is equal). Look at the example in OP
0 1 0 1 0 1 1 1
0 1 1 1 1 1 1 0
1 1 0 1 1 0 1 1
0 1 0 0 1 0 1 0
0 1 1 1 1 1 1 1
so the submatrix from (1,1)to (4,6) is the answer
=> Look carefully, solution is a 4 by 5 submatrix.
Secondly, I doubt if you are right here. How could 2n-1 be # of diagonals? It should be 1 + 2 + 3 + ... n = O(n^2).
Sorry, it was a typo...
solution is 4 by 6 submatrix.
So, overall I can't accept your solution to be O(n^2) for the specific problem!
Reading again and repeating here for your benefit: "given matrix will bee square matrix and we have find square submatrix as well"
There are 2n-1 diagonals, going from top left to bottom (or diagonals of slope -1, if you will). Any square submatrix's top left corner will be on one of those diagonals, and the bottom right corner would be on the same diagonal as the top left corner.
You are free not to accept anything without proper proof, which is a good trait, if, you are willing to put some effort yourself first.
Similarly I am free not to care whether you accept it or not :-)
I think it works. For an interview an O(n^3) solution will be acceptable, IMO.
btw, we are counting # of diagonal, not the number of squares on each diagonal.
For each diagonal of length d, the B and T give an O(d) algorithm. Adding up as you did, give an O(n^2) algorithm.
I can't understand why people like to put additional constrain to a problem. As supersonglj pointed O(n^3) is doable like max-subrectangle problem. Interviewer didn't ask to do in O(n^2), right? Then why need to make it complex?
I found for square submatrix, one posted diagonal-based searching that is with optimum O(n^2) complexity for this problem.
However, I'm wondering how O(n^3) solution could be derived for finding rectangular submatrix with max area for the above problem. My approach is O(n^4) which seems too slow. Any idea?
O(n^2 log n) is possible I think.
- Anonymous August 30, 2011For each entry, we consider if it can be the top-left or bottom-right corner of a square.
We preprocess in O(n^2) time, filling each entry with max possible lengths of the top-left and bottom right square.
Now we go over each diagonal and try to find a top-left/bottom-right pair.
Say for a diagonal, we have the arrays
TL[1,..., d] and BR[1,...d]
We can form a square with i and j (note this is along the diagonal) if
TL[i] >= j-i+1
and
BR[j] >= j-i+1.
This can be rewritten as
TL[i]+i-1 >= j and BR[j] -j -1 >= -i
Form new array T[i] = TL[i] + i - 1, B[j] = BR[j] - j - 1.
Now for each i, you need to find the right most j in [i, T[i]] such that B{j] >= -i. This can be done in O(nlog n) time total if we use balanced trees.
Thus we get an O(n^2 log n) algorithm.
O(n^2) seems possible, perhaps using some kind of range minimum query structures.