220. Contains Duplicate III

LeetCode 220. Contains Duplicate III

Description

Given an integer array nums and two integers k and t, return true if there are two distinct indices i and j in the array such that abs(nums[i] - nums[j]) <= t and abs(i - j) <= k.

Example 1:

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

Example 2:

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

Constraints:

• 0 <= nums.length <= 2 * 104

• -231 <= nums[i] <= 231 - 1

• 0 <= k <= 104

• 0 <= t <= 231 - 1

Tags

Sort, Ordered Map

Solution

We initialize a map to store a set of buckets. The size of each bucket is t+1. Iterate over nums, we first obtain the bucket which the current element maps to. If there has already been an element in this bucket, we return true. Or, if the adjacent buckets hold elements and the difference between any one of the them and the current element is within t, return true. After evaluating, we put the current element to the corresponding bucket, and remove the bucket which nums[i-k] maps to. Finally, we return false since no qualified element found.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(\min(n, k))$

Code

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
	buckets := map[int]int{} // element:bucket, bucket size = t+1
	getID := func(x int) int {
		if x >= 0 {
			return x / (t + 1)
		}
		return (x+1)/(t+1) - 1
	}
	for i, x := range nums {
		id := getID(x)
		if _, ok := buckets[id]; ok {
			return true
		}
		if y, ok := buckets[id-1]; ok && abs(y-x) <= t {
			return true
		}
		if y, ok := buckets[id+1]; ok && abs(y-x) <= t {
			return true
		}
		buckets[id] = x
		if i >= k {
			delete(buckets, getID(nums[i-k]))
		}
	}
	return false
}

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

Reference

1. 存在重复元素 III