Room for a caption
A caption has to be placed on a photograph so that it does not cover fine details. The pixels are marked: 1 is calm (the brightness around hardly changes), 0 is not. Find the rectangle of the largest area with sides along the edges of the picture whose pixels are all ones.
Tests two to five are four photographs by the site’s author, shrunk to 300 pixels wide. On “Water and mountains” the best place is a strip of sky above the mountains, 217 × 36 pixels.
Input
The first line holds the height h and width w (1 ≤ h, w ≤ 600), then h lines of w characters 0 and 1.
Output
The largest area of a rectangle of ones (0 if there are no ones).
Examples
Example 1
4 5 10100 10111 11111 10010
6
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Fix the bottom row of the rectangle. Above each of its pixels is a column of ones of some height. What does the problem then look like?
2The idea
For each row compute the heights: how many consecutive ones there are above each pixel, counting itself. The heights are recomputed from the previous row in O(w). A rectangle with its bottom side on this row is a rectangle under the histogram of these heights, and the largest such is found by a monotonic stack.
3Walkthrough
The stack holds bars whose heights increase from bottom to top, and for each, where it started on the left. A new bar lower than the top means the bars higher than it will not continue further right: pop them, compute the area “height × width from the start to the current position”, and the new bar inherits the start of the last bar popped. At the end of the row put a bar of zero height to pop everything.
Each bar is pushed and popped once, so a row is processed in O(w), and the whole picture in O(h·w).
3+Solution
4Complexity
O(h·w) time and O(w) memory.
5Common mistakes
- Extending each bar left and right. Correct, but on a smooth sky the bars are equal, and each spreads over the whole row: the sixth test of nothing but ones is 600 rows of 600·600 steps.
- Forgetting the zero-height bar at the end. Then rectangles that reach the right edge are not counted.
- Recomputing heights from scratch. The height above a pixel is the height above it in the previous row plus one if the pixel is a one, and zero otherwise.