Tricky problem ... solution needed
I was asked this qstn today morning by an interviewer. Cant figure out where to start... Sample input [ [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 0, 0, 1], [1, 0, 1, 0, 0, 0, 1], [1, 0, 1, 1, 1, 1, 1], [1, 0, 1, 0, 0, 1, 1], [1, 1, 1, 0, 0, 1, 1], [1, 1, 1, 1, 1, 1, 1], ] Sample output [ [2, 3, 3, 5], // top-left is (2, 3), bottom-right is (3, 5) [3, 1, 5, 1], [5, 3, 6, 4] ] // first zeros set top-left is (Y,X) -> (2, 3), bottom-right is (3, 5) For each zero starting and ending in the adjacent matrix co-ordinates... output matrix should have those co-ordinates. Any hint?
More clarification... look at output 2nd row .. (remember to start i from 0) Second set of 0s in input started from Y=3.. x=1. .. and ended at y=5.. x=1.. so output row is 3,1,5,1
Looks like interviewer clarifying his/her doubts.
So my code currently gives the co ordinates if there is only one zero's rectangle.. If i have multiple zeros rectangle. it gives first zero and last zero in the whole matrix.
General problem is Find Connected components. There seems to be either an input assumption or an output restriction on rectangular components. If you can assume input will have rectangular zero components, solution is trivial through a single pass. If output needs to be constrained, a DP solution to get maximal rectangle within each component will be O(nlogn), I think.
https://en.m.wikipedia.org/wiki/Connected_component_(graph_theory)
Try again
Here is the problem in leetcode: https://leetcode.com/problems/maximal-rectangle/description/
With a find all twist
@op, who asked this question ?
Yep clarification required. Op should have asked the interviewer but I guess he bombed it.
If we can assume all the zeroes form a square 1) Find left corner by scanning rows from left to right, top to bottom 2) Go down until you hit a 1. This is the row index of right corner. 3) Go right until you hit a 1. This is the right bottom column. As you perform the graph traversal when you first hit a zero, make each visited node in the matrix so you don’t revisit the node
Try again.
Why is it wrong? What case breaks it?
One way to approach this is to write a preprocessing pass that produces a list for each row. The list consists of intervals [a, b] where a and b are column numbers for maximum length runs of ones. Now you need to output intersection of contiguous lists or if none exists the earliest interval. Preprocessing is O(rows * cols) and for each pass you eliminate at least one column for examining O(rows) work. That is still O(rows * cols) is work overall so linear in the number of elements of the matrix.
Fuck these interviews. This shit isn't funny anymore