3567. Minimum Absolute Difference in Sliding Submatrix

Problem Link

Description

---

You are given an m x n integer matrix grid and an integer k.

For every contiguous k x k submatrix of grid, compute the minimum absolute difference between any two distinct values within that submatrix.

Return a 2D array ans of size (m - k + 1) x (n - k + 1), where ans[i][j] is the minimum absolute difference in the submatrix whose top-left corner is (i, j) in grid.

Note: If all elements in the submatrix have the same value, the answer will be 0.

A submatrix (x1, y1, x2, y2) is a matrix that is formed by choosing all cells matrix[x][y] where x1 <= x <= x2 and y1 <= y <= y2.

 

Example 1:

Input: grid = [[1,8],[3,-2]], k = 2

Output: [[2]]

Explanation:

• There is only one possible k x k submatrix: [[1, 8], [3, -2]].
• Distinct values in the submatrix are [1, 8, 3, -2].
• The minimum absolute difference in the submatrix is |1 - 3| = 2. Thus, the answer is [[2]].

Example 2:

Input: grid = [[3,-1]], k = 1

Output: [[0,0]]

Explanation:

• Both k x k submatrix has only one distinct element.
• Thus, the answer is [[0, 0]].

Example 3:

Input: grid = [[1,-2,3],[2,3,5]], k = 2

Output: [[1,2]]

Explanation:

• There are two possible k × k submatrix:

  <ul>
  	<li>Starting at <code>(0, 0)</code>: <code>[[1, -2], [2, 3]]</code>.
  
  	<ul>
  		<li>Distinct values in the submatrix are <code>[1, -2, 2, 3]</code>.</li>
  		<li>The minimum absolute difference in the submatrix is <code>|1 - 2| = 1</code>.</li>
  	</ul>
  	</li>
  	<li>Starting at <code>(0, 1)</code>: <code>[[-2, 3], [3, 5]]</code>.
  	<ul>
  		<li>Distinct values in the submatrix are <code>[-2, 3, 5]</code>.</li>
  		<li>The minimum absolute difference in the submatrix is <code>|3 - 5| = 2</code>.</li>
  	</ul>
  	</li>
  </ul>
  </li>
  <li>Thus, the answer is <code>[[1, 2]]</code>.</li>
  

 

Constraints:

• 1 <= m == grid.length <= 30
• 1 <= n == grid[i].length <= 30
• -105 <= grid[i][j] <= 105
• 1 <= k <= min(m, n)

Solution

---

Python3

class Solution:
    def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]:
        rows, cols = len(grid), len(grid[0])
        rSize, cSize = rows - k + 1, cols - k + 1
        ans = [[None] * cSize for _ in range(rSize)]
        
        for i in range(rSize):
            for j in range(cSize):
                curr = set()
 
                for ki in range(i, i + k):
                    for kj in range(j, j + k):
                        curr.add(grid[ki][kj])
 
                A = sorted(list(curr))
                if len(A) == 1:
                    ans[i][j] = 0
                else:
                    ans[i][j] = min(abs(a - b) for a, b in zip(A, A[1:]))
                    
        return ans