3567. Minimum Absolute Difference in Sliding Submatrix

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:
  • 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.
  • 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.
• Thus, the answer is [[1, 2]].

 

Constraints:

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

 

Solutions

Solution: Simulation

• Time complexity: O((m-k)*(n-k)*k²)
• Space complexity: O((m-k)*(n-k))

 

JavaScript

/**
 * @param {number[][]} grid
 * @param {number} k
 * @return {number[][]}
 */
const minAbsDiff = function (grid, k) {
  const m = grid.length;
  const n = grid[0].length;
  const result = Array.from({ length: m - k + 1 }, () => {
    return new Array(n - k + 1).fill(0);
  });

  const getMinAbsoluteDiff = (startRow, startCol) => {
    const valueSet = new Set();

    for (let row = 0; row < k; row++) {
      for (let col = 0; col < k; col++) {
        const value = grid[startRow + row][startCol + col];

        valueSet.add(value);
      }
    }

    if (valueSet.size === 1) return 0;

    const values = [...valueSet].toSorted((a, b) => a - b);
    let minDiff = Number.MAX_SAFE_INTEGER;

    for (let index = 1; index < values.length; index++) {
      const diff = Math.abs(values[index] - values[index - 1]);

      minDiff = Math.min(diff, minDiff);
    }

    return minDiff;
  };

  for (let row = 0; row < m - k + 1; row++) {
    for (let col = 0; col < n - k + 1; col++) {
      result[row][col] = getMinAbsoluteDiff(row, col);
    }
  }

  return result;
};