Largest Solid Square

Medium

You are given a rectangular grid grid with m rows and n columns; each cell is the string '1' or '0'. Find the largest square, aligned with the grid lines, whose cells are all '1', and return its area (the number of cells). If there are no ones, the answer is 0.

Example 1

grid=[['1', '1', '1', '0'], ['1', '1', '1', '1'], ['1', '1', '1', '1'], ['0', '1', '1', '0']] → 9

The top-left 3 × 3 square is all ones, area 9. There is no all-ones 4 × 4 square.

Example 2

grid=[['0', '1', '0'], ['1', '0', '1']] → 1

The ones stand alone, so the best square is 1 × 1.

Example 3

grid=[['0', '0']] → 0

Constraints

1 ≤ m, n ≤ 300
All rows have the same number of cells
Each cell is '0' or '1'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix

Similar problems

Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium Best Spot for the Turret Medium Steps to the Nearest Zero Medium Longest Lit Line Medium

Input

grid=[['1', '1', '1', '0'], ['1', '1', '1', '1'], ['1', '1', '1', '1'], ['0', '1', '1', '0']]

Expected

Run checks the first 3 tests in your browser. Submit checks all 71 tests on the server, hidden ones included.