Katkat
Back

Largest Square of Ones

AirwallexSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Tests dynamic programming on a 2D grid, specifically optimizing state transitions to achieve O(n) auxiliary space.

Largest Square of Ones

Given an m x n binary matrix filled with '0's and '1's, find the largest square containing only '1's and return its area.

Your solution should run in O(m * n) time and use at most O(n) extra space (where n is the number of columns).

Function Signature

def maximal_square(matrix: list[list[str]]) -> int:
    pass

Input

  • matrix: A list of lists of strings, where each element is either '0' or '1'.

Output

  • Returns an integer representing the maximum area of a square composed entirely of '1's.

Constraints

  • 1 <= m, n <= 300
  • matrix[i][j] is either '0' or '1'.

Examples

Example 1:

Input: matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 4
Explanation: The largest square of all '1's has side length 2 (found in rows 1-2, cols 2-3 or cols 3-4), so the area is 2 * 2 = 4.

Example 2:

Input: matrix = [
  ["0","1"],
  ["1","0"]
]
Output: 1
Explanation: The maximum square side length is 1, so the area is 1.

Example 3:

Input: matrix = [["0"]]
Output: 0
Explanation: There are no '1's in the matrix.

Edge Cases

  • A matrix consisting entirely of '0's should return 0.
  • A matrix consisting of a single row or column.
  • The entire matrix being filled with '1's.

Hints

Hint 1

Consider defining dp[i][j] as the side length of the largest square whose bottom-right corner is at (i, j).

Hint 2

Notice that dp[i][j] depends only on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1].

Hint 3

To achieve O(n) space, maintain a single 1D array representing the current row and use a temporary variable to hold the top-left diagonal value from the previous row.

Follow-up questions

  • How would you solve the problem if you needed to find the area of the largest rectangle of all ones instead of a square?
  • If the input matrix was extremely wide (m >> n) or extremely tall (n >> m), how would you structure your space optimization?
  • How could this algorithm be adapted to return the row and column coordinates of the optimal square rather than just its area?