You are given a grid of R rows and C columns where every cell is 0 or 1. Consider every axis-aligned square block of cells. Find the area (number of cells) of the largest such square whose cells are all 1. If the grid has no 1, the answer is 0.
Line 1: two integers R and C.
Next R lines: each has C space-separated values, every value 0 or 1.
A single integer: the area of the largest all-ones square.
Example 1
Input
4 5 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Expected
4
Explanation
The largest all-ones square has side 2 (for instance the block in rows 2-3, columns 3-4), so its area is 4.
Example 2
Input
2 2 0 0 0 0
Expected
0
Explanation
There are no ones anywhere, so the largest all-ones square has area 0.
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 →