Medium

Minimum Absolute Difference in Sliding Submatrix

LAB

For each k by k submatrix, return the minimum absolute difference between any two distinct values.

EXAMPLES

Example 1

Input
{
  "grid": [
    [
      1,
      8
    ],
    [
      3,
      4
    ]
  ],
  "k": 2
}

Output
[
  [
    1
  ]
]

FUNCTION SHAPE

grid: intMatrixk: int→intMatrix

SOLUTION NOTE

Fixed 2D sliding window. The problem asks for distinct values, so duplicates must not create a false difference of 0. The source shows a direct set-based version and mentions optimizing with a SortedSet plus frequencies.

Reveal reference solution +

pythonREFERENCE

from itertools import pairwise

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

    for i in range(m - k + 1):
        for j in range(n - k + 1):
            values = set()
            for ii in range(k):
                for jj in range(k):
                    values.add(grid[i + ii][j + jj])
            ordered = sorted(values)
            res[i][j] = min((b - a for a, b in pairwise(ordered)), default=0)

    return res

TimeO(m * n * k² log k)

SpaceO(k²)

Open on LeetCode ↗