Welcome to Subscribe On Youtube

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 1: Enumeration

We can enumerate all possible $k \times k$ submatrices by their top-left coordinates $(i, j)$. For each submatrix, we extract all its elements into a list $\textit{nums}$. Then, we sort $\textit{nums}$ and compute the absolute differences between adjacent distinct elements to find the minimum absolute difference. Finally, we store the result in a 2D array.

The time complexity is $O((m - k + 1) \times (n - k + 1) \times k^2 \log(k))$, where $m$ and $n$ are the number of rows and columns of the matrix, and $k$ is the size of the submatrix. The space complexity is $O(k^2)$, used to store the elements of each submatrix.

  • class Solution { public int[][] minAbsDiff(int[][] grid, int k) { int m = grid.length, n = grid[0].length; int[][] ans = new int[m - k + 1][n - k + 1]; for (int i = 0; i <= m - k; i++) { for (int j = 0; j <= n - k; j++) { List<Integer> nums = new ArrayList<>(); for (int x = i; x < i + k; x++) { for (int y = j; y < j + k; y++) { nums.add(grid[x][y]); } } Collections.sort(nums); int d = Integer.MAX_VALUE; for (int t = 1; t < nums.size(); t++) { int a = nums.get(t - 1); int b = nums.get(t); if (a != b) { d = Math.min(d, Math.abs(a - b)); } } ans[i][j] = (d == Integer.MAX_VALUE) ? 0 : d; } } return ans; } } 
  • class Solution { public: vector<vector<int>> minAbsDiff(vector<vector<int>>& grid, int k) { int m = grid.size(), n = grid[0].size(); vector<vector<int>> ans(m - k + 1, vector<int>(n - k + 1, 0)); for (int i = 0; i <= m - k; ++i) { for (int j = 0; j <= n - k; ++j) { vector<int> nums; for (int x = i; x < i + k; ++x) { for (int y = j; y < j + k; ++y) { nums.push_back(grid[x][y]); } } sort(nums.begin(), nums.end()); int d = INT_MAX; for (int t = 1; t < nums.size(); ++t) { if (nums[t] != nums[t - 1]) { d = min(d, abs(nums[t] - nums[t - 1])); } } ans[i][j] = (d == INT_MAX) ? 0 : d; } } return ans; } }; 
  • class Solution: def minAbsDiff(self, grid: List[List[int]], k: int) -> List[List[int]]: m, n = len(grid), len(grid[0]) ans = [[0] * (n - k + 1) for _ in range(m - k + 1)] for i in range(m - k + 1): for j in range(n - k + 1): nums = [] for x in range(i, i + k): for y in range(j, j + k): nums.append(grid[x][y]) nums.sort() d = min((abs(a - b) for a, b in pairwise(nums) if a != b), default=0) ans[i][j] = d return ans 
  • func minAbsDiff(grid [][]int, k int) [][]int { m, n := len(grid), len(grid[0]) ans := make([][]int, m-k+1) for i := range ans { ans[i] = make([]int, n-k+1) } for i := 0; i <= m-k; i++ { for j := 0; j <= n-k; j++ { var nums []int for x := i; x < i+k; x++ { for y := j; y < j+k; y++ { nums = append(nums, grid[x][y]) } } sort.Ints(nums) d := math.MaxInt for t := 1; t < len(nums); t++ { if nums[t] != nums[t-1] { diff := abs(nums[t] - nums[t-1]) if diff < d { d = diff } } } if d != math.MaxInt { ans[i][j] = d } } } return ans } func abs(x int) int { if x < 0 { return -x } return x } 
  • function minAbsDiff(grid: number[][], k: number): number[][] { const m = grid.length; const n = grid[0].length; const ans: number[][] = Array.from({ length: m - k + 1 }, () => Array(n - k + 1).fill(0)); for (let i = 0; i <= m - k; i++) { for (let j = 0; j <= n - k; j++) { const nums: number[] = []; for (let x = i; x < i + k; x++) { for (let y = j; y < j + k; y++) { nums.push(grid[x][y]); } } nums.sort((a, b) => a - b); let d = Number.MAX_SAFE_INTEGER; for (let t = 1; t < nums.length; t++) { if (nums[t] !== nums[t - 1]) { d = Math.min(d, Math.abs(nums[t] - nums[t - 1])); } } ans[i][j] = d === Number.MAX_SAFE_INTEGER ? 0 : d; } } return ans; }

All Problems

All Solutions