2.1 Largest Square of 1s in binary matrix

Assumption: The given matrix is not null and guaranteed to be of size n*n, n >= 0

Input: int[][] matrix

Output: int the length of the largest square of 1s

Solution:

1. In order to find a square, lock in the position of its bottom-right corner in the matrix, check its top, left, and top-left (3 directions) for the max size of squares

2. Induction rule: dp[i][j] represents the max size of square w/ its bottom-right corner at (i, j)

= min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

3. Base case: dp[0][j] = matrix[0][j], dp[i][0] = matrix[i][0], if matrix[i][j] == 0, else = 1

TC: O(n^2)

SC: O(n^2) Could be optimize by using % 2 on index

public int largest (int[][] matrix) {
  int n = matrix.length;
  if (n == 0) {
     return 0;
  }
  int res = 0;
  int[][] dp = new int[n][n];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      //base case
      if (i == 0 || j == 0) {
        dp[i][j] = matrix[i][j] == 1 ? 1 : 0;
      } else if (matrix[i][j] == 1) {
        dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i - 1][j] + 1);
        dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i][j]);
      }
      res = Math.max(res, dp[i][j]);
    }
   }
   return res;
}