Based on my shorter Ruby version. Still using ruichang's idea to use binary search.
def minArea(self, image, x, y): def first(lo, hi, check): while lo < hi: mid = (lo + hi) / 2 if check(mid): hi = mid else: lo = mid + 1 return lo top = first(0, x, lambda x: '1' in image[x]) bottom = first(x, len(image), lambda x: '1' not in image[x]) left = first(0, y, lambda y: any(row[y] == '1' for row in image)) right = first(y, len(image), lambda y: all(row[y] == '0' for row in image)) return (bottom - top) * (right - left)
first function could also use the
bisect module, for example:
def first(lo, hi, check): self.__getitem__ = check return bisect.bisect(self, False, lo, hi) def first(lo, hi, check): class Checker: __getitem__ = staticmethod(check) return bisect.bisect(Checker(), False, lo, hi)
The first one is a bit dirtier, and requires
class Solution: instead of
bottom = first(x, len(image), lambda x: '1' not in image[x]) can be changed to
bottom = first(x + 1, len(image), lambda x: '1' not in image[x])
I know, but that makes the code longer :-P. Especially annoying if I did it for y, then it would be too wide for Firefox which would start showing a scroll bar...
@AspirinSJL: check this out. You will find it interesting. Note that Stefan's code is very clear and (very often) does not need comments (as Bob Martin once said, writing a comment is a failure for a programmer). I believe that less is more, when you know what you're doing.
@agave Well, like I said for my Ruby version and now also here, the basic idea was ruichang's. But yeah, I'm happy with the implementation. Though I just added some shorter but more or less dirty variations.
@StefanPochmann: right, I was about to ask you why you didn't use
bisect.bisect_left() in some way...
@agave Perhaps I didn't yet know that I can "abuse" the bisect module like that. I mean, its documentation only mentions "lists" and "arrays". And I think I've only ever seen one other person do that (and it was later). So it doesn't seem mainstream.
@StefanPochmann: right. I didn't think it was possible, honestly... That's why I thought "I am sure he thought about using
bisect but maybe it's not customizable for any
check function..." But you never stop learning...
@StefanPochmann I have a very basic question and it would be really helpful if you can clarify. In all the solutions given why are we searching for the first column with ones on left side and first column with zeros on the right side? Similarly for top and bottom cases.
I tried implementing this and with searching for first and last columns with ones on either side and the binary search on the right side ended in an infinite loop. It got stuck at i=2 and j=3 (for the sample input provided).
This is the code I tried. http://pastebin.com/L2WzD5Fx
It would be really helpful if you can clarify.
@StefanPochmann I just want to consult if you have any tricks/ways to write a correct binary search (such as the one in this post)? I always struggle about the corner cases and I will always need to twist for a few times before reach to the correct solution. Thanks in advance!
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.