Determine the largest square surrounded by a bunch of matches (each match is either horizontal or vertical), return the length of the largest square.
The input is a matrix of points. Each point has one of the following values:
0 - there is no match to its right or bottom.
1 - there is a match to its right.
2 - there is a match to its bottom.
3 - there is a match to its right, and a match to its bottom.
Assumptions
The given matrix is guaranteed to be of size M * N, where M, N >= 0
Examples
{{3, 1, 1, 3, 0, 1, 1, 0},
{2, 0, 0, 2, 0, 0, 0, 0},
{3, 1, 3, 0, 0, 0, 0, 0},
{2, 0, 2, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0, 0, 0}}
This matrix represents the following bunch of matches:
The largest square has length of 2.
public class Solution {
public int largestSquareOfMatches(int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
if (N == 0 || M == 0) return 0;
int result = 0;
int[][] down = new int[N + 1][M + 1];
int[][] right = new int[N + 1][M + 1];
for (int i = N - 1; i >= 0; i--){
for (int j = M - 1; j >= 0; j--){
int curNum = matrix[i][j];
if(hasRight(curNum)){
right[i][j] = right[i][j + 1] + 1;
}
if(hasDown(curNum)){
down[i][j] = down[i + 1][j] + 1;
}
//if has both, can make possible square
if(hasBoth(curNum)){
for(int maxLength = Math.min(down[i][j], right[i][j]); maxLength >= 1; maxLength--){
//if two other edges exist at cur side length aka maxLength
if(right[i + maxLength][j] >= maxLength && down[i][j + maxLength] >= maxLength){
result = Math.max(result, maxLength);
}
}
}
}
}
return result;
}
private boolean hasRight(int num){
if (num == 3 || num == 1) return true;
return false;
}
private boolean hasDown(int num){
if (num == 2 || num == 3) return true;
return false;
}
private boolean hasBoth(int num){
if (num == 3) return true;
return false;
}
}
TC: O(NM)
SC: O(NM)
