2.4 Largest 1-bordered square

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

Input: int[][] binary matrix

Output: length of the largest square

Solution: dp[i][j] represents the max length of the square with bottom-right corner at (i, j). Only need to check max lengths of its left and top directions (bottom and right sides of the square)

TC: n * m * n(or m) = O(n^3)

SC: O(n*m)

Map on matrix[i - 1][j - 1]

public int largest(int[][] matrix) {
  int n = matrix.length;
  int m = matrix[0].length;
  if (n == 0 || m == 0) { return 0; }
  
  int res = 0;
  int[][] left = new int[n + 1][m + 1];
  int[][] up = new int[n + 1][m + 1];

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (matrix[i][j] == 1) {
        left[i + 1][j + 1] = left[i + 1][j] + 1;
        up[i + 1][j + 1] = up[i][j + 1] + 1;
        int max = Math.min(left[i + 1][j + 1], up[i + 1][j + 1]);
        for (; max >= 1; max--) {
          if (left[i + 1 - max + 1][j + 1] >= max && up[i + 1][j + 1 - max + 1] >= max) {
            res = Math.max(res, max);
            break;
          }
        }
      }
    }
  }
  return res;
}

If map on matrix[i][j], similar to 2.2, needs to check index bound

for (int i = 0; i < n; i++) {
     for (int j = 0; j < m; j++) {
       if (matrix[i][j] == 1) {
         if (i == 0 && j == 0) {
           left[i][j] = 1;
           up[i][j] = 1;
         } else if (i == 0) {
           left[i][j] = left[i][j - 1] + 1;
           up[i][j] = 1;
         } else if (j == 0) {
           left[i][j] = 1;
           up[i][j] = up[i - 1][j] + 1;
         } else {
           left[i][j] = left[i][j - 1] + 1;
           up[i][j] = up[i - 1][j] + 1;
         }
         int max = Math.min(left[i][j], up[i][j]);
           for (; max >= 1; max--) {
             if(left[i + 1 - max][j] >= max && up[i][j + 1 - max] >= max) {
               res = Math.max(res, max);
               break;
             }
           }
       }  
     }
   }
   return res;