221. Maximal Square

/*
 * Find the upper left corner of the square
 *
 * we can exit when:
 * - the row we are on prevents a larger square
 * - the col we are on prevents a larger square
 *
 * future enhancement: use dynamic programming, a separate matrix
 * (can be optimized into a single array + variables)
 * where dp[i] = lower right corner of square with the value length
 * dp[i] can be calculated by looking left, up, and left-up
 */

class Solution {
  public int maximalSquare(char[][] matrix) {
    int maxSide = 0;

    int rows = matrix.length;

    if (rows == 0) return 0;

    int cols = matrix[0].length;

    int row = 0;
    int col = 0;

    while(row < rows && (rows - row) > maxSide) {
      while(col < cols && (cols - col) > maxSide) {
        if (matrix[row][col] == '1') {
          maxSide = Math.max(maxSide, getMaxSide(matrix, row, col));
        }
        col++;
      }

      row++;
      col = 0;
    }

    return maxSide * maxSide;
  }

  // Requires matrix[row][col] == 1
  public int getMaxSide(char[][] matrix, int row, int col) {
    int maxSide = 1;

    int rows = matrix.length;
    int cols = matrix[0].length;

    while(true) {
      // Bounds checking
      if (row + maxSide >= rows) break;
      if (col + maxSide >= cols) break;

      // check bottom border
      for(int cOffset = 0; cOffset < maxSide + 1; cOffset++) {
        if (matrix[row + maxSide][col + cOffset] == '0') {
          return maxSide;
        }
      }

      // check right border
      // excluding last element because bottom border checked it
      for(int rOffset = 0; rOffset < maxSide; rOffset++) {
        if (matrix[row + rOffset][col + maxSide] == '0') {
          return maxSide;
        }
      }

      maxSide++;
    }

    return maxSide;
  }
}