LeetCode-in-Java

4016. Maximum Area of Two Non-Overlapping Square Submatrices

Medium

You are given a 2D integer matrix mat of size m × n, where:

Your task is to find two submatrices that satisfy the following conditions:

Return the maximum possible area of each of the two squares. If it is not possible to choose two such squares, return 0.

Example 1:

Input: mat = [[1,1,1,0],[1,1,1,1],[0,0,1,1]]

Output: 4

Explanation:

The largest equal non-overlapping squares have side length k = 2 with area 4.

Thus, the answer is 4.

Example 2:

Input: mat = [[0,1],[1,0]]

Output: 1

Explanation:

The largest equal non-overlapping squares have side length k = 1 with area 1.

Thus, the answer is 1.

Example 3:

Input: mat = [[0,0],[0,1]]

Output: 0

Explanation:

There is only one usable cell, so it is impossible to choose two non-overlapping squares. Thus, the answer is 0.

Constraints:

Solution

@SuppressWarnings("java:S6885")
public class Solution {
    public int maxArea(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dp = new int[m][n];
        int[] top = new int[m];
        int[] bottom = new int[m];
        int[] left = new int[n];
        int[] right = new int[n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (mat[r][c] == 0) {
                    continue;
                }
                if (r == 0 || c == 0) {
                    dp[r][c] = 1;
                } else {
                    dp[r][c] = 1 + Math.min(dp[r - 1][c - 1], Math.min(dp[r - 1][c], dp[r][c - 1]));
                }
                int k = dp[r][c];
                top[r] = Math.max(top[r], k);
                left[c] = Math.max(left[c], k);
                bottom[r - k + 1] = Math.max(bottom[r - k + 1], k);

                right[c - k + 1] = Math.max(right[c - k + 1], k);
            }
        }
        for (int r = 1; r < m; r++) {
            top[r] = Math.max(top[r], top[r - 1]);
        }
        for (int c = 1; c < n; c++) {
            left[c] = Math.max(left[c], left[c - 1]);
        }
        for (int r = m - 2; r >= 0; r--) {
            bottom[r] = Math.max(bottom[r], bottom[r + 1]);
        }
        for (int c = n - 2; c >= 0; c--) {
            right[c] = Math.max(right[c], right[c + 1]);
        }
        int best = 0;
        for (int r = 0; r < m - 1; r++) {
            best = Math.max(best, Math.min(top[r], bottom[r + 1]));
        }
        for (int c = 0; c < n - 1; c++) {
            best = Math.max(best, Math.min(left[c], right[c + 1]));
        }
        return best * best;
    }
}