# 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:

![](https://laicode-problem-assests.s3-us-west-2.amazonaws.com/public/638img.png)

The largest square has length of 2.

```java
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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://llssff.gitbook.io/coding-problems/dynamic-programming/largest-square-of-matches.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.