Problem Statement in English

You’re given a 2D grid of integers and an integer k. You need to find the minimum absolute difference between any two distinct elements in every k x k submatrix of the grid.

Approach

All you need to do is to iterate over all k x k submatrices, extract the elements, sort them, and find the minimum absolute difference between any two distinct elements.

And we’re done!

Solution in Python


class Solution:
    def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
        M = len(grid)
        N = len(grid[0])

        res = [[0 for _ in range(N - k + 1)] for _ in range(M - k + 1)]

        for i in range(M - k + 1):
            for j in range(N - k + 1):
                if k == 1:
                    res[i][j] = 0
                    continue

                s = []

                for x in range(i, i + k):
                    for y in range(j, j + k):
                        s.append(grid[x][y])

                temp = inf
                s.sort()
                for e in range(1, len(s)):
                    if s[e - 1] != s[e]:
                        temp = min(temp, s[e] - s[e - 1])

                res[i][j] = temp if temp != inf else 0

        return res

Complexity

  • Time: $O(MNk^2\log k)$
    Since we need to iterate over all k x k submatrices and sort the elements of each submatrix, which takes O(k^2\log k) time.

  • Space: $O(k^2)$
    Since we need to store the elements of each k x k submatrix in a list before sorting.

And we are done.