Largest Square of Ones

Question

The question asks the candidate to find the area of the largest square that can be formed using only '1's in a given binary matrix.

Codemia · Accepted Answer

To solve the problem of finding the largest square of '1's in a binary matrix, we can utilize a dynamic programming approach. The idea is to maintain a 2D array `dp` where `dp[i][j]` represents the side length of the largest square whose bottom-right corner is at cell `(i, j)`. If the cell in the original matrix is '1', we can calculate the value of `dp[i][j]` based on the minimum of the squares that can be formed from the left, top, and top-left cells.

1. Initialize a 2D array `dp` of the same dimensions as the input matrix, filled with zeros.
2. Iterate through each cell in the matrix:
   - If `matrix[i][j]` is '1', update `dp[i][j]` as follows:
     `dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`
   - Keep track of the maximum value found in `dp`, which represents the side length of the largest square.
3. The area of the largest square is the square of the maximum value found.

The time complexity of this algorithm is O(m * n), where m is the number of rows and n is the number of columns in the matrix. This is because we are iterating through each cell once. The space complexity is also O(m * n) due to the additional `dp` array. However, we can optimize the space complexity to O(n) by only keeping track of the current and previous rows.

```python
def maximalSquare(matrix):
    if not matrix:
        return 0
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    max_side = 0

for i in range(m):
        for j in range(n):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                max_side = max(max_side, dp[i][j])

return max_side * max_side
```

It's important to consider edge cases such as:
- An empty matrix, which should return an area of 0.
- A matrix filled with '0's, which should also return an area of 0.
- A matrix filled with '1's, where the area should be the square of the side length of the matrix.

Largest Square of Ones

Airwallex

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Airwallex Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string