Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

184. Maximal Square

MediumDay 54 of 60Dynamic Programming

You are given an m x n grid matrix filled with the characters "0" and "1". Find the largest square that contains only "1" cells and return its area.

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
There is a 2 x 2 square of ones in rows 1 to 2, columns 2 to 3 (and 3 to 4).
Example 2
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Constraints
  • 1 <= m, n <= 300
  • matrix[i][j] is "0" or "1"
Hints
Frequently asked at: Amazon, Google, Apple, Microsoft
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min