LeetCode Problem 3567

Difficulty: 🟡 Medium
Topics: Array, Sorting, Matrix

Solution

Problem Understanding

The problem requires computing a specific statistic for every contiguous k x k submatrix of a given m x n integer matrix grid. For each submatrix, we must find the minimum absolute difference between any two distinct elements. The final result is a 2D array ans of size (m - k + 1) x (n - k + 1) where each entry corresponds to a top-left corner of a submatrix.

In simpler terms, you slide a k x k window over the matrix, and for each window, you identify all distinct numbers, compute all pairwise differences, and return the smallest. If all numbers in the submatrix are identical, the minimum difference is 0.

The constraints tell us the matrix is relatively small (m, n ≤ 30) and element values range between -10^5 and 10^5. The k parameter can vary between 1 and the smaller dimension of the matrix. Edge cases include single-element submatrices (k = 1) and submatrices where all elements are the same, which require careful handling to avoid errors in computing differences.

Approaches

Brute Force Approach

A straightforward solution is to iterate over all possible k x k submatrices. For each submatrix, extract all elements, deduplicate them, sort the list, and compute the minimum difference between consecutive elements. Sorting is necessary because the minimum difference will always occur between two consecutive numbers in a sorted list. This method guarantees correctness but is inefficient because we are repeatedly processing overlapping submatrices, which can be costly when k is large.

Optimal Approach

The key observation for optimization is that the submatrix size is small (k ≤ 30) and the total number of submatrices is bounded by (m - k + 1) * (n - k + 1) ≤ 900. This allows a simple brute-force-like solution to work within constraints, but we can avoid sorting by using a SortedList or similar data structure that maintains order while inserting elements, allowing us to calculate minimum differences efficiently. This reduces the repeated sorting overhead and simplifies finding consecutive differences.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m-k+1)*(n-k+1)_k^2_log(k^2))	O(k^2)	Extract submatrix, sort, compute min difference
Optimal	O((m-k+1)*(n-k+1)*k^2)	O(k^2)	Use a sorted data structure to maintain elements for min difference computation

Algorithm Walkthrough

1. Initialize an empty 2D array ans of size (m - k + 1) x (n - k + 1) to store the results.
2. Iterate over all valid top-left coordinates (i, j) for k x k submatrices.
3. For each submatrix, extract all k^2 elements into a list.
4. Convert the list to a set to remove duplicates, since we only care about distinct values.
5. If the submatrix has fewer than 2 distinct elements, set the corresponding ans[i][j] to 0.
6. Otherwise, sort the distinct elements to easily find consecutive differences.
7. Iterate through the sorted list and compute the absolute differences between consecutive elements.
8. Set ans[i][j] to the minimum of these differences.
9. Return ans after processing all submatrices.

Why it works: Sorting guarantees that the smallest absolute difference between distinct values is always between two consecutive elements. Using a set ensures duplicates do not affect the calculation. Iterating through all valid positions covers every submatrix. The problem asks us to analyze every possible contiguous k x k submatrix inside a given m x n integer grid and compute a specific statistic for each of those submatrices. For each such window, we must find the minimum absolute difference between any two distinct values inside that window, and place that result into a corresponding position in the output matrix.

In simpler terms, we slide a square window of size k x k over the grid. For each position of the window, we look at all values inside it, and we want the smallest difference between any two different numbers in that region. If all values in the window are identical, then the answer is 0.

The output is a reduced matrix of size (m - k + 1) x (n - k + 1), where each cell corresponds to the top-left corner of a valid k x k submatrix in the original grid.

The constraints are small, with m, n <= 30, meaning at most 900 cells total, and at most 900 submatrices. Each submatrix contains at most k^2 <= 900 elements. This strongly suggests that an O(k^2 log k^2) per-window solution is acceptable.

Important edge cases include when k = 1, where every submatrix contains only one element and the answer is always 0, and when all values in a submatrix are identical, which also forces the answer to be 0. Negative values are also allowed, so sorting or absolute difference logic must handle full integer ranges correctly.

Approaches

The brute-force idea is straightforward. For each k x k submatrix, we extract all values into a list, sort it, and then compute the minimum difference between consecutive elements in the sorted order. This works because the smallest absolute difference between any two numbers must occur between adjacent values in sorted order. However, repeating this extraction and sorting for every window can still be expensive, though it remains feasible under constraints.

The key observation is that once values are sorted, we do not need to compare all pairs. Only adjacent differences matter. This reduces the problem inside each window from quadratic comparisons to linear scanning after sorting.

A more advanced optimization would maintain a balanced structure while sliding the window, but given the small constraints, recomputing per window is sufficiently optimal and simpler to implement correctly.

Complexity Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m-k+1)(n-k+1) · k² log k²)	O(k²)	Extract and sort each window independently
Optimal (sort per window + scan)	O((m-k+1)(n-k+1) · k² log k)	O(k²)	Sort each window and compute adjacent differences

Algorithm Walkthrough

The optimal approach processes each valid top-left corner of a k x k submatrix systematically.

1. We iterate over every possible starting row i from 0 to m - k, and every starting column j from 0 to n - k. Each (i, j) defines a unique k x k window.
2. For each window, we collect all k^2 values into a temporary list. This step is necessary because we need a flat structure to sort and compare values efficiently.
3. We sort the collected values in non-decreasing order. Sorting ensures that any pair with minimal absolute difference must appear adjacent in this ordering.
4. We initialize a variable best with infinity. We then scan through the sorted list from left to right, computing differences between consecutive elements.
5. If we find a difference of 0, we immediately return 0 for that window because this is the smallest possible value.
6. Otherwise, we keep tracking the minimum difference found during the scan.
7. We store this result in the output matrix at position (i, j).

Why it works

The correctness relies on a standard ordering property: for any set of numbers, the minimum absolute difference must occur between two consecutive elements in sorted order. Any non-adjacent pair must have at least one intermediate value, which cannot produce a smaller gap than its adjacent neighbors. This guarantees that scanning only adjacent pairs after sorting is sufficient to find the correct answer for each submatrix.

Python Solution

from typing import List

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):
                elements = []
                for x in range(i, i + k):
                    for y in range(j, j + k):
                        elements.append(grid[x][y])
                
                distinct_elements = sorted(set(elements))
                
                if len(distinct_elements) < 2:
                    ans[i][j] = 0
                else:
                    min_diff = float('inf')
                    for a, b in zip(distinct_elements, distinct_elements[1:]):
                        min_diff = min(min_diff, b - a)
                    ans[i][j] = min_diff
        
        return ans

Implementation Explanation: The outer loops iterate over the starting points of each k x k submatrix. Inner loops collect elements. Converting to a set removes duplicates, and sorting ensures we can compute consecutive differences efficiently. The zip function pairs consecutive elements, and we track the minimum difference. The result array is filled progressively. res_rows = m - k + 1 res_cols = n - k + 1 ans = [[0] * res_cols for _ in range(res_rows)]

    for i in range(res_rows):
        for j in range(res_cols):
            values = []

            for r in range(i, i + k):
                for c in range(j, j + k):
                    values.append(grid[r][c])

            values.sort()

            best = float("inf")
            for t in range(1, len(values)):
                diff = values[t] - values[t - 1]
                if diff == 0:
                    best = 0
                    break
                if diff < best:
                    best = diff

            ans[i][j] = best

    return ans

The implementation directly follows the algorithm structure. We iterate over all valid windows, flatten each `k x k` region into a list, sort it, and then compute adjacent differences. The early exit on zero improves efficiency in duplicate-heavy cases. The result matrix is filled incrementally.

## Go Solution

```go
import (
    "math"
    "sort"
)

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++ {
            elementsMap := make(map[int]struct{})
            for x := i; x < i+k; x++ {
                for y := j; y < j+k; y++ {
                    elementsMap[grid[x][y]] = struct{}{}
                }
            }

            distinctElements := make([]int, 0, len(elementsMap))
            for val := range elementsMap {
                distinctElements = append(distinctElements, val)
            }

            if len(distinctElements) < 2 {
                ans[i][j] = 0
            } else {
                sort.Ints(distinctElements)
                minDiff := math.MaxInt32
                for idx := 1; idx < len(distinctElements); idx++ {
                    diff := distinctElements[idx] - distinctElements[idx-1]
                    if diff < minDiff {
                        minDiff = diff
                    }
                }
                ans[i][j] = minDiff
            }
        }
    }

    return ans
}

Go-specific Notes: We use a map to deduplicate elements since Go does not have a built-in set. Sorting and min difference calculation is the same conceptually. Slices are dynamically allocated for results and intermediate storage.

Worked Examples

Example 1: grid = [[1,8],[3,-2]], k = 2

Extract submatrix [[1,8],[3,-2]] → distinct [1,8,3,-2] → sort [-2,1,3,8] → differences [3,2,5] → min is 2 → result [[2]].

Example 2: grid = [[3,-1]], k = 1

Each submatrix has a single element → distinct length < 2 → result [[0,0]].

Example 3: grid = [[1,-2,3],[2,3,5]], k = 2

Submatrix (0,0) [[1,-2],[2,3]] → distinct [-2,1,2,3] → min diff 1.

Submatrix (0,1) [[-2,3],[3,5]] → distinct [-2,3,5] → min diff 2.

Final result [[1,2]]. func minAbsDiff(grid [][]int, k int) [][]int { m := len(grid) n := len(grid[0])

resRows := m - k + 1
resCols := n - k + 1

ans := make([][]int, resRows)
for i := range ans {
	ans[i] = make([]int, resCols)
}

values := make([]int, 0, k*k)

for i := 0; i < resRows; i++ {
	for j := 0; j < resCols; j++ {
		values = values[:0]

		for r := i; r < i+k; r++ {
			for c := j; c < j+k; c++ {
				values = append(values, grid[r][c])
			}
		}

		quickSort(values)

		best := int(^uint(0) >> 1)

		for t := 1; t < len(values); t++ {
			diff := values[t] - values[t-1]
			if diff == 0 {
				best = 0
				break
			}
			if diff < best {
				best = diff
			}
		}

		ans[i][j] = best
	}
}

return ans

}

func quickSort(arr []int) { if len(arr) <= 1 { return } pivot := arr[len(arr)/2] left := 0 right := len(arr) - 1

i, j := 0, right
for i <= j {
	for arr[i] < pivot {
		i++
	}
	for arr[j] > pivot {
		j--
	}
	if i <= j {
		arr[i], arr[j] = arr[j], arr[i]
		i++
		j--
	}
}

if j > 0 {
	quickSort(arr[:j+1])
}
if i < len(arr) {
	quickSort(arr[i:])
}

}

In Go, we explicitly reuse a preallocated slice `values` to avoid repeated allocations. The sorting is implemented via a custom quicksort to remain self-contained, though in production code `sort.Ints` would be preferred for correctness and simplicity. Integer initialization uses `int(^uint(0) >> 1)` to represent infinity.

## Worked Examples

### Example 1

Input grid:

`[[1,8],[3,-2]], k = 2`

For the only window `(0,0)`, we collect `[1, 8, 3, -2]`.

After sorting: `[-2, 1, 3, 8]`

Differences:

- `1 - (-2) = 3`
- `3 - 1 = 2`
- `8 - 3 = 5`

Minimum is `2`, so output is `[[2]]`.

### Example 2

Input grid:

`[[3,-1]], k = 1`

Each window has a single element.

For `(0,0)`: `[3]` → no pair, so `0`

For `(0,1)`: `[-1]` → no pair, so `0`

Output is `[[0, 0]]`.

### Example 3

Input grid:

`[[1,-2,3],[2,3,5]], k = 2`

Window `(0,0)`:

Values: `[1, -2, 2, 3]`

Sorted: `[-2, 1, 2, 3]`

Differences: `3, 1, 1` → result `1`

Window `(0,1)`:

Values: `[-2, 3, 3, 5]`

Sorted: `[-2, 3, 3, 5]`

Differences: `5, 0, 2` → result `0`

Note that duplicates produce a zero minimum difference, which is immediately optimal.

Final output: `[[1, 0]]`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O((m-k+1)*(n-k+1)_k^2_log(k^2)) | For each submatrix, deduplicate and sort `k^2` elements |
| Space | O(k^2) | Storage for submatrix elements and distinct elements set |

Although the worst-case complexity involves sorting, `k` is at most 30, making this feasible within the constraints.
| Time | O((m-k+1)(n-k+1) · k² log k) | Each window collects k² elements and sorts them |
| Space | O(k²) | Temporary storage for values in one window |

The time complexity is acceptable because both dimensions are bounded by 30, leading to at most 900 windows, and each window processes at most 900 elements.

## Test Cases

Provided examples

assert Solution().minAbsDiff([[1,8],[3,-2]], 2) == [[2]] # single 2x2 submatrix assert Solution().minAbsDiff([[3,-1]], 1) == [[0,0]] # single-element submatrices assert Solution().minAbsDiff([[1,-2,3],[2,3,5]], 2) == [[1,2]] # multiple submatrices

Edge cases

assert Solution().minAbsDiff([[5]], 1) == [[0]] # 1x1 matrix assert Solution().minAbsDiff([[1,1,1],[1,1,1],[1,1,1]], 2) == [[0,0],[0,0]] # all identical assert Solution().minAbsDiff([[1,2,3],[4,5,6],[7,8,9]], 3) == [[1]] # full matrix assert Solution().minAbsDiff([[1,8],[3,-2]], 2) == [[2]] # basic 2x2 case assert Solution().minAbsDiff([[3,-1]], 1) == [[0,0]] # k=1 edge case assert Solution().minAbsDiff([[1,-2,3],[2,3,5]], 2) == [[1,0]] # multiple windows assert Solution().minAbsDiff([[5]], 1) == [[0]] # single cell grid assert Solution().minAbsDiff([[1,1],[1,1]], 2) == [[0]] # all duplicates assert Solution().minAbsDiff([[1,100,1000],[2,3,4]], 2) == [[1,1]] # varied values

| Test | Why |
| --- | --- |
| Single 2x2 submatrix | Validates calculation of min absolute difference |
| Single-element submatrices | Tests handling k=1 |
| 2x2 matrix | verifies full-window computation |
| k=1 case | ensures single element windows return 0 |
| multiple windows | validates sliding correctness |
| single cell | smallest possible input |
| all duplicates | checks zero-difference propagation |
| mixed values | ensures correct min adjacent diff logic |

## Edge Cases

One important edge case is when `k = 1`. In this situation, every submatrix contains exactly one element, so there are no pairs to compare. A naive implementation might attempt to compute differences on an empty or singleton list, but the correct behavior is always to return `0` for every position.

Another edge case is when all values in a submatrix are identical. After sorting, all elements are equal, so every adjacent difference is `0`. The implementation correctly short-circuits when a zero difference is found, ensuring optimal performance and correctness.

A third edge case involves negative numbers mixed with positive numbers. Since absolute difference is independent of sign ordering, sorting still correctly aligns values so that the minimum difference is found between adjacent elements. The algorithm does not treat negatives specially, which avoids subtle bugs in manual absolute difference comparisons.