Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The required difference is between distinct values, so duplicate occurrences must not create an artificial zero answer. Once a submatrix's distinct values are sorted, the smallest difference occurs between neighboring values: any nonadjacent gap includes at least one smaller adjacent gap.

Approach

Enumerate each top-left position whose k-by-k submatrix fits inside the grid. Insert all values in that submatrix into a set. If there is only one distinct value, store zero as required. Otherwise sort the distinct values and scan adjacent pairs for the smallest difference.

Place that minimum in the output cell corresponding to the submatrix's top-left position. The implementation rebuilds the set and sorting for each submatrix independently, rather than incrementally maintaining a sliding structure. A one-cell submatrix naturally takes the single-distinct-value branch.

class Solution:
    def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
        n = len(grid)
        m = len(grid[0])
        res = [[0] * (m - k + 1) for _ in range(n - k + 1)]

        for i in range(n):
            for j in range(m):
                if i + k <= n and j + k <= m:
                    curr = set()
                    for ii in range(i, i + k):
                        for jj in range(j, j + k):
                            curr.add(grid[ii][jj])

                    if len(curr) == 1:
                        res[i][j] = 0
                    else:
                        mn = inf
                        s = sorted(curr)
                        for ii, v in enumerate(s):
                            if ii == 0:
                                continue
                            mn = min(mn, v - s[ii - 1])
                        res[i][j] = mn

        return res

Complexity analysis

Let r and c be the grid dimensions and P=(r-k+1)(c-k+1). Time is O(rc + Pk^2log(k+1)), or O(Pk^2log(k+1)) since Pk^2>=r*c. This includes Python's checks at all grid positions and remains valid for k=1, when all P output cells still need processing. Auxiliary space is O(k^2) for each rebuilt set and sorted array, excluding the O(P) output.