Given a matrix of N rows and N columns in square form. The matrix elements are numbers from 0 to 9, the task is to identify the largest square within the limits of the matrix with a single distinct digit.
Example :
Input : N= 4 3 3 3 1 3 3 3 3 3 3 3 9 1 0 3 2 Output : 3 Explanation : The largest square that lies within the bounds of the matrix and contains a single distinct digit is of size 3 hence the output is 3. Input : N=5 3 2 2 2 2 2 2 2 4 1 1 2 2 4 2 2 2 2 7 9 3 1 5 2 7 Output : 2 Explanation : The largest square that lies within the bounds of the matrix and contains a single distinct digit is of size 2 hence the output is 2.
Brute force Approach: O(N^4) :
1. A brute force solution is to fix the lower right corner of the square and then incrementally increase its size while possible.
2. When going from size L to L+1 we need to check if all the 2∗L+1 new values (those that are now on the left and the upper borders) are all equal to the fixed digit.
3. This algorithm has a complexity of O(N^4).
4. The worst case is when the matrix contains only a single distinct digit.
Time Complexity : of above approach is O(N^4) we can reduce it to O(N^3).
Efficient Approach 1: O(N^3) :
1. We can preprocess for each cell (i,j) the number of cells equal to it if we move up: (i−1,j),(i−2,j),… and so on.
2. This can be done in a total time of O(N^2) .
3. Now we can extend from a square of size L to L+1 in O(1)
4 . For a fixed lower right corner and certain size L we need to check if each cell on the lower border has at least L equal values on top of it (these are the preprocessed values).
5. As we increase the size of the square, we can maintain the minimum of the preprocessed values for the cells on the lower border.
6. We should stop when this minimum value becomes less then the size of the square.
7. This solution has a running time of O(N^3).
Time Complexity : of above approach is O(N^3) we can reduce it to O(N^2).
Efficient Approach 2: O(N^2) :
In order to get an even better complexity we should use dynamic programming:
- dp[i][j]= the size of the largest square containing a single distinct digit with the lower right corner in (i,j).
1. The answer is equal to max(dp[i][j],1≤i,j≤N).
2. In order to find the recurrence, there’s an important observation to help us. If the dp[i][j]=L
3. Then dp[i][j−1],dp[i−1][j],dp[i−1][j−1]≥L−1.
4. In other words, if the largest square for cell (i,j) has size L.
5. Then the largest squares for cells (i,j−1), (i−1,j) and (i−1,j−1) have a size of at least L−1. Therefore, we can come up with the recurrence:
- dp[i][j]=min(dp[i][j−1],dp[i−1][j],dp[i−1][j−1])+1 if the value of cell (i,j) is equal to those of cells (i−1,j),(i,j−1), (i-1, j-1) or 1 otherwise.
If we want to optimize the memory used, we notice that in order to calculate a line i in dp, we only need to know the previous line of dp and lines i and i−1 of the matrix. Therefore, we can compute dp using only O(N) additional memory.
Implementation :
// Find the size of the largest square that lies within the
// bounds of the matrix and contains a single distinct
// digit.
#include <bits/stdc++.h>
using namespace std;
// funnction to size of the largest square
int largestSquare(const vector<vector<int> >& A)
{
// dp vector
vector<int> dp[2];
// variable to calculate the size
int N = (int)A.size();
// resize of the dp vector
dp[0].resize(N + 5);
dp[1].resize(N + 5);
// intialization to 1
for (int i = 0; i < N; i++)
dp[0][i] = 1;
// dec sol equal to 1
int sol = 1;
// the largest squares for cells (i,j−1), (i−1,j) and
// (i−1,j−1) have a size of at least L−1. Therefore, we
// can come up with the recurrence:
/* dp[i][j] = min(dp[i][j−1], dp[i−1][j], dp[i−1][j−1]) + 1 if the value of cell(i, j)
is equal to those of cells(i−1, j),
(i, j−1),
(i - 1, j - 1)
or 1 otherwise. */
for (int i = 1; i < N; i++)
{
dp[1][0] = 1;
for (int j = 1; j < N; j++) {
if (A[i][j] == A[i - 1][j]
&& A[i][j] == A[i][j - 1]
&& A[i][j] == A[i - 1][j - 1])
dp[1][j]
= 1
+ min(min(dp[0][j], dp[0][j - 1]),
dp[1][j - 1]);
else
dp[1][j] = 1;
sol = max(sol, dp[1][j]);
}
for (int j = 0; j < N; j++)
dp[0][j] = dp[1][j];
}
// return the size
return sol;
}
// Driver code
int main()
{
// variable N
int N;
N = 4;
// Matrix of N x N
vector<vector<int> > A{ { 3, 3, 3, 1 },
{ 3, 3, 3, 3 },
{ 3, 3, 3, 9 },
{ 1, 0, 3, 2 } };
// function call
cout << largestSquare(A) << "\n";
return 0;
}
Output :
3
Time Complexity : O(n^2)
Space Complexity : O(N)
