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 ksubmatrix:[[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 ksubmatrix 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 × ksubmatrix:- Starting at
(0, 0):[[1, -2], [2, 3]].- Distinct values in the submatrix are
[1, -2, 2, 3]. - The minimum absolute difference in the submatrix is
|1 - 2| = 1.
- Distinct values in the submatrix are
- Starting at
(0, 1):[[-2, 3], [3, 5]].- Distinct values in the submatrix are
[-2, 3, 5]. - The minimum absolute difference in the submatrix is
|3 - 5| = 2.
- Distinct values in the submatrix are
- Starting at
- Thus, the answer is
[[1, 2]].
Constraints:
1 <= m == grid.length <= 301 <= n == grid[i].length <= 30-105 <= grid[i][j] <= 1051 <= k <= min(m, n)
Solutions
This is a more memory-efficient variant that avoids storing Sets in the DP array; instead, it creates a temporary Set for each k×k subgrid, immediately processes it to find the minimum difference, and stores only the final result in the DP cell. It uses a continue statement to skip processing when a subgrid has only one unique element, leaving that cell at its initialized value of 0.
/**
* @param {number[][]} grid
* @param {number} k
* @return {number[][]}
*/
var minAbsDiff = function(grid, k) {
const m = grid.length;
const n = grid[0].length;
const dp = Array.from({ length: m - k + 1 }, () => Array(n - k + 1).fill(0));
for (let row = 0; row < m - k + 1; row++) {
for (let col = 0; col < n - k + 1; col++) {
const set = new Set();
for (let r = 0; r < k; r++) {
for (let c = 0; c < k; c++) {
set.add(grid[row + r][col + c]);
}
}
const arr = [...set];
if (arr.length <= 1) {
continue;
}
arr.sort((a, b) => a - b);
let minDiff = Infinity;
for (let pos = 1; pos < arr.length; pos++) {
minDiff = Math.min(minDiff, Math.abs(arr[pos] - arr[pos - 1]));
}
dp[row][col] = minDiff;
}
}
return dp;
};