2.2 Longest Cross of 1s in binary matrix

Assumption: Given matrix is not null, size of n * m, n & m >= 0

Input: int[][] matrix with matrix.length = n, matrix[0].length = m

Output: int the arm length of the longest cross

Solution:

1. Maintain four directions to store the longest consecutive 1s (as in 1.1)

2. Find the min among the four directions

dp[i][j] = min(dp1, dp2, dp3, dp4)

left -> right  dp1[n][m]
0 1 0 0			matrix[i][j] == 1, dp[i][j] = dp[i][j - 1] + 1   
1 2 3 4			refer to left
0 1 0 0
0 1 0 0

right - > left dp2[n][m]
0 1 0 0 		matrix[i][j] == 1, dp[i][j] = dp[i][j + 1] + 1  
4 3 2 1			refer to right
0 1 0 0 
0 1 0 0

up -> down M3[n][m]
0 1 0 0			matrix[i][j] == 1, dp[i][j] = dp[i - 1][j] + 1
1 2 1 1			refer to top
0 3 0 0
0 4 0 0

down -> up M4[n][m]
0 4 0 0			matrix[i][j] == 1, dp[i][j] = dp[i + 1][j] + 1
1 3 1 1 		refer to bottom
0 2 0 0
0 1 0 0

TC: 4 for loops 4*n*m + get min n*m = O(n*m)

SC: Merge 4 into 2 int[][], = O(n*m)

public int largest(int[][] matrix) {
  int n = matrix.length;
  int m = matrix[0].length;
  if (n == 0 || m == 0) { return 0; }
  
  // maintain 2 int[][]
  int[][] leftUp = leftUp(matrix, n, m);
  int[][] rightDown = rightDown(matrix, n, m);
  return merge(leftUp, rightDown, n, m);
}

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++) {
      // initialize
      if (matrix[i][j] == 1) {
         if (i = 0 && j = 0) {
           up[i][j] = 1;
           left[i][j] = 1; 
         } else if (i == 0) { // top row
	up[i][j] = 1;
            left[i][j] = left[i][j - 1] + 1;
         } else if (j == 0) { // left column
            up[i][j] = up[i - 1][j] + 1;
            left[i][j] = 1;
         } else {
            up[i][j] = up[i - 1][j] + 1;
            left[i][j] - left[i][j - 1] + 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) {
        if (i = n - 1 && j = m - 1) {
          right[i][j] = 1;
          down[i][j] = 1;
        } else if (i = n - 1) { // bottom row
          right[i][j] = right[i][j + 1] + 1;
           down[i][j] = 1;
        } else if (j = m - 1) {  // right column
          right[i][j] = 1;
          down[i][j] = down[i + 1][j] + 1;
        } else {
          right[i][j] = right[i][j + 1] + 1;
          down[i]i[j] = down[i + 1][j];
        }
      }
    }
  }
  merge(right, down, n, m);
  return right;
}

private int merge (int[][] leftUp, int[][] rightDown, int n, int m) {
  int res = 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]);
      res = Math.max(leftUp[i][j], res);
    }
  }
  return res;
}