1
$\begingroup$

I've recently come across a following problem. In a rectangular array of ones and zeros one has to find maximum non-degenerate rectangle whose sides are filled with ones. By "maximum" i mean any rectangle with maximum possible perimeter. By "non-degenerate" i mean that all sides consist of at least two cells. We do not care about the points inside the rectangle. The only requirement is that its sides consist of cells filled with ones.

I know how to solve a similar problem where one needs to find maximum rectangle totally filled with ones (i.e. not only its border, but its interior too). But with this problem i got stuck so any ideas will be highly appreciated. I believe that there is some smart $O(max(m,n)^3)$ solution but can't see it yet.

Thanks in advance.

P.S. This is not a problem from an ongoing competition, hometask problem or an interview question. The problem originates from KPI-OPEN 2017 competition. You can find original statement here (problem F): http://kpi-open.kpi.ua/problemset/kpi_open_2017_2/eng.pdf

According to bounds on rectangle's size and time limitations there has to be at most cubic (or perhaps cubic-logarithmic) solution. As far as i know there were cubic solutions during the contest.

P.P.S. There is an algorithm which precomputes for each cell how many cells there are to the left and above it which are filled with ones. Using such precomputation we can easily solve the problem in $O(max(m,n)^4)$ considering all possible rectangles. We just iterate through all possible cells for upper left corner of rectangle and through all possible cells for lower right corner. With the precomputation we might check in $O(1)$ that our rectangle is appropriate and if it is we just update the answer. Unfortunately such approach is to slow.

Improve this question
$\endgroup$
9
  • $\begingroup$ @Evil I've read once a chapter on DP in CLRS but i don't remember such problem being explained there. If it is a "quite well known problem" then it should have some well known name like "Knapsack problem" or "Subset sum problem" etc. $\endgroup$ Commented Jul 16, 2017 at 17:42
  • $\begingroup$ I know it as "maximal rectangle problem", eg. at dr dobbs or at SO. It may require a bit tunning, but even naive approach conversion between these problem is possible in $\mathcal O(mn)$. It also solves your initial problem in "quadratic" (rectanglish?) time. The special case for degenerate rectangle is not needed, if the maximal answer is degenerate case simply return "not found". $\endgroup$ Commented Jul 16, 2017 at 17:49
  • $\begingroup$ Nice exercise. Where did you encounter this? Can you credit the source for where you saw this problem? Where did you get $O(\max(m,n)^3)$ from? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ Commented Jul 16, 2017 at 18:18
  • $\begingroup$ @Evil, this is not the same as the "maximal rectangle problem". The maximal rectangle problem requires the entire rectangle to be filled with ones. This question is about the case where only the sides have to be ones, but the interior can be anything. $\endgroup$ Commented Jul 16, 2017 at 18:20
  • $\begingroup$ I think we've had this question before? $\endgroup$ Commented Jul 16, 2017 at 19:09

1 Answer 1

Reset to default
1
$\begingroup$

Yes, it is solvable in $O(\max(m,n)^3)$ time. In fact, it should be solvable in $O(\min(m,n)^2 \max(m,n))$ time -- e.g., if $m<n$, it should be solvable in $O(m^2 n)$ time.

Let $N_\text{down}(i,j)$ denote the number of cells that you can go down, starting from $(i,j)$, without encountering a zero. Similarly, let $N_\text{right}(i,j)$ denote the number you can go right. You can precompute all of these values in $O(mn)$ time. Do you see how?

Now, I'm going to give you some hints, to help you solve this on your own. Hint #1:

Suppose I told you that the left side of the rectangle is at column $j_0$ and the right side is at column $j_1$. Could you find the top and bottom sides of the rectangle with maximum perimeter? How efficiently could you find it?

Hint #2:

Continuing from Hint #1 -- can you identify some necessary and sufficient conditions to recognize the upper-left corner of the rectangle, $(i_0,j_0)$? What would have to be true about the $N_\text{down}$ and $N_\text{right}$ values? Similarly for the lower-left corner.

Hint #3:

Try a linear scan downwards in those two columns. In fact, all you need are the $N_\text{right}$ values.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.