Show problems as
Classic problem #3567MediumArraySortingMatrix

Minimum Absolute Difference in Sliding Submatrix

Real-world version: Closest Distinct Pair in Each Window
Tracked in this browser only
Read Minimum Absolute Difference in Sliding Submatrix on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A board of readings is given as grid.

For every k by k window of the board, report the smallest positive difference between two readings inside it, or 0 when every reading in that window is the same.

Return those figures as a board of their own, laid out so that the entry at row i and column j answers the window whose top-left corner sits at row i, column j.

Examples

Example 1

Input
grid = [[14, 3, 27], [9, 21, 6], [17, 8, 31]], k = 2
Output
[[5, 3], [1, 2]]

The top-left window holds 14, 3, 9 and 21; in order those are 3, 9, 14 and 21, and the closest neighbours are 9 and 14, five apart. The other three windows are read the same way.

Example 2

Input
grid = [[7, 7], [7, 7]], k = 2
Output
[[0]]

The single window holds one distinct reading, so there is no pair to measure.

Example 3

Input
grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 1
Output
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]

Every window is a single cell, so none of them holds a pair.

Constraints

  • 1 <= grid.length <= 30
  • 1 <= grid[i].length <= 30
  • Every row of grid has the same length
  • -10^5 <= grid[i][j] <= 10^5
  • 1 <= k <= min(grid.length, grid[i].length)

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def min_abs_diff(grid: list[list[int]], k: int) -> list[list[int]]:
Java
public int[][] minAbsDiff(int[][] grid, int k)

More on the same topics