220. Contains Duplicate III #

Problem #

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Problem Summary #

Given an array num, and K and t. Determine whether a pair of i and j can be found in num such that the absolute difference between num[i] and num[j] is at most t, and the absolute difference between i and j is at most k.

Solution Ideas #

• Given an array, the requirement is to find 2 indices in the array, i and j, such that | nums[i] - nums[j] | ≤ t and | i - j | ≤ k.
• This is a sliding window problem. The first idea is to use two pointers, i and j; for each i, scan the entire array backward from i + 1, check each i and j, and determine whether the problem requirements are satisfied. During the loop for j, pay attention to the pruning condition | i - j | ≤ k. The time complexity of this approach is O(n^2). The reason this approach is slow is that the left and right boundaries of the sliding window do not slide together during the sliding process.
• So consider: what if the array is sorted? Sort the array in ascending order by element value; if the element values are equal, sort by index in ascending order. In such a sorted array, when looking for i and j that satisfy the requirements, the left and right boundaries of the sliding window slide together. Slide the right boundary of the window to a position where the difference from the left boundary’s element value is ≤ t. After this condition is satisfied, then check | i - j | ≤ k. If the difference between the right boundary and the left boundary’s element value is > t, it means the left boundary should be moved to the right (the reason it can be moved this way is that we sorted the array elements by value; moving right is the direction of increasing elements). When moving the left boundary, note that the left boundary cannot exceed the right boundary. In this way, by sliding the window once across the entire sorted array, we can determine whether there exist i and j that satisfy the requirements. The main time cost of this approach is sorting, and the time complexity is O(n log n).
• The optimal solution for this problem uses the idea of bucket sort. The condition | i - j | ≤ k is maintained using a window of size k. The key is how to satisfy the condition | nums[i] - nums[j] | ≤ t. Using the idea of bucket sort, divide all elements nums[i] into …,[0,t],[t+1,2t+1],…. The size of each interval is t + 1. Each element now corresponds to a bucket ID. Performing 3 lookups can determine whether a pair satisfying the condition | nums[i] - nums[j] | ≤ t can be found. If an element is found in the same bucket, then such i and j can be found. There are also 2 possible cases corresponding to bucket boundaries. If there exists an element in the previous bucket that can make the difference also ≤ t, then such a pair also satisfies the requirements. The final case is that if there exists an element in the next bucket that can make the difference also ≤ t, then such a pair also satisfies the requirements. Query 3 times; if none exists, it means the current i cannot find a j that satisfies the requirements. Continue the loop to search. If no pair satisfying the requirements is found after one full loop, output false.

Code #

package leetcode

// Solution 1 Bucket Sort
func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
	if k <= 0 || t < 0 || len(nums) < 2 {
		return false
	}
	buckets := map[int]int{}
	for i := 0; i < len(nums); i++ {
		// Get the ID of the bucket from element value nums[i] and bucket width t + 1
		key := nums[i] / (t + 1)
		// -7/9 = 0, but need -7/9 = -1
		if nums[i] < 0 {
			key--
		}
		if _, ok := buckets[key]; ok {
			return true
		}
		// check the lower bucket, and have to check the value too
		if v, ok := buckets[key-1]; ok && nums[i]-v <= t {
			return true
		}
		// check the upper bucket, and have to check the value too
		if v, ok := buckets[key+1]; ok && v-nums[i] <= t {
			return true
		}
		// maintain k size of window
		if len(buckets) >= k {
			delete(buckets, nums[i-k]/(t+1))
		}
		buckets[key] = nums[i]
	}
	return false
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}

// Solution 2 Sliding Window + Pruning
func containsNearbyAlmostDuplicate1(nums []int, k int, t int) bool {
	if len(nums) <= 1 {
		return false
	}
	if k <= 0 {
		return false
	}
	n := len(nums)
	for i := 0; i < n; i++ {
		count := 0
		for j := i + 1; j < n && count < k; j++ {
			if abs(nums[i]-nums[j]) <= t {
				return true
			}
			count++
		}
	}
	return false
}