Largest Plus Sign LeetCode solution in Java

1
class Solution {
2
  public int orderOfLargestPlusSign(int n, int[][] mines) {
3
    // Create the matrix
4
    int[][] arr = new int[n][n];
5
    for (int[] subArray : arr) {
6
      Arrays.fill(subArray, 1);
7
    }
8

9
    for (int i = 0; i < mines.length; i++) {
10
      arr[mines[i][0]][mines[i][1]] = 0;
11
    }
12

13
    // Prefix Count DP arrays
14
    int[][] dpTop = new int[arr.length][arr.length];
15
    int[][] dpLeft = new int[arr.length][arr.length];
16
    int[][] dpRight = new int[arr.length][arr.length];
17
    int[][] dpBottom = new int[arr.length][arr.length];
18

19
    // Prefix count of 1 cells on top and left directions
20
    for (int i = 0; i < arr.length; i++) {
21
      for (int j = 0; j < arr.length; j++) {
22
        if (i - 1 >= 0 && arr[i - 1][j] == 1) {
23
          dpTop[i][j] = 1 + dpTop[i - 1][j];
24
        }
25

26
        if (j - 1 >= 0 && arr[i][j - 1] == 1) {
27
          dpLeft[i][j] = 1 + dpLeft[i][j - 1];
28
        }
29
      }
30
    }
31

32
    // Prefix count of 1 cells on bottom and right directions
33
    for (int i = arr.length - 1; i >= 0; i--) {
34
      for (int j = arr.length - 1; j >= 0; j--) {
35
        if (i + 1 < arr.length && arr[i + 1][j] == 1) {
36
          dpBottom[i][j] = 1 + dpBottom[i + 1][j];
37
        }
38

39
        if (j + 1 < arr.length && arr[i][j + 1] == 1) {
40
          dpRight[i][j] = 1 + dpRight[i][j + 1];
41
        }
42
      }
43
    }
44

45
    int maxPlusSignLength = 0;
46
    for (int i = 0; i < arr.length; i++) {
47
      for (int j = 0; j < arr.length; j++) {
48
        if (arr[i][j] == 0) continue;
49

50
        // Minimum adjacent 1 cell count from all four directions to ensure symmetry
51
        int minAdjacentOnes =
52
            Math.min(Math.min(dpTop[i][j], dpBottom[i][j]), Math.min(dpLeft[i][j], dpRight[i][j]));
53
        maxPlusSignLength = Math.max(maxPlusSignLength, minAdjacentOnes + 1);
54
      }
55
    }
56

57
    return maxPlusSignLength;
58
  }
59
}