Find the Largest All-One Square in a Binary Matrix

Quick Overview

Find the largest all-one square in a binary matrix using dynamic programming, with a correctness argument, boundary handling, and linear-space code.

Find the Largest All-One Square in a Binary Matrix

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a rectangular matrix containing `0` and `1`, return the area of its largest square consisting entirely of ones. An empty matrix or a matrix with no ones has answer zero. ### Clarifying Questions to Ask - Is the desired result the square's area or its side length? - Are entries integers or character digits, and is the matrix guaranteed rectangular? ```hint Anchor one corner Describe the largest all-one square whose bottom-right corner is a particular cell. ``` ### What a Strong Answer Covers - A state measuring side length and a recurrence that checks all three adjacent directions. - Correct handling of zero cells and matrix boundaries. - Conversion from maximum side length to area and linear-space optimization. ### Follow-up Questions - How would you also return one square's coordinates? - Why is taking the maximum of neighboring square sizes incorrect?

Overview: Find the largest all-one square in a binary matrix using dynamic programming, with a correctness argument, boundary handling, and linear-space code.

Read the full Amazon Software Engineer interview experience this question came from

Amazon logo
Amazon
Nov 18, 2026
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Given a rectangular matrix containing 0 and 1, return the area of its largest square consisting entirely of ones. An empty matrix or a matrix with no ones has answer zero.

Clarifying Questions to Ask Guidance

  • Is the desired result the square's area or its side length?
  • Are entries integers or character digits, and is the matrix guaranteed rectangular?

What a Strong Answer Covers Guidance

  • A state measuring side length and a recurrence that checks all three adjacent directions.
  • Correct handling of zero cells and matrix boundaries.
  • Conversion from maximum side length to area and linear-space optimization.

Follow-up Questions Guidance

  • How would you also return one square's coordinates?
  • Why is taking the maximum of neighboring square sizes incorrect?