Scale Engineer

Minimum Absolute Difference in Sliding Submatrix

Med
#3176Time: O(m * n * k^2 * log(k^2)) or O(m * n * k^2 * log k) There are `(m - k + 1) * (n - k + 1)` submatrices, which is O(m*n). For each submatrix, we collect `k^2` elements and sort them, which takes `O(k^2 * log(k^2))`. The final pass to find the minimum difference takes `O(k^2)`. Thus, the total time complexity is dominated by the sorting step for each submatrix.Space: O(k^2) This is for the temporary list used to store the elements of each submatrix. The space for the output array is not included in this analysis.
Algorithms
Sorting
Data structures
ArrayMatrix

Prompt

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)

Approaches

2 approaches with complexity analysis and trade-offs.

The brute-force approach is the most straightforward way to solve the problem. It involves iterating through every possible k x k submatrix within the given grid. For each submatrix, we extract all its k*k elements, sort them, and then find the minimum absolute difference between any two adjacent elements in the sorted list. This minimum difference is the answer for that specific submatrix.

Algorithm

  • Create a result matrix ans of size (m - k + 1) x (n - k + 1).
  • Iterate through each possible top-left corner (i, j) of a k x k submatrix, where i ranges from 0 to m - k and j ranges from 0 to n - k.
  • For each submatrix:
    • Create a temporary list to store all k * k elements from the submatrix grid[i...i+k-1][j...j+k-1].
    • Sort this list of elements in ascending order.
    • Initialize a variable min_diff to a very large value.
    • Iterate through the sorted list from the second element. For each element, calculate the difference with its preceding element and update min_diff if this difference is smaller.
    • If min_diff remains at its initial large value (which happens if there's one or zero distinct elements, e.g., k=1), the difference is 0. Otherwise, it's the calculated minimum difference.
    • Store this min_diff in ans[i][j].
  • Return the ans matrix.

Walkthrough

This method systematically checks every valid top-left coordinate (i, j) for a k x k submatrix. For each such submatrix, it performs the following steps:

  1. Extraction: All k*k elements are gathered from grid and placed into a temporary list.
  2. Sorting: The list is sorted to bring elements with the smallest differences next to each other. The minimum absolute difference in the submatrix will be the minimum difference between any two adjacent elements in this sorted list.
  3. Difference Calculation: A single pass through the sorted list is made to find the minimum difference between consecutive elements. If the submatrix contains fewer than two distinct values (e.g., for k=1 or if all elements are identical), the minimum difference is considered to be 0 as per the problem's examples.
  4. Storing Result: The calculated minimum difference is stored in the corresponding cell of the result matrix.
class Solution {    public int[][] minAbsDifference(int[][] grid, int k) {        int m = grid.length;        int 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> submatrixElements = new ArrayList<>();                for (int r = i; r < i + k; r++) {                    for (int c = j; c < j + k; c++) {                        submatrixElements.add(grid[r][c]);                    }                }                 Collections.sort(submatrixElements);                 int minDiff = Integer.MAX_VALUE;                for (int l = 1; l < submatrixElements.size(); l++) {                    minDiff = Math.min(minDiff, submatrixElements.get(l) - submatrixElements.get(l - 1));                }                                ans[i][j] = (minDiff == Integer.MAX_VALUE) ? 0 : minDiff;            }        }        return ans;    }}

Complexity

Time

O(m * n * k^2 * log(k^2)) or O(m * n * k^2 * log k) There are `(m - k + 1) * (n - k + 1)` submatrices, which is O(m*n). For each submatrix, we collect `k^2` elements and sort them, which takes `O(k^2 * log(k^2))`. The final pass to find the minimum difference takes `O(k^2)`. Thus, the total time complexity is dominated by the sorting step for each submatrix.

Space

O(k^2) This is for the temporary list used to store the elements of each submatrix. The space for the output array is not included in this analysis.

Trade-offs

Pros

  • Simple to understand and implement.

  • Correct and guaranteed to find the solution.

Cons

  • Highly inefficient due to redundant computations. It re-processes all k*k elements for each submatrix, even though adjacent submatrices have a large overlap.

  • The time complexity can be prohibitive for larger grids or window sizes, although it passes for the given constraints.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem