This was asked in 3rd round of ZS Associates interview process. You’re given square matrix of size NxN of 1s and 0s. From this find the largest square of 1s(ones). The catch is that the required square should NOT be filled with 1s, they just want it to be a square border.
Could you please be more clear or give a link to the problem(if there)
Sorry bro, it was asked in interview, the interviewer explained the problem, and asked me to write code on paper.
Ex.
input=>
1 0 1 1 0 0 0 0 0 0
0 1 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 1 1 1 0
0 1 1 1 1 1 0 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 1 1 0 1 1 1 1 0
0 0 0 0 0 0 0 0 0 0
output=>
4
Do You know Flood Fill algorithm and boundary fill algorithm , if no then try them maybe it will be helpful.
That’s what I suggested, to fill the square and then find the largest “filled” square in the matrix, but he didn’t accept that solution, idk why.
try this for every continuous ones in the matrix find if it makes a square and then if it does check if its the max we can form
Here is the easy solution,
1)First you create to prefix sum matrices.
2)Traverse the matrix.
3)You see, a(i)(j)…
4) You check if 2x2 matrix is possible in O(1) due to (1). You check all possible sizes in O(N).
5)Total Time Complexity:- O(N^3)…which is more closer to O(N^2) in real life.
1 Like
I have optimized it to n^2.log(n)…where the matrix is of size : - nxn , do binary search in 4th step, which will take log(N) time!
Think before you say…
Binary search is obviously wrong.
What you are saying without understanding is obviously wrong…I’ll write the code in few hours, then you can keep checking it with different tests. I am 100% sure of my solution.
Let me explain what binary search actually is: if f(x) is true then f(x+1)…f(x+n) is true. Binary search works for monotonic functions only, here you can see if you get a square border of size 3 it doesn’t guarantee that you’ll get one of size 2 also. Hope you understand
No…no…I am not doing that what you have written, I am doing something else, will explain soon.
2 Likes
Okay then it would be something new to me, I thought you’ll do this because of what you have written above, waiting for it. Maybe you can explain your binary search approach if you’re free
1 Like
I got what you’re trying to say, it’s correct 
1 Like
Here is my O(n^2) solution…
1)You see (1,1)…say…
2)Now, you find out the max(x) such that, we can make continuous 1’s of length ‘x’ in right and bottom. In O(1) or O(logn)
3)Say,x=5… So, (1,1) to (1,5) is secured…and (1,1) to (5,1) …is also secured…you agree with me???
4)Now, the possible candidates for the square are:- (2,2), (3,3),(4,4),(5,5)… You agree??
5)Now,I have pre-calculated all the slant lines to know which is good guy, which is bad gay.
6)Say, good guys:-(2,2),(4,4)… And (3,3) and (5,5) are bad guys…
7)In other 2-D array I have also stored the index where the last good guy came.
8)So value of (5,5) is actually (4,4)
…
Solved… Now, a question might arise…that I have to update all good guys and bad guys when I calculate for (2,2) and hence we fail.
Answer is No. I have a complex way to handle that too! Now, I am in a class. I’ll answer it later…
So here is the super complicated idea:- for each diagonal you store ‘x’ in it which means it can satisfy all squares which start at (y,y) where y<=x, now, all you gotta check is, for the given diagonal array, find the lowest index of person which is >=y, which can be done using some data-structure. Max complexity:- O(n^2.log(n)) O(n^3) solution is simple and I guess interviewer expected the same 
The best solution to this question on the internet:- https://www-geeksforgeeks-org.cdn.ampproject.org/v/s/www.geeksforgeeks.org/given-matrix-o-x-find-largest-subsquare-surrounded-x/amp/?usqp=mq331AQQKAFwAZgBkZm1jr3NndLTAQ%3D%3D&_js_v=a2&_gsa=1#referrer=https%3A%2F%2Fwww.google.com&share=https%3A%2F%2Fwww.geeksforgeeks.org%2Fgiven-matrix-o-x-find-largest-subsquare-surrounded-x%2F
Has O(N^3) complexity, which we already discussed. But, I found an over complicated O(n^2.log(n)). I d k if I should feel bad or good lol:grin:
So here is the complete solution:-
1)For each slant-line , create an array.
2)Each element of array has the value ‘v’ . ‘v’ means that it can satisfy any matrix whose top-left corner co-ordinate is greater than (v,v)…(assuming the diagonal matrix as of now…)
3)Now, we traverse that array… if we are at say (14,14)…and the best we can go is till (21,21)…we do a range query on (14,14) to (21,21) to find the index of an element whose value<=14 and has the greatest index.
4)How do we do that??:- We create a merge sort tree, each node has all elements in sorted order as well their indices…for <=x, we get a set of elements from index (0 to y), now, we need to find the lowest index of 0 to y guys…which we can do by maintaining a prefix maximum array.
5)Time Complexity of the solution:- O(n^2.logn.logn)
To learn about merge-sort-tree:–>https://www.commonlounge.com/discussion/fe6ac441785c44d6a959eab662f15adc