Practice/Expedia/Leetcode 221. Maximal Square

Leetcode 221. Maximal Square

CodingMust

Problem

You are given a 2D binary matrix where each cell contains either the character '0' or '1'. Your task is to find the largest square submatrix that contains only '1's and return its area.

A square submatrix must be axis-aligned (not rotated) and all cells within it must contain '1'. If no such square exists, return 0.

Requirements

1. The input matrix consists only of characters '0' and '1'
2. Return the area (not the side length) of the largest square
3. The square must be contiguous and axis-aligned
4. Handle edge cases like empty matrices or matrices with no '1's

Constraints

• m == matrix.length (number of rows)
• n == matrix[i].length (number of columns)
• 1 <= m, n <= 300
• matrix[i][j] is either '0' or '1'
• Expected time complexity: O(m × n)
• Expected space complexity: O(m × n) or O(n) with optimization

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 has side length 2 (bottom-right area), giving an area of 2 × 2 = 4

Example 2:

Input: matrix = [['0','1'],['1','0']] Output: 1 Explanation: The largest squares are individual '1' cells with area 1

Example 3:

Input: matrix = [['0']] Output: 0 Explanation: No '1's exist, so no square can be formed