Is Maximal Square easy or hard?

Maximal Square is generally rated Medium difficulty. The challenge lies in recognizing the dynamic programming relationship between neighboring cells rather than checking all possible squares, which would be much slower.

How to solve Maximal Square in O(n) space?

Use a space-optimized dynamic programming approach that stores only one row of DP values. While scanning each row, keep track of the previous diagonal value before overwriting the current entry. This keeps the time complexity at O(m*n) but reduces memory usage to O(n).

What is the best approach for Maximal Square?

The optimal approach uses dynamic programming. For each cell in the matrix, compute the largest square ending at that position using the recurrence dp[i][j] = 1 + min(top, left, diagonal). This processes every cell once, giving O(m*n) time complexity and O(m*n) space, which can be optimized to O(n).

What data structure is used in Maximal Square?

The solution primarily uses a 2D or 1D dynamic programming array to store intermediate square sizes. The input itself is a matrix, and the DP array tracks the largest square ending at each position while iterating through the grid.

What is the time complexity of Maximal Square?

The standard dynamic programming solution runs in O(m*n) time, where m is the number of rows and n is the number of columns in the matrix. Each cell is processed exactly once and updated using constant-time comparisons with its neighbors.

Maximal Square Python or Java solution approach?

Both Python and Java implementations typically use the same DP recurrence: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) when the matrix cell is '1'. The algorithm runs in O(m*n) time and can be implemented with either a 2D DP table or a space-optimized 1D array.

Is Maximal Square asked at Google, Amazon, or Meta?

Maximal Square is a common matrix dynamic programming problem and has appeared in interviews at companies such as Amazon, Google, and Microsoft. It tests understanding of DP state transitions and optimization of 2D grid problems.

Description Solution Video 19:50

221. Maximal Square

Medium50.7% acceptance28 companies

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.

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

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

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

Asked at top 20 of 28 companies

eBay Wise Gsa Capital Oppo DP World PayPal Airbnb Bytedance Booking.com Qualtrics Flipkart PhonePe

+8 more

Zomato Whatnot Karat

Google Oracle Apple NVIDIA Citadel

Topics

19:50

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

221. Maximal Square

Asked at top 20 of 28 companies

Topics

Similar problems