commit c7d3cce24ad8f1e0a7164a6ce27cb9fa83bae856
parent 8d924ee213a626f679fcb2e06a9b479b17d32f0b
Author: Jack Sangdahl <jack@pngu.org>
Date: Fri, 20 Mar 2026 08:45:10 -0600
3567. minimum absolute difference in sliding submatrix
Diffstat:
2 files changed, 162 insertions(+), 0 deletions(-)
diff --git a/min_abs_diff_sliding_submat.c b/min_abs_diff_sliding_submat.c
@@ -0,0 +1,108 @@
+// 3567. Minimum Absolute Difference in Sliding Submatrix
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' integer matrix 'grid' and an integer 'k'. for every
+ * two 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'.
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); }
+
+int compute_diff(int *arr, int n) {
+ if (n < 2)
+ return 0;
+ int min_diff = INT_MAX;
+ for (int i = 0; i < n - 1; i++) {
+ int diff = arr[i + 1] - arr[i];
+ if (diff > 0 && diff < min_diff)
+ min_diff = diff;
+ }
+ return min_diff == INT_MAX ? 0 : min_diff;
+}
+
+int **minAbsDiff(int **grid, int gridSize, int *gridColSize, int k,
+ int *returnSize, int **returnColumnSizes) {
+ int m = gridSize, n = gridColSize[0];
+ int rm = m - k + 1, rn = n - k + 1;
+ int **ans = (int **)malloc(rm * sizeof(int *));
+ *returnColumnSizes = (int *)malloc(rm * sizeof(int));
+ for (int i = 0; i < rm; i++) {
+ ans[i] = (int *)malloc(rn * sizeof(int));
+ (*returnColumnSizes)[i] = rn;
+ }
+ int *dp = (int *)malloc(k * k * sizeof(int));
+ for (int r = 0; r < rm; r++)
+ for (int c = 0; c < rn; c++) {
+ int idx = 0;
+ for (int i = 0; i < k; i++)
+ for (int j = 0; j < k; j++)
+ dp[idx++] = grid[r + i][c + j];
+ qsort(dp, k * k, sizeof(int), cmp);
+ ans[r][c] = compute_diff(dp, k * k);
+ }
+ free(dp);
+ *returnSize = rm;
+ return ans;
+}
+
+int main() {
+ int g1i[2][2] = {{1, 8}, {3, -2}}, rs1, *rcs1;
+ int g2i[1][2] = {{3, -1}}, rs2, *rcs2;
+ int g3i[2][3] = {{1, -2, 3}, {2, 3, 5}}, rs3, *rcs3;
+ int r1[1][1] = {{2}}, r2[1][2] = {{0, 0}}, r3[1][2] = {{1, 2}};
+ struct two_d_arr *g1 =
+ two_d_arr_init(ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i);
+ struct two_d_arr *g2 =
+ two_d_arr_init(ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i);
+ struct two_d_arr *g3 =
+ two_d_arr_init(ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i);
+ int **mad1 = minAbsDiff(g1->arr, g1->row_size, g1->col_size, 2, &rs1, &rcs1);
+ int **mad2 = minAbsDiff(g2->arr, g2->row_size, g2->col_size, 1, &rs2, &rcs2);
+ int **mad3 = minAbsDiff(g3->arr, g3->row_size, g3->col_size, 2, &rs3, &rcs3);
+ for (int i = 0; i < rs1; i++) {
+ for (int j = 0; j < rcs1[i]; j++) {
+ printf("%d ", mad1[i][j]);
+ assert(mad1[i][j] == r1[i][j]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs2; i++) {
+ for (int j = 0; j < rcs2[i]; j++) {
+ printf("%d ", mad2[i][j]);
+ assert(mad2[i][j] == r2[i][j]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs3; i++) {
+ for (int j = 0; j < rcs3[i]; j++) {
+ printf("%d ", mad3[i][j]);
+ assert(mad3[i][j] == r3[i][j]);
+ }
+ printf("\n");
+ }
+ printf("\n");
+ for (int i = 0; i < rs1; i++)
+ free(mad1[i]);
+ free(mad1);
+ for (int i = 0; i < rs2; i++)
+ free(mad2[i]);
+ free(mad2);
+ for (int i = 0; i < rs3; i++)
+ free(mad3[i]);
+ free(mad3);
+ free(rcs1);
+ free(rcs2);
+ free(rcs3);
+ two_d_arr_free(g1);
+ two_d_arr_free(g2);
+ two_d_arr_free(g3);
+}
diff --git a/min_abs_diff_sliding_submat.py b/min_abs_diff_sliding_submat.py
@@ -0,0 +1,54 @@
+# 3567. Minimum Absolute Difference in Sliding Submatrix
+from bisect import bisect_left, insort
+from typing import List
+
+"""
+you are given an 'm x n' integer matrix 'grid' and an integer 'k'. for every
+two 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'.
+"""
+
+
+class Solution:
+ def compute_diff(self, dp):
+ if len(dp) < 2:
+ return 0
+ min_diff = float("inf")
+ for i in range(len(dp) - 1):
+ diff = dp[i + 1] - dp[i]
+ if diff > 0 and diff < min_diff:
+ min_diff = diff
+ return min_diff if min_diff != float("inf") else 0
+
+ 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 r in range(m - k + 1):
+ dp = []
+ for i in range(k):
+ for j in range(k):
+ insort(dp, grid[r + i][j])
+ ans[r][0] = self.compute_diff(dp)
+ for c in range(1, n - k + 1):
+ for i in range(k):
+ remove = grid[r + i][c - 1]
+ idx = bisect_left(dp, remove)
+ dp.pop(idx)
+ for i in range(k):
+ add = grid[r + i][c + k - 1]
+ insort(dp, add)
+ ans[r][c] = self.compute_diff(dp)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minAbsDiff(grid=[[1, 8], [3, -2]], k=2))
+ print(obj.minAbsDiff(grid=[[3, -1]], k=1))
+ print(obj.minAbsDiff(grid=[[1, -2, 3], [2, 3, 5]], k=2))
