Skills101
← All coding problems

Largest Square of 1s

mediumMatrix+20 XPTime limit 2s

A plot of land is drawn as a grid: 1 is a usable square metre, 0 is a rock. You want to build a square house on usable land only. Find the area of the largest all-1 square in the grid.

Input:

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

Output: the area of the largest square containing only 1s (0 if there is no 1).

Constraints: 1 ≤ r, c ≤ 500.

Think about it: let dp[i][j] be the side of the largest all-1 square whose bottom-right corner is (i, j). If the cell is 1, dp[i][j] = 1 + min(top, left, top-left) — the square can only grow as far as all three neighbours allow.

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

4

Sample input 2

2 2
0 1
1 0

Sample output 2

1

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.