Problem Description
This is the problem of finding the largest square composed of 1’s in a given binary matrix. Each element of the matrix is either 0 or 1, and 1 can be included as part of the square.
Determining the size of the square is based on the edge values of each 1, and thus, we will use a Dynamic Programming approach to solve the problem.
Input Format
Given the size of the matrix n x m, the input is provided in the following format.
[
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
]
Output Format
Returns the area of the largest square as an integer.
Example Input and Output
Input:
[
['1', '0', '1', '0', '0'],
['1', '0', '1', '1', '1'],
['1', '1', '1', '1', '1'],
['1', '0', '0', '1', '0']
]
Output: 4
Problem Solving Process
1. Understanding and Analyzing the Problem
This problem requires finding the maximum square made of ‘1’s in a binary matrix.
To do this, we need to keep track of the possible square sizes for each element.
The value of each element in the matrix is determined based on the following rules, with respect to the bottom right corner of the square.
If the element at position (i, j) is ‘1’, then the size of the square with this position as the bottom right corner will be
the minimum value among the left (i, j-1), above (i-1, j), and upper left diagonal (i-1, j-1) positions plus 1.
This allows us to analyze the ‘1’s included in the current position and find the area of the largest square.
2. Algorithm Design
To solve the problem, we apply Dynamic Programming (DP) in the following steps.
- Check the size of the given binary matrix and create a DP array.
- Iterate through each element of the binary matrix and update the DP array whenever a 1 is encountered.
- Find the maximum value in the DP array and return its square to calculate the area of the largest square.
3. Code Implementation
Based on the algorithm design above, let’s implement the code in C++.
Below is the final implementation code.
#include
#include
#include
using namespace std;
int maximalSquare(vector>& matrix) {
if (matrix.empty()) return 0;
int maxSide = 0;
int rows = matrix.size(), cols = matrix[0].size();
vector> dp(rows + 1, vector(cols + 1, 0));
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide; // return area
}
int main() {
vector> matrix = {
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
};
cout << "The area of the largest square is: " << maximalSquare(matrix) << endl;
return 0;
}
4. Code Analysis
This code creates a DP array initialized to 0 and iterates through the input matrix, updating the maximum square size at each position.
The reason for using an array size of (rows + 1) x (cols + 1) is to easily handle boundary conditions in the DP array.
The variable maxSide, which stores the length of the largest side, is used to ultimately calculate the area of the square.
5. Performance Analysis
The time complexity of this algorithm is O(n * m), and the space complexity is also O(n * m).
The performance increases proportionally to the size of the matrix n x m, making it efficient for processing large matrices.
Conclusion
In this article, we discussed how to solve the algorithm problem of finding the area of the largest square in a binary matrix using C++.
The Dynamic Programming approach is very effective in decomposing the problem and finding the optimal solution.
I hope this course provided an opportunity to deepen your understanding of data structures and algorithms in C++ through practical exercises.