Skills101
← All coding problems

Largest Rectangle of 1s

hardMatrix+40 XPTime limit 2s

The grid contains only 0s and 1s. Find the area of the largest rectangle (sides parallel to the grid) that contains only 1s.

Input:

  • line 1: r c
  • next r lines: c values, each 0 or 1

Output: the largest area (0 if the grid has no 1).

Constraints: 1 ≤ r, c ≤ 400.

Think about it: process the grid row by row. For each column keep the height of the run of 1s ending at the current row — together these heights form a histogram. The answer is the largest rectangle in any of these r histograms, which a monotonic stack finds in O(c) per row, O(r·c) in total.

Sample input 1

4 5
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Sample output 1

6

Sample input 2

1 1
0

Sample output 2

0

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.