Given a matrix that contains only 1s and 0s, find the largest cross which contains only 1s, with the same arm lengths and the four arms joining at the central point.

Return the arm length of the largest cross.

Assumptions

• The given matrix is not null, has size of N * M, N > = 0 and M > = 0.

Examples

{ {0, 0, 0, 0},

{1, 1,1, 1},

{0,1, 1, 1},

{1, 0,1, 1} }

the largest cross of 1s has arm length 2.

Approach: Preprocess the matrix, store each direction's longest 1s.(1D array DP) left, right, up, down. for each matrix[i][j], find the

result[i][j] = Min(left[i][j], right[i][j], up[i][j], down[i][j]). max = Max(result[i][j], max).

public class Solution {
  public int largest(int[][] matrix) {
    // Write your solution here.
    if (matrix == null || matrix.length == 0) {
      return 0;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    int max = 0;
    int[][] left = new int[m][n];
    int[][] right = new int[m][n];
    int[][] up = new int[m][n];
    int[][] down = new int[m][n];
    int[][] min = new int[m][n];

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (j == 0) {
          left[i][j] = matrix[i][j];
        } else if (matrix[i][j] == 1) {
          left[i][j] = left[i][j - 1] + 1;
        }
      }
    }

    for (int i = 0; i < m; i++) {
      for (int j = n - 1; j >= 0; j--) {
        if (j == n - 1) {
          right[i][j] = matrix[i][j];
        } else if (matrix[i][j] == 1) {
          right[i][j] = right[i][j + 1] + 1;
        }
      }
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (i == 0) {
          up[i][j] = matrix[i][j];
        } else if (matrix[i][j] == 1) {
          up[i][j] = up[i - 1][j] + 1;
        }
      }
    }

    for (int i = m - 1; i >= 0; i--) {
      for (int j = 0; j < n; j++) {
        if (i == m - 1) {
          down[i][j] = matrix[i][j];
        } else if (matrix[i][j] == 1) {
          down[i][j] = down[i + 1][j] + 1;
        }
      }
    }

    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        min[i][j] = Math.min(left[i][j], right[i][j]);
        min[i][j] = Math.min(min[i][j], up[i][j]);
        min[i][j] = Math.min(min[i][j], down[i][j]);
        if (min[i][j] > max) {
          max = min[i][j];
        }
      }
    }
    return max;
  }
}

Time : O(n^2) 5*n^2 5 for for to scan the matrix.

Space: O(n^2)