Skip to content

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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]);
                    }
                }
                ranges::sort(nums);
                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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
impl Solution {
    pub fn min_abs_diff(grid: Vec<Vec<i32>>, k: i32) -> Vec<Vec<i32>> {
        let m = grid.len();
        let n = grid[0].len();
        let k = k as usize;

        let mut ans = vec![vec![0; n - k + 1]; m - k + 1];

        for i in 0..=m - k {
            for j in 0..=n - k {
                let mut nums = Vec::with_capacity(k * k);
                for x in i..i + k {
                    for y in j..j + k {
                        nums.push(grid[x][y]);
                    }
                }

                nums.sort_unstable();

                let mut d = i32::MAX;
                for t in 1..nums.len() {
                    if nums[t] != nums[t - 1] {
                        d = d.min((nums[t] - nums[t - 1]).abs());
                    }
                }

                ans[i][j] = if d == i32::MAX { 0 } else { d };
            }
        }

        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public int[][] MinAbsDiff(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        int[][] ans = new int[m - k + 1][];
        for (int i = 0; i <= m - k; ++i) {
            ans[i] = new int[n - k + 1];
            for (int j = 0; j <= n - k; ++j) {
                List<int> nums = new List<int>(k * k);
                for (int x = i; x < i + k; ++x) {
                    for (int y = j; y < j + k; ++y) {
                        nums.Add(grid[x][y]);
                    }
                }

                nums.Sort();

                int d = int.MaxValue;
                for (int t = 1; t < nums.Count; ++t) {
                    if (nums[t] != nums[t - 1]) {
                        d = Math.Min(d, Math.Abs(nums[t] - nums[t - 1]));
                    }
                }

                ans[i][j] = d == int.MaxValue ? 0 : d;
            }
        }
        return ans;
    }
}

Comments