Problem statement

https://binarysearch.com/problems/Minimal-Submatrices/

Solution

The idea is to use Leetcode problem 239. Sliding Window Maximum first for one dimention and then for another.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, matrix, k):
        def maxS(nums):
            deq, n, ans = deque([0]), len(nums), []

            for i in range (n):
                if deq[0] <= i - k:
                    deq.popleft()
                while deq and nums[i] <= nums[deq[-1]] :
                    deq.pop()
                deq.append(i)
                ans.append(nums[deq[0]])
                
            return ans[k-1:]

        t = [maxS(row) for row in matrix]
        t2 = [maxS(row) for row in zip(*t)]
        return [x for x in zip(*t2)]