FastPrep
Problem · Matrix

Largest Two Non-Overlapping Buildable Squares

Learn this problem
● HardAmerican Express logoAmerican ExpressINTERNOA

Problem statement

A rectangular map is represented by a binary matrix grid. A cell containing 1 is buildable, and a cell containing 0 is not.

Place two axis-aligned square regions such that:

  • Both squares have the same positive side length.
  • Every cell in both squares contains 1.
  • The squares share no cell. Touching along an edge or corner is allowed.

Return the maximum common side length. Return 0 if no valid pair exists.

Function

largestTwoSquares(grid: int[][]) → int

Examples

Example 1

grid = [[1,1,0,1,1],[1,1,0,1,1]]return = 2

The left and right 2 x 2 all-one blocks are disjoint.

Example 2

grid = [[1,1],[1,1]]return = 1

Any two different buildable cells form two disjoint squares of side 1, but two side-2 squares cannot fit.

Example 3

grid = [[1]]return = 0

Only one buildable square exists, so no pair can be placed.

Constraints

  • 1 <= grid.length <= 700
  • 1 <= grid[i].length <= 700
  • Every row has the same length.
  • grid[i][j] is either 0 or 1.

More American Express problems

drafts saved locally
public int largestTwoSquares(int[][] grid) {
    // Write your solution here.
}
grid[[1,1,0,1,1],[1,1,0,1,1]]
expected2
checking account