220. Contains Duplicate III
Approach
Bucket sort with bucket size valueDiff+1; within a sliding window
of indexDiff, check the same and two adjacent buckets for a near-duplicate.
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.
Sorting is often a preprocessing step that enables binary search, two-pointer sweeps, or greedy algorithms. C#'s Array.Sort() uses an introspective sort (O(n log n)). Custom comparisons use the Comparison<T> delegate or IComparer<T>. Consider counting sort or bucket sort for bounded integer inputs.
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.
// Approach: Bucket sort with bucket size valueDiff+1; within a sliding window
// of indexDiff, check the same and two adjacent buckets for a near-duplicate.
// Time: O(n) Space: O(k)
public class Solution
{
public bool ContainsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff)
{
if (nums.Length == 0 || indexDiff <= 0 || valueDiff < 0)
return false;
long mn = nums.Min();
long diff = valueDiff + 1; // In case that `valueDiff` equals 0.
// Use long because of corner case int.MaxValue - (-1) will overflow
Dictionary<long, long> bucket = new Dictionary<long, long>();
for (int i = 0; i < nums.Length; ++i)
{
long num = (long)nums[i];
long key = GetKey(nums[i], mn, diff);
if (bucket.ContainsKey(key)) // the current bucket
return true;
if (bucket.ContainsKey(key - 1) && num - bucket[key - 1] < diff) // the left adjacent bucket
return true;
if (bucket.ContainsKey(key + 1) && bucket[key + 1] - num < diff) // the right adjacent bucket
return true;
bucket[key] = num;
if (i >= indexDiff)
bucket.Remove(GetKey(nums[i - indexDiff], mn, diff));
}
return false;
}
private long GetKey(int num, long mn, long diff)
{
return (num - mn) / diff;
}
}