2

Possible Duplicate:
Find largest rectangle containing only zeros in an N×N binary matrix

Here is a n*m matrix filled up with 0s and 1s. I need to find the biggest rectangular made of 1s. The biggest rectangular made of 0s is equivalent as I can use 0 instead of 1. So in this example, 8x8 matrix: The biggest rectangular is the submatrix starting at (2,0) and diagonally ending at (7,1) having 12 1s.

10011110
10011110
11100010
11100010
11100000
11001111
11000000
11000000

This is not a HOMEWORK. This is one of my preparation questions for an interview.

I came up with the following solution. Start at (0,0) and for each element, try to go diagonally if possible, thereby check the other elements forming that particular rectangle in both directions (say the diagonal end is 2,2 I would check 2,1 and 1,2 for 1s), otherwise go left or right depending on the 1s that exist. If rectangular is expanded, mark the cell with the current number of 1s included in the rectangular.

How would you approach? What do you think of my solution?

Community
  • 1
  • 1
Bob
  • 991
  • 8
  • 23
  • 40
  • pretend the matrix is a B&W image, use blob area algorithms to produce the largest one :D – im so confused Sep 26 '12 at 18:12
  • 1
    There is a good explanation at [Dr Dobbs](http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529) of an O(nm) algorithm to solve this. – Peter de Rivaz Sep 26 '12 at 18:14
  • @AK4749 Seriously though, It seems like a non-trivial algorithm. Is there any well-known solution to this problem? Like a proven-one that outperforms other solutions? – Bob Sep 26 '12 at 18:14
  • @AmitD that says only N*N. In this case, it is a fully variable sized matrix. – Bob Sep 26 '12 at 18:16
  • @Bob fully variable meaning just N*M. The algorithm still holds as it works via solving a reduced problem per row. As such, it is column-independent (with some code modifications of course). – im so confused Sep 26 '12 at 18:23
  • Although @PeterdeRivaz has an EXCELLENT link. I'd go with that – im so confused Sep 26 '12 at 18:26
  • @PeterdeRivaz Just read through the document you posted, is there any explanation for the same algorithm in Java? Python is no use for me especially when understanding an algorithm. – Bob Sep 26 '12 at 18:39
  • @AK4749 is the optimal solution for space and time complexity both O(n*m)? – Bob Sep 26 '12 at 18:42
  • @Bob In terms of time complexity, it HAS to be O(m x n) in order to access every element of the original matrix, correct? I believe the link he posted uses an O(m) space algorithm though – im so confused Sep 26 '12 at 18:47
  • @Bob also I believe it's pseudocode, meaning it can be implemented in any language. Doesn't look like any python i've encountered – im so confused Sep 26 '12 at 18:51
  • 1
    @Bob: the code in Dr Dobbs is not Python. Compare it with [my answer which is in Python](http://stackoverflow.com/a/4671342/4279). Though it doesn't use anything that can't be easily translated to Java. It is a single pass algorithm it looks at one row at a time. Despite the title of the question it works for n*m case without any changes (it should even work for non-constant row sizes (imagine left-aligned text with lines of different length)). There is a link with detailed description of several algorithms in plain English. You can ask if something is unclear. – jfs Sep 26 '12 at 22:38

0 Answers0