In this guide, you will discover the process of determining the largest possible square sub-matrix that consists entirely of the value 1 in C++.
Problem statement:
You have a 2D array, and you need to find the largest matrix that consists of the same elements.
Input format:
A 2D matrix of order n X m .
Output format:
An integer representing the area of the largest matrix.
It signifies the total of all the units in the largest possible matrix.
Explanation for an example is as follows:
Matrix is:
{{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}}
Output:
Maximum sized matrix is:
{{'1', '1'},
{'1', '1'}}
Method 1: Brute Force method
Let's consider an illustration to determine the Largest possible square sub-matrix containing only 1s using the brute force technique in C++.
#include <iostream>
#include <vector>
using namespace std;
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int rows = matrix.size();
int cols = matrix[0].size();
int maxSize = 0;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '1') {
int size = 1;
bool isSquare = true;
while (i + size < rows && j + size < cols && isSquare) {
for (int k = i; k <= i + size; ++k) {
if (matrix[k][j + size] == '0') {
isSquare = false;
break;
}
}
for (int k = j; k <= j + size; ++k) {
if (matrix[i + size][k] == '0') {
isSquare = false;
break;
}
}
if (isSquare) size++;
}
maxSize = max(maxSize, size);
}
}
}
return maxSize * maxSize;
}
int main() {
vector<vector<char>> matrix = {
{ '0', '1', '1', '0', '1' },
{ '1', '1', '0', '1', '0' },
{ '0', '1', '1', '1', '0' },
{ '1', '1', '1', '1', '0'},
{ '1', '1', '1', '1', '1' },
{ '0', '0', '0', '0', '0' }
};
cout <<"Taken matrix is "<< endl;
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
cout << matrix[i][j] <<" ";
}
cout << endl;
}
int result = maximalSquare(matrix);
cout << "Size of the largest square: " << result << endl;
return 0;
}
Output:
Explanation:
The program mentioned above is designed to identify a submatrix that is either of size n or a square matrix of order n X n. This process utilizes a brute force approach, involving iterating through the matrix. Initially, a fixed-size submatrix of 2 is selected and shifted horizontally until it reaches the matrix's end. Upon reaching the horizontal end, the submatrix is moved down by one step and the process is repeated from the beginning, sliding it to the end of the matrix once again. This results in the creation of a fixed 2 X 2 sized submatrix.
Afterward, alter the arrangement of the submatrix; modify it to a 3 X 3 dimension. Subsequently, repeat the identical procedure for all the sub-matrices with varying dimensions. This sequence will conclude when no additional sub-matrices are generated. During this traversal of the matrix, ensure to validate whether all the elements within the matrix are uniformly set to one. Upon confirming that all elements are ones, record the size of the matrix in a designated variable. Whenever encountering a sub-matrix with a size exceeding the current variable value, update the variable with this new larger size, ensuring each sized matrix comprises solely ones. Upon completion of this series of operations, display the final value stored in the variable. This will yield the intended outcome. This approach may offer improved efficiency, albeit at the cost of increased time and space complexity to attain the result.
Method 2: Using Dp Array
Let's consider an illustration to determine the largest square sub-matrix with all elements as 1 by employing the dynamic programming array in C++.
#include <iostream>
#include <vector>
using namespace std;
int findMaxSquare(vector<vector<char>>& matrix, vector<vector<int>>& dp, int i, int j) {
if (i < 0 || j < 0 || matrix[i][j] == '0') return 0;
if (dp[i][j] != -1) return dp[i][j];
int left = findMaxSquare(matrix, dp, i, j - 1);
int up = findMaxSquare(matrix, dp, i - 1, j);
int diagonal = findMaxSquare(matrix, dp, i - 1, j - 1);
dp[i][j] = 1 + min(min(left, up), diagonal);
return dp[i][j];
}
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int rows = matrix.size();
int cols = matrix[0].size();
int maxSize = 0;
vector<vector<int>> dp(rows, vector<int>(cols, -1));
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
if (matrix[i][j] == '1') {
maxSize = max(maxSize, findMaxSquare(matrix, dp, i, j));
}
}
}
return maxSize * maxSize;
}
int main() {
vector<vector<char>> matrix = {
{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}
};
int result = maximalSquare(matrix);
cout << "Size of the largest square: " << result << endl;
return 0;
}
Output:
Explanation:
To comprehend the aforementioned code snippet, we will initially examine the variables utilized within the code. To begin with, there is the matrix, a 2D array denoted as input, encompassing only binary values of ones and zeros. The Dp array serves as a dynamic array designated to retain the solutions of sub-problems computed, thus averting calculation errors. This array plays a crucial role in enhancing the efficiency of the recursive problem within the program. Initially, all elements in the dp array are initialized to -1, indicating that they have not been computed yet. The variables i and j are integers representing the current row and indices of the matrix, respectively. Moreover, the integers left, right, and diagonal serve as placeholders to store the outcomes of recursive invocations within the findMaxSquare function. The variable maxSize is responsible for monitoring the primary output, which corresponds to the maximum size achievable for the sub-square.
The initial condition for the findMaxSquare function occurs when either i or j exceeds the matrix boundaries, leading to a return value of zero. Subsequently, the function proceeds to implement memoization. If the values of i and j within the matrix have already been computed and saved in the dp table, it retrieves and returns the stored outcome. Alternatively, it recursively evaluates the impacts of the adjacent left, upper, and diagonal cells, saving the minimum result plus 1 in the dp array. Finally, the function concludes by providing the size of the largest square as the output.
Method 3: Tabulation method
Let's consider an illustration to determine the Largest possible square sub-matrix with all 1s utilizing the tabulation technique in C++.
#include <iostream>
#include <vector>
using namespace std;
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int rows = matrix.size();
int cols = matrix[0].size();
int maxSize = 0;
vector<vector<int>> dp(rows + 1, vector<int>(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] = 1 + min(min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]);
maxSize = max(maxSize, dp[i][j]);
}
}
}
return maxSize * maxSize;
}
int main() {
vector<vector<char>> matrix = {
{'1','0','1','0','0'},
{'1','0','1','1','1'},
{'1','1','1','1','1'},
{'1','0','0','1','0'}
};
int result = maximalSquare(matrix);
for(int i=0;i<matrix.size();i++){
for(int j=0;j<matrix[0].size();j++){
cout << matrix[i][j] << " ";
}
cout<< endl;
}
cout << "Size of the largest square: " << result << endl;
return 0;
}
Output:
Explanation:
The variable found within the program represents a matrix, taking the form of a 2D array populated solely with ones and zeros. Dp, a dynamic array, holds the resolved solutions for sub-problems to prevent miscalculations, thereby enhancing the efficiency of the program's recursion. At the outset, all entries in the dp array are initialized as 0s, indicating that they have not been computed yet. The variables i and j denote the present row and current indices in the matrix. The integers left, right, and diagonal hold the computed outcomes.
The software examines every cell within the provided matrix. When encountering a cell with a value of '1 ', it determines the maximum square size that could terminate at that specific cell, taking into account adjacent cells to the left, above, and diagonally upper-left. It maintains a record of the most extensive square identified. Ultimately, the function provides the total area of the largest square constructed from '1's within the initial matrix.
Conclusion:
The ideal way to wrap up the preceding article is as below:
Brute force method involves
- exhaustive search to find a solution.
The time complexity for this approach is O((mn)^3).
It has a space complexity of O(1).
Implementing a dynamic programming array:
- Time complexity: O(mn^2)
- Space complexity: O(mn)
Tabulation:
- Time complexity: O(mn)
- Space complexity: O(mn)
The straightforward method thoroughly evaluates each potential submatrix, resulting in a notable rise in the time complexity. Conversely, dynamic programming methodologies (including both top-down and bottom-up) enhance the solution by storing intermediate outcomes, notably reducing the time complexity. Within these dynamic programming approaches, the tabulation technique emerges as particularly efficient in both time and space usage. Therefore, it is the preferred method for addressing this issue. In conclusion, while all techniques are capable of resolving the problem, utilizing dynamic programming with tabulation presents the most effective solution, adeptly handling time and space intricacies.
