League Warm-Up Squares

Largest side length of an all-1 square in a binary matrix

Easy2-D Dynamic ProgrammingGrid DPRolling Array

A football league divides its training field into a rectangular grid of equal-sized plots. Each plot is marked 1 if it is available for warm-ups and 0 if it is closed.

A team needs a square warm-up zone made from consecutive rows and consecutive columns. Every plot inside the zone must be available, and the zone's edges must follow the grid lines.

Given the integer matrix available, return the largest possible side length in plots of a square warm-up zone. Return 0 if no plot is available.

Examples

Example 1

Input: available = [[1,1,0,1],[1,1,1,1],[0,1,1,0]]
Output: 2

The available plots in the first two rows and first two columns form a square zone. Every larger square includes at least one closed plot.

Example 2

Input: available = [[0,1,1,1,0]]
Output: 1

The field has only one row, so a warm-up zone cannot extend across multiple rows, even though several adjacent plots are available.

Example 3

Input: available = [[1,1,1],[1,1,1],[1,1,1]]
Output: 3

Every plot is available, so the entire field can serve as a square warm-up zone.

Constraints

  • 1 <= len(available) <= 120
  • 1 <= len(available[0]) <= 120
  • All rows have the same length.
  • Every entry in available is either 0 or 1.

The reference solutions run in O(rows * columns) time and use O(columns) extra space. The input matrix is not modified.

Hints

Show hint 1

Let a state describe the largest available square whose bottom-right corner is a particular plot.

Show hint 2

For an available plot, relate its state to the states immediately above, immediately left, and diagonally above-left.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • Can you use only O(number of columns) extra space?
  • How would you also return the top-left coordinates of a largest zone, breaking ties by smallest row and then smallest column?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem