‹ DS&A interview · Socratic
DSA · Dynamic Programming · #111

Maximal Square

Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke

Given an `m x n` binary `matrix` filled with the characters `'0'` and `'1'`, implement `maximalSquare(matrix)` that returns the **area** of the largest square containing only `'1'`s. The entry point is the function `maximalSquare`, which takes a 2D array of single-character strings and returns an integer (the side length squared).

Examples
  • matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] → 4 — The largest all-'1' square has side length 2, so the area is 4.
  • matrix = [["0","1"],["1","0"]] → 1 — No 2x2 square of '1's exists; a single '1' gives area 1.
  • matrix = [["0"]] → 0 — No '1' present.
Constraints
  • · m == matrix.length
  • · n == matrix[i].length
  • · 1 <= m, n <= 300
  • · matrix[i][j] is '0' or '1'.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.