Skip to content

4016. Maximum Area of Two Non-Overlapping Square Submatrices

Description

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

  • mat[r][c] == 1 means the cell at row r and column c is usable.
  • mat[r][c] == 0 means it is not usable.

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

  • Both submatrices must be squares of the same side length k.
  • The two submatrices must not share any cell.
  • Each submatrix can only cover cells where mat[r][c] == 1.

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.

  • First square starts at top-left (0, 0) and covers cells (0, 0), (0, 1), (1, 0), and (1, 1).
  • Second square starts at top-left (1, 2) and covers cells (1, 2), (1, 3), (2, 2), and (2, 3).

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.

  • First square starts at top-left (0, 1) and covers cell (0, 1).
  • Second square starts at top-left (1, 0) and covers cell (1, 0).

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:

  • mat.length == m
  • mat[i].length == n
  • 1 <= m, n <= 500
  • mat[i][j] is either 0 or 1.

Solutions

Solution 1: Dynamic Programming + Enumerating Dividing Lines

Two non-overlapping axis-aligned rectangles can always be separated by a horizontal line or a vertical line (their row intervals or column intervals must be disjoint). Therefore, we only need to consider the case where one square lies entirely above some horizontal dividing line and the other below it, and the case where one lies entirely to the left of some vertical dividing line and the other to its right. The latter can be handled by transposing the matrix and reusing the logic of the former.

For the horizontal case, we design a function \(\textit{calc}(\textit{mat})\):

  • Bottom-up dynamic programming: let \(f[i][j]\) be the maximum side length of an all-\(1\) square with top-left corner at \((i, j)\). If \(\textit{mat}[i][j] = 1\), then \(f[i][j] = \min(f[i+1][j], f[i][j+1], f[i+1][j+1]) + 1\). We use \(g[i]\) to record the maximum side length in row \(i\), then compute the suffix maximum \(\textit{suf}[i] = \max(\textit{suf}[i+1], g[i])\), which represents the maximum side length of an all-\(1\) square within rows \([i, m)\).
  • Top-down dynamic programming: let \(f[i][j]\) be the maximum side length of an all-\(1\) square with bottom-right corner at \((i-1, j-1)\). If \(\textit{mat}[i-1][j-1] = 1\), then \(f[i][j] = \min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1\). Similarly, we compute the prefix maximum \(\textit{pre}[i] = \max(\textit{pre}[i-1], g[i])\), which represents the maximum side length of an all-\(1\) square within rows \([0, i)\).
  • Enumerate the dividing line \(i \in [1, m)\) between every pair of adjacent rows. The maximum side length of an all-\(1\) square above the line is \(\textit{pre}[i]\), and below it is \(\textit{suf}[i]\). Since the two squares must have equal side lengths, the feasible side length is \(t = \min(\textit{pre}[i], \textit{suf}[i])\), and we update the answer with \(t^2\).

Finally, return \(\max(\textit{calc}(\textit{mat}), \textit{calc}(\textit{mat}^\top))\).

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\), where \(m\) and \(n\) are the number of rows and columns of the matrix, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def maxArea(self, mat: list[list[int]]) -> int:
        def calc(mat: list[list[int]]) -> int:
            m, n = len(mat), len(mat[0])

            f = [[0] * (n + 1) for _ in range(m + 1)]
            g = [0] * (m + 1)
            suf = [0] * (m + 1)
            for i in range(m - 1, 0, -1):
                for j in range(n - 1, -1, -1):
                    if mat[i][j]:
                        f[i][j] = min(f[i + 1][j], f[i][j + 1], f[i + 1][j + 1]) + 1
                        g[i] = max(g[i], f[i][j])
                suf[i] = max(suf[i + 1], g[i])

            f = [[0] * (n + 1) for _ in range(m + 1)]
            g = [0] * (m + 1)
            pre = [0] * (m + 1)
            for i in range(1, m + 1):
                for j in range(1, n + 1):
                    if mat[i - 1][j - 1]:
                        f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1
                        g[i] = max(g[i], f[i][j])

                pre[i] = max(pre[i - 1], g[i])

            ans = 0
            for i in range(1, m):
                t = min(pre[i], suf[i])
                ans = max(ans, t * t)
            return ans

        def transpose(mat: list[list[int]]) -> list[list[int]]:
            m, n = len(mat), len(mat[0])
            ans = [[0] * m for _ in range(n)]
            for i in range(m):
                for j in range(n):
                    ans[j][i] = mat[i][j]
            return ans

        return max(calc(mat), calc(transpose(mat)))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
    public int maxArea(int[][] mat) {
        return Math.max(calc(mat), calc(transpose(mat)));
    }

    private int calc(int[][] mat) {
        int m = mat.length, n = mat[0].length;

        int[][] f = new int[m + 1][n + 1];
        int[] g = new int[m + 1];
        int[] suf = new int[m + 1];

        for (int i = m - 1; i > 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (mat[i][j] != 0) {
                    f[i][j] = Math.min(Math.min(f[i + 1][j], f[i][j + 1]), f[i + 1][j + 1]) + 1;
                    g[i] = Math.max(g[i], f[i][j]);
                }
            }
            suf[i] = Math.max(suf[i + 1], g[i]);
        }

        f = new int[m + 1][n + 1];
        g = new int[m + 1];
        int[] pre = new int[m + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (mat[i - 1][j - 1] != 0) {
                    f[i][j] = Math.min(Math.min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1;
                    g[i] = Math.max(g[i], f[i][j]);
                }
            }
            pre[i] = Math.max(pre[i - 1], g[i]);
        }

        int ans = 0;
        for (int i = 1; i < m; i++) {
            int t = Math.min(pre[i], suf[i]);
            ans = Math.max(ans, t * t);
        }
        return ans;
    }

    private int[][] transpose(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] ans = new int[n][m];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans[j][i] = mat[i][j];
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    int maxArea(vector<vector<int>>& mat) {
        return max(calc(mat), calc(transpose(mat)));
    }

private:
    int calc(const vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();

        vector<vector<int>> f(m + 1, vector<int>(n + 1));
        vector<int> g(m + 1), suf(m + 1);

        for (int i = m - 1; i > 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (mat[i][j]) {
                    f[i][j] = min({f[i + 1][j],
                                  f[i][j + 1],
                                  f[i + 1][j + 1]})
                        + 1;
                    g[i] = max(g[i], f[i][j]);
                }
            }
            suf[i] = max(suf[i + 1], g[i]);
        }

        f.assign(m + 1, vector<int>(n + 1));
        g.assign(m + 1, 0);
        vector<int> pre(m + 1);

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (mat[i - 1][j - 1]) {
                    f[i][j] = min({f[i - 1][j],
                                  f[i][j - 1],
                                  f[i - 1][j - 1]})
                        + 1;
                    g[i] = max(g[i], f[i][j]);
                }
            }
            pre[i] = max(pre[i - 1], g[i]);
        }

        int ans = 0;
        for (int i = 1; i < m; i++) {
            int t = min(pre[i], suf[i]);
            ans = max(ans, t * t);
        }

        return ans;
    }

    vector<vector<int>> transpose(const vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();

        vector<vector<int>> ans(n, vector<int>(m));

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans[j][i] = mat[i][j];
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
func maxArea(mat [][]int) int {
    return max(calc(mat), calc(transpose(mat)))
}

func calc(mat [][]int) int {
    m, n := len(mat), len(mat[0])

    f := make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    g := make([]int, m+1)
    suf := make([]int, m+1)

    for i := m - 1; i > 0; i-- {
        for j := n - 1; j >= 0; j-- {
            if mat[i][j] != 0 {
                f[i][j] = min(
                    f[i+1][j],
                    f[i][j+1],
                    f[i+1][j+1],
                ) + 1
                if f[i][j] > g[i] {
                    g[i] = f[i][j]
                }
            }
        }
        suf[i] = max(suf[i+1], g[i])
    }

    f = make([][]int, m+1)
    for i := range f {
        f[i] = make([]int, n+1)
    }
    g = make([]int, m+1)
    pre := make([]int, m+1)

    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if mat[i-1][j-1] != 0 {
                f[i][j] = min(
                    f[i-1][j],
                    f[i][j-1],
                    f[i-1][j-1],
                ) + 1
                if f[i][j] > g[i] {
                    g[i] = f[i][j]
                }
            }
        }
        pre[i] = max(pre[i-1], g[i])
    }

    ans := 0
    for i := 1; i < m; i++ {
        t := min(pre[i], suf[i])
        if t*t > ans {
            ans = t * t
        }
    }
    return ans
}

func transpose(mat [][]int) [][]int {
    m, n := len(mat), len(mat[0])
    ans := make([][]int, n)
    for i := range ans {
        ans[i] = make([]int, m)
    }
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            ans[j][i] = mat[i][j]
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
function maxArea(mat: number[][]): number {
    return Math.max(calc(mat), calc(transpose(mat)));
}

function calc(mat: number[][]): number {
    const m = mat.length;
    const n = mat[0].length;

    let f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    let g = Array(m + 1).fill(0);
    let suf = Array(m + 1).fill(0);

    for (let i = m - 1; i > 0; i--) {
        for (let j = n - 1; j >= 0; j--) {
            if (mat[i][j]) {
                f[i][j] = Math.min(f[i + 1][j], f[i][j + 1], f[i + 1][j + 1]) + 1;
                g[i] = Math.max(g[i], f[i][j]);
            }
        }
        suf[i] = Math.max(suf[i + 1], g[i]);
    }

    f = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    g = Array(m + 1).fill(0);
    const pre = Array(m + 1).fill(0);

    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (mat[i - 1][j - 1]) {
                f[i][j] = Math.min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1;
                g[i] = Math.max(g[i], f[i][j]);
            }
        }
        pre[i] = Math.max(pre[i - 1], g[i]);
    }

    let ans = 0;
    for (let i = 1; i < m; i++) {
        const t = Math.min(pre[i], suf[i]);
        ans = Math.max(ans, t * t);
    }
    return ans;
}

function transpose(mat: number[][]): number[][] {
    const m = mat.length;
    const n = mat[0].length;

    const ans = Array.from({ length: n }, () => Array(m).fill(0));

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            ans[j][i] = mat[i][j];
        }
    }
    return ans;
}

Comments