পাইথনে ম্যাট্রিক্স থেকে সব k×k সাবম্যাট্রিক্সের ন্যূনতম মান বের করা

সমাধানের ধাপসমূহ (Sliding Window Minimum / Monotonic Deque - ২D)

1. প্রথমে প্রতিটি সারির জন্য স্লাইডিং উইন্ডো মিনিমাম (১D) ক্যালকুলেট করুন দিক k দিয়ে। ফলাফল নতুন ম্যাট্রিক্সে রাখুন।

2. তারপর প্রতিটি কলামের জন্য স্লাইডিং উইন্ডো মিনিমাম (১D) ক্যালকুলেট করুন দিক k দিয়ে।

3. ফাইনাল ম্যাট্রিক্স থেকে (i+k-1, j+k-1) পজিশনগুলো নিয়ে রেজাল্ট ম্যাট্রিক্স বানান (আকার: (n-k+1) x (m-k+1))।

পাইথন কোড উদাহরণ

import collections
class Solution:
    def solve(self, matrix, k):
        for r, row in enumerate(matrix):
            q = collections.deque()
            nrow = []
            for i in range(len(row)):
                if q and q[0] == i - k:
                    q.popleft()
                while q and row[q[-1]] > row[i]:
                    q.pop()
                q.append(i)
                nrow.append(row[q[0]])
            matrix[r] = nrow
        for j in range(len(matrix[0])):
            q = collections.deque()
            ncol = []
            for i in range(len(matrix)):
                if q and q[0] == i - k:
                    q.popleft()
                while q and matrix[q[-1]][j] > matrix[i][j]:
                    q.pop()
                q.append(i)
                ncol.append(matrix[q[0]][j])
            for i in range(len(matrix)):
                matrix[i][j] = ncol[i]
        ret = [[0] * (len(matrix[0]) - k + 1) for _ in range(len(matrix) - k + 1)]
        for i in range(len(ret)):
            for j in range(len(ret[0])):
                ret[i][j] = matrix[i + k - 1][j + k - 1]
        return ret

ob = Solution()
print(ob.solve(matrix=[[3, 5, 6], [8, 6, 5], [4, 3, 12]], k=2))

ইনপুট

[[3,5,6],[8,6,5],[4,3,12]], 2

আউটপুট

[[3, 5], [3, 3]]