Largest Square of Matches

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)