3567. Minimum Absolute Difference in Sliding Submatrix
Approach
For each k×k submatrix sort unique elements; find min adjacent difference.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
The sliding window technique maintains a dynamic sub-array (or substring) of interest, expanding the right boundary and shrinking the left boundary based on a constraint. It reduces O(n²) substring enumeration to O(n). Track state (frequency map, sum, distinct count) incrementally.
Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.
// Approach: For each k×k submatrix sort unique elements; find min adjacent difference.
// Time: O(mn * k² log k) Space: O(k²)
public class Solution
{
public int[][] MinAbsDiff(int[][] grid, int k)
{
int rows = grid.Length;
int cols = grid[0].Length;
// Result array to store minimum absolute differences for each subgrid
int[][] result = new int[rows - k + 1][];
for (int i = 0; i < result.Length; i++)
result[i] = new int[cols - k + 1];
// Iterate through all possible starting positions for k x k subgrids
for (int startRow = 0; startRow <= rows - k; startRow++)
{
for (int startCol = 0; startCol <= cols - k; startCol++)
{
// Collect all elements from the current k x k subgrid
List<int> subgridElements = new List<int>();
for (int row = startRow; row < startRow + k; row++)
{
for (int col = startCol; col < startCol + k; col++)
subgridElements.Add(grid[row][col]);
}
// Sort elements to find minimum difference between adjacent elements
subgridElements.Sort();
// Find minimum absolute difference between any two distinct elements
int minDifference = int.MaxValue;
for (int index = 1; index < subgridElements.Count; index++)
{
int previousElement = subgridElements[index - 1];
int currentElement = subgridElements[index];
// Only consider distinct elements
if (previousElement != currentElement)
minDifference = Math.Min(minDifference,
Math.Abs(previousElement - currentElement));
}
// If no distinct elements found (all elements are the same), set to 0
result[startRow][startCol] = (minDifference == int.MaxValue) ? 0 : minDifference;
}
}
return result;
}
}