# Minimum Absolute Difference in Sliding Submatrix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-absolute-difference-in-sliding-submatrix)
Canonical: https://scaleengineer.com/dsa/problems/minimum-absolute-difference-in-sliding-submatrix
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Matrix
---
## Problem
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
## Brute Force Iteration over Submatrices
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## 2D Sliding Window with Self-Balancing BST
This approach improves upon the brute-force method by using a 2D sliding window. Instead of re-calculating from scratch for each submatrix, we efficiently update the state as the window slides. We maintain the elements of the current `k x k` window in data structures that allow for fast updates and querying of the minimum difference. A pair of self-balancing binary search trees (implemented as `TreeMap` in Java) is ideal for this purpose.
**Time:** O(n * (m + k) * k * log k)
For each of the `n-k+1` columns, we initialize the window in `O(k^2 * log k)`. Then we perform `m-k` vertical slides, each taking `O(k * log k)` time (k updates, each `O(log k)`). The total time is `O(n * (k^2 * log k + m * k * log k))`, which simplifies to `O(n * (m+k) * k * log k)`. · **Space:** O(k^2)
The `TreeMap`s store at most `k^2` distinct elements and `k^2-1` distinct differences.
**Pros:** Much more efficient than the brute-force approach by avoiding redundant computations.; Effectively reuses information from overlapping submatrices.
**Cons:** Significantly more complex to implement correctly compared to the brute-force approach.; Requires careful management of the helper data structures and the sliding logic.
### Explanation
We use two `TreeMap`s to keep track of the window's state. The `elements` map stores the frequency of each number, and the `diffs` map stores the frequency of differences between adjacent unique numbers. The minimum difference is always the smallest key in the `diffs` map.

The sliding process can be performed column by column. For each column `j` of the result matrix, we first build the data structures for the submatrix at `(0, j)`. Then, we slide this window downwards one row at a time. Each downward slide involves removing the `k` elements from the row that is leaving the window and adding the `k` elements from the row that is entering the window. The `add` and `remove` helper functions handle the logic of updating the `elements` and `diffs` maps in `O(log k)` time per element.

```java
class Solution {
    private TreeMap<Integer, Integer> elements;
    private TreeMap<Integer, Integer> diffs;

    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 j = 0; j <= n - k; j++) {
            elements = new TreeMap<>();
            diffs = new TreeMap<>();
            // Initialize for the first window in this column strip (i=0)
            for (int r = 0; r < k; r++) {
                for (int c = j; c < j + k; c++) {
                    add(grid[r][c]);
                }
            }
            ans[0][j] = diffs.isEmpty() ? 0 : diffs.firstKey();

            // Slide down for the rest of the column
            for (int i = 1; i <= m - k; i++) {
                // Remove top row of the previous window
                for (int c = j; c < j + k; c++) {
                    remove(grid[i - 1][c]);
                }
                // Add bottom row of the new window
                for (int c = j; c < j + k; c++) {
                    add(grid[i + k - 1][c]);
                }
                ans[i][j] = diffs.isEmpty() ? 0 : diffs.firstKey();
            }
        }
        return ans;
    }

    private void add(int num) {
        elements.put(num, elements.getOrDefault(num, 0) + 1);
        if (elements.get(num) == 1) { // New distinct element
            Integer prev = elements.lowerKey(num);
            Integer next = elements.higherKey(num);
            if (prev != null && next != null) {
                removeDiff(next - prev);
            }
            if (prev != null) {
                addDiff(num - prev);
            }
            if (next != null) {
                addDiff(next - num);
            }
        }
    }

    private void remove(int num) {
        if (elements.get(num) == 1) { // This distinct element will be removed
            Integer prev = elements.lowerKey(num);
            Integer next = elements.higherKey(num);
            if (prev != null) {
                removeDiff(num - prev);
            }
            if (next != null) {
                removeDiff(next - num);
            }
            if (prev != null && next != null) {
                addDiff(next - prev);
            }
        }
        elements.put(num, elements.get(num) - 1);
        if (elements.get(num) == 0) {
            elements.remove(num);
        }
    }

    private void addDiff(int diff) {
        diffs.put(diff, diffs.getOrDefault(diff, 0) + 1);
    }

    private void removeDiff(int diff) {
        diffs.put(diff, diffs.get(diff) - 1);
        if (diffs.get(diff) == 0) {
            diffs.remove(diff);
        }
    }
}
```
### Algorithm
- The core idea is to use a 2D sliding window and maintain the elements within the window in efficient data structures.
- We use two `TreeMap`s:
  1. `elements`: A `TreeMap<Integer, Integer>` to store the frequency of each number in the current `k x k` window. This keeps the distinct elements sorted by value.
  2. `diffs`: A `TreeMap<Integer, Integer>` to store the frequency of differences between adjacent distinct elements from the `elements` map. The smallest key in this map is the minimum absolute difference for the current window.
- We define helper methods `add(num)` and `remove(num)` to update these maps. When an element's count changes from 0 to 1 or 1 to 0, we update the `diffs` map by removing old differences and adding new ones involving the element's neighbors.
- The main algorithm slides a `k x k` window. A simple sliding strategy is to process the grid column by column of submatrices:
  - For each submatrix column `j` from `0` to `n - k`:
    - **Initialize**: Create new `elements` and `diffs` maps. Populate them for the first submatrix in that column, `(0, j)`. This takes `O(k^2 * log k)`. Store the result `ans[0][j]`. The result is `diffs.firstKey()` or 0 if `diffs` is empty.
    - **Slide Vertically**: For `i` from `1` to `m - k`, slide the window down by one row. This involves removing the `k` elements of the top row (`i-1`) of the old window and adding the `k` elements of the bottom row (`i+k-1`) of the new window. Each slide takes `O(k * log k)`. After each slide, update `ans[i][j]`.
- Return the `ans` matrix.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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

```