minimum-absolute-difference-in-sliding-submatrix

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

cangjie

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

You are given an <code>m x n</code> integer matrix <code>grid</code> and an integer <code>k</code>.

For every contiguous <code>k x k</code> submatrix of <code>grid</code>, compute the minimum absolute difference between any two distinct values within that submatrix.

Return a 2D array <code>ans</code> of size <code>(m - k + 1) x (n - k + 1)</code>, where <code>ans[i][j]</code> is the minimum absolute difference in the submatrix whose top-left corner is <code>(i, j)</code> in <code>grid</code>.

Note: If all elements in the submatrix have the same value, the answer will be 0.
A submatrix <code>(x1, y1, x2, y2)</code> is a matrix that is formed by choosing all cells <code>matrix[x][y]</code> where <code>x1 &lt;= x &lt;= x2</code> and <code>y1 &lt;= y &lt;= y2</code>.
&nbsp;
Example 1:

<div class="example-block">
Input: grid = [[1,8],[3,-2]], k = 2

Output: [[2]]

Explanation:

<ul>
	<li>There is only one possible <code>k x k</code> submatrix: <code>[[1, 8], [3, -2]]</code>.</li>
	<li>Distinct values in the submatrix are <code>[1, 8, 3, -2]</code>.</li>
	<li>The minimum absolute difference in the submatrix is <code>|1 - 3| = 2</code>. Thus, the answer is <code>[[2]]</code>.</li>
</ul>
</div>

Example 2:

<div class="example-block">
Input: grid = [[3,-1]], k = 1

Output: [[0,0]]

Explanation:

<ul>
	<li>Both <code>k x k</code> submatrix has only one distinct element.</li>
	<li>Thus, the answer is <code>[[0, 0]]</code>.</li>
</ul>
</div>

Example 3:

<div class="example-block">
Input: grid = [[1,-2,3],[2,3,5]], k = 2

Output: [[1,2]]

Explanation:

<ul>
	<li>There are two possible <code>k &times; k</code> submatrix:

	<ul>
		<li>Starting at <code>(0, 0)</code>: <code>[[1, -2], [2, 3]]</code>.

		<ul>
			<li>Distinct values in the submatrix are <code>[1, -2, 2, 3]</code>.</li>
			<li>The minimum absolute difference in the submatrix is <code>|1 - 2| = 1</code>.</li>
		</ul>
		</li>
		<li>Starting at <code>(0, 1)</code>: <code>[[-2, 3], [3, 5]]</code>.
		<ul>
			<li>Distinct values in the submatrix are <code>[-2, 3, 5]</code>.</li>
			<li>The minimum absolute difference in the submatrix is <code>|3 - 5| = 2</code>.</li>
		</ul>
		</li>
	</ul>
	</li>
	<li>Thus, the answer is <code>[[1, 2]]</code>.</li>
</ul>
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= m == grid.length &lt;= 30</code></li>
	<li><code>1 &lt;= n == grid[i].length &lt;= 30</code></li>
	<li><code>-105 &lt;= grid[i][j] &lt;= 105</code></li>
	<li><code>1 &lt;= k &lt;= min(m, n)</code></li>
</ul>

第 452 场周赛

weekly-contest-452

minAbsDiff

高级工程师

Minimum Absolute Difference in Sliding Submatrix

Array

Matrix

Sorting

给你一个 <code>m x n</code> 的整数矩阵 <code>grid</code> 和一个整数 <code>k</code>。

对于矩阵 <code>grid</code> 中的每个连续的 <code>k x k</code> 子矩阵，计算其中任意两个&nbsp;不同值 之间的&nbsp;最小绝对差&nbsp;。

返回一个大小为 <code>(m - k + 1) x (n - k + 1)</code> 的二维数组 <code>ans</code>，其中 <code>ans[i][j]</code> 表示以 <code>grid</code> 中坐标 <code>(i, j)</code> 为左上角的子矩阵的最小绝对差。

注意：如果子矩阵中的所有元素都相同，则答案为 0。

子矩阵 <code>(x1, y1, x2, y2)</code> 是一个由选择矩阵中所有满足 <code>x1 &lt;= x &lt;= x2</code> 且 <code>y1 &lt;= y &lt;= y2</code> 的单元格 <code>matrix[x][y]</code> 组成的矩阵。

&nbsp;

示例 1：

<div class="example-block">
输入： grid = [[1,8],[3,-2]], k = 2

输出： [[2]]

解释：

<ul>
	<li>只有一个可能的 <code>k x k</code> 子矩阵：<code>[[1, 8], [3, -2]]</code>。</li>
	<li>子矩阵中的不同值为 <code>[1, 8, 3, -2]</code>。</li>
	<li>子矩阵中的最小绝对差为 <code>|1 - 3| = 2</code>。因此，答案为 <code>[[2]]</code>。</li>
</ul>
</div>

示例 2：

<div class="example-block">
输入： grid = [[3,-1]], k = 1

输出： [[0,0]]

解释：

<ul>
	<li>每个 <code>k x k</code> 子矩阵中只有一个不同的元素。</li>
	<li>因此，答案为 <code>[[0, 0]]</code>。</li>
</ul>
</div>

示例 3：

<div class="example-block">
输入： grid = [[1,-2,3],[2,3,5]], k = 2

输出： [[1,2]]

解释：

<ul>
	<li>有两个可能的 <code>k × k</code> 子矩阵：

	<ul>
		<li>以 <code>(0, 0)</code> 为起点的子矩阵：<code>[[1, -2], [2, 3]]</code>。

		<ul>
			<li>子矩阵中的不同值为 <code>[1, -2, 2, 3]</code>。</li>
			<li>子矩阵中的最小绝对差为 <code>|1 - 2| = 1</code>。</li>
		</ul>
		</li>
		<li>以 <code>(0, 1)</code> 为起点的子矩阵：<code>[[-2, 3], [3, 5]]</code>。
		<ul>
			<li>子矩阵中的不同值为 <code>[-2, 3, 5]</code>。</li>
			<li>子矩阵中的最小绝对差为 <code>|3 - 5| = 2</code>。</li>
		</ul>
		</li>
	</ul>
	</li>
	<li>因此，答案为 <code>[[1, 2]]</code>。</li>
</ul>
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= m == grid.length &lt;= 30</code></li>
	<li><code>1 &lt;= n == grid[i].length &lt;= 30</code></li>
	<li><code>-105 &lt;= grid[i][j] &lt;= 105</code></li>
	<li><code>1 &lt;= k &lt;= min(m, n)</code></li>
</ul>