Given a $n \times m$ grid $G$, with each grid square having a value 0 or 1, find a rectangle $R$ in $G$ that maximizes $R_1 - R_0$, where $R_0,R_1$ are defined as follows:

$R_0$ = the total number of 0's in $R$
$R_1$ = the total number of 1's in $R$

The brute force solution is to compute the value $(R_1 - R_0)$ for all possible rectangles, then select the one with maximum value. There can be $1/4 \lbrace nm(n+1)(m+1) \rbrace$ possible rectangles in a $n \times m$ grid. [Source]

Is there a smarter way to do this? Can we relate this problem to the Maximal Rectangle Problem?

This problem turns out to be similar to this one. We just have to replace 0s with -1s, then find the rectangle with largest sum. Using the techniques shown there, the problem can be solved in $O(nm \cdot \min(n,m))$ time. Can we do better?

  • $\begingroup$ You can, say, compute the sum in a rectangle by appropriately combining rectangles with one vertex at the origin, and compute the sum for them systematically. That cuts down the work, but it is still $\Omega(m n)$ precomputation. $\endgroup$ – vonbrand Sep 28 '15 at 1:22
  • $\begingroup$ Note that maximum and maximal are different notions. Maximal is a locally optimal solution, while maximum is a globally optimal one. The article you linked to seems to be using the wrong terminology. $\endgroup$ – Tom van der Zanden Sep 28 '15 at 5:45
  • $\begingroup$ This probably doesn't help in general, but you can improve the best case by predicting the maximum sum you can get (it would be the number of cells not seen so far plus the sum calculated so far). Also you could use the sum of the entire matrix as a predictor for the algorithm to choose: i.e. you could predict whether there are more zeros or more ones, and thus assume that larger rectangle is likely the solution or the smaller one. $\endgroup$ – wvxvw Sep 28 '15 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.