A rectangular display board has R rows and C columns of bulb sockets, each either holding a lit bulb or left empty. To minimize the amount of trim needed, the technician wants to build the smallest possible axis-aligned rectangular frame — with sides running along full rows and full columns of the board — that completely encloses every lit bulb. Given the state of every socket on the board, compute the area, in socket cells, of the smallest such frame. It is guaranteed that at least one bulb on the board is lit.
Example 1
Input
4 5 00000 01010 00100 00000
Expected
6
Explanation
The lit bulbs sit at rows 1 and 2 (0-indexed) and columns 1 through 3, so the smallest enclosing rectangle spans rows 1-2 and columns 1-3, an area of 2 rows * 3 columns = 6.
Example 2
Input
3 3 000 010 000
Expected
1
Explanation
Only one bulb is lit, at row 1, column 1, so the smallest enclosing rectangle is the single cell itself, giving an area of 1*1=1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →