LeetCode in Kotlin

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

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun maxArea(mat: Array<IntArray>): Int {
        val m = mat.size
        val n = mat[0].size
        val dp = Array<IntArray>(m) { IntArray(n) }
        val top = IntArray(m)
        val bottom = IntArray(m)
        val left = IntArray(n)
        val right = IntArray(n)
        for (r in 0..<m) {
            for (c in 0..<n) {
                if (mat[r][c] == 0) {
                    continue
                }
                if (r == 0 || c == 0) {
                    dp[r][c] = 1
                } else {
                    dp[r][c] = 1 + min(dp[r - 1][c - 1], min(dp[r - 1][c], dp[r][c - 1]))
                }
                val k = dp[r][c]
                top[r] = max(top[r], k)
                left[c] = max(left[c], k)
                bottom[r - k + 1] = max(bottom[r - k + 1], k)

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