Largest X of 1s

Given a matrix that contains only 1s and 0s, find the largest X shape 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 X shape.

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 X of 1s has arm length 2.

public class Solution {
  public int largest(int[][] matrix) {
    //high level
    //track the largest leg in all four directions
    //take the min for each starting spot
    int N = matrix.length;
    int M = matrix[0].length;
    if (N == 0 || M == 0) return 0;
    int[][]leftUp = leftUp(matrix, N, M);
    int[][]rightDown = rightDown(matrix,N,M);
    return merge(leftUp, rightDown, N, M);
  }
  private int merge(int[][] leftUp, int[][] rightDown, int N, int M){
    int result = 0;
    for (int i = 0; i < N; i++){
      for (int j = 0; j < M; j++){
        leftUp[i][j] = Math.min(leftUp[i][j],rightDown[i][j]);
        result = Math.max(result, leftUp[i][j]);
      }
    }
    return result;
  }

  private int[][] leftUp(int[][] matrix, int N, int M){
    int[][] left = new int[N][M];
    int[][] up = new int[N][M];
    for (int i = 0; i < N; i++){
      for (int j = 0; j < M; j++){
        if (matrix[i][j] == 1){
          left[i][j] = getNumber(left, i - 1, j - 1, N, M) + 1;
          up[i][j] = getNumber(up, i - 1, j + 1, N, M) + 1;
        }
      }
    }
    merge(left,up, N, M);
    return left;
  }

  private int[][] rightDown(int[][] matrix, int N, int M){
    int[][] right = new int[N][M];
    int[][] down = new int[N][M];
    for(int i = N - 1; i >= 0; i--){
      for(int j = M - 1; j >=0; j--){
        if (matrix[i][j] == 1){
          right[i][j] = getNumber(right, i + 1, j + 1, N, M) + 1;
          down[i][j] = getNumber(down, i + 1, j - 1, N, M) + 1;
        }
      }
    }
    merge(right, down, N, M);
    return right;
  }

  private int getNumber(int[][] input, int x, int y, int N, int M){
    if (x < 0 || x >= N || y < 0 || y >= M) return 0;
    return input[x][y];
  }
}

TC: O(NM)

SC: O(NM)