LeetCode 220 - Contains Duplicate III

LeetCode Problem 220

Difficulty: 🔴 Hard
Topics: Array, Sliding Window, Sorting, Bucket Sort, Ordered Set

Solution

Problem Understanding

The problem asks whether there exists a pair of different indices (i, j) in the array such that two conditions are satisfied at the same time.

The first condition is about index distance:

$$|i - j| \leq indexDiff$$

This means the two elements must be relatively close together in the array.

The second condition is about value distance:

$$|nums[i] - nums[j]| \leq valueDiff$$

This means the values themselves must also be close numerically.

We need to return true if at least one valid pair exists. Otherwise, we return false.

The input consists of:

• nums, an integer array that may contain positive numbers, negative numbers, and duplicates.
• indexDiff, which limits how far apart indices may be.
• valueDiff, which limits how different the values may be.

The constraints are large:

• nums.length can be up to 100000
• Values can range from -10^9 to 10^9

These constraints immediately rule out quadratic solutions. A naive pairwise comparison would require checking up to:

$$\frac{n(n-1)}{2}$$

pairs, which is far too slow when n = 100000.

Another important observation is that we only care about elements within an index window of size indexDiff. Once an element becomes farther away than that, it can never participate in a valid pair with the current element.

Several edge cases are important:

• valueDiff = 0, which means we are effectively looking for duplicates within a sliding window.
• Negative numbers, because bucket calculations can become tricky with integer division.
• Very large positive and negative values, which means overflow must be handled carefully in languages like Go.
• Arrays with repeated values appearing just outside the allowed index range.
• Very small windows such as indexDiff = 1.

Approaches

Brute Force

The simplest approach is to check every valid pair of indices.

For each index i, we examine every index j such that:

$$i < j \leq i + indexDiff$$

For each pair, we compute:

$$|nums[i] - nums[j]|$$

If the difference is at most valueDiff, we return true.

This works because it explicitly checks every possible candidate pair that satisfies the index constraint.

However, the worst case occurs when indexDiff is close to n. In that situation, we may compare nearly every pair of elements, leading to:

$$O(n^2)$$

time complexity.

With 100000 elements, this becomes infeasible.

Optimal Approach, Bucket Sort with Sliding Window

The key insight is that if two numbers differ by at most valueDiff, then they must either:

• fall into the same bucket, or
• fall into adjacent buckets

if we define bucket size as:

$$bucketSize = valueDiff + 1$$

Why does this work?

Suppose each bucket covers a numeric interval of width valueDiff + 1.

Then any two numbers inside the same bucket must differ by at most valueDiff.

For example, if valueDiff = 3, then bucket size is 4:

• Bucket 0 contains [0,1,2,3]
• Bucket 1 contains [4,5,6,7]

Any two values inside the same bucket differ by at most 3.

We process the array from left to right while maintaining only the last indexDiff elements inside our bucket structure. This creates a sliding window over valid indices.

For every number:

1. Compute its bucket ID.
2. Check whether that bucket already contains a number.
3. Check neighboring buckets because close values can straddle bucket boundaries.
4. Insert the current value.
5. Remove elements that leave the sliding window.

This reduces the problem to approximately constant work per element.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * indexDiff) worst case O(n²)	O(1)	Checks every eligible pair directly
Optimal	O(n)	O(indexDiff)	Uses buckets and a sliding window

Algorithm Walkthrough

Optimal Bucket-Based Sliding Window Algorithm

1. Define the bucket size as valueDiff + 1.

We cannot use valueDiff directly because when valueDiff = 0, bucket size would become zero, which is invalid. Using valueDiff + 1 guarantees a positive bucket width. 2. Create a hash map called buckets.

The key is the bucket ID, and the value is the actual number stored in that bucket.

At any moment, the map only contains elements inside the current sliding window of size indexDiff. 3. Iterate through the array from left to right.

For each value num, compute its bucket ID.

The bucket ID is:

$$bucketId = \left\lfloor \frac{num}{bucketSize} \right\rfloor$$

Care must be taken with negative numbers because integer division behaves differently across languages. 4. Check whether the current bucket already contains a number.

If it does, then the existing number and the current number differ by at most valueDiff.

We can immediately return true. 5. Check the neighboring buckets.

Even if two numbers are not in the same bucket, they may still satisfy the value constraint if they lie near a bucket boundary.

Therefore, we also examine:

• bucketId - 1
• bucketId + 1

If either neighboring bucket exists and the absolute difference is at most valueDiff, return true. 6. Insert the current number into its bucket.

After all checks pass, store the current value. 7. Maintain the sliding window.

Once the window size exceeds indexDiff, remove the element that falls out of range.

Specifically, when processing index i, remove:

$$nums[i - indexDiff]$$

because any future element would violate the index constraint with it. 8. If the loop finishes without finding a valid pair, return false.

Why it works

The algorithm maintains the invariant that the bucket map contains exactly the elements whose indices are within indexDiff of the current position.

Because each bucket spans valueDiff + 1 consecutive integers, any two numbers inside the same bucket must differ by at most valueDiff.

Any valid pair crossing a bucket boundary must lie in neighboring buckets, so checking adjacent buckets is sufficient.

Thus, every valid candidate pair is examined, and no invalid pair can incorrectly satisfy the conditions.

Python Solution

from typing import List

class Solution:
    def containsNearbyAlmostDuplicate(
        self,
        nums: List[int],
        indexDiff: int,
        valueDiff: int
    ) -> bool:

        bucket_size = valueDiff + 1
        buckets = {}

        for i, num in enumerate(nums):

            bucket_id = num // bucket_size

            # Same bucket
            if bucket_id in buckets:
                return True

            # Left neighbor bucket
            if (
                bucket_id - 1 in buckets and
                abs(num - buckets[bucket_id - 1]) <= valueDiff
            ):
                return True

            # Right neighbor bucket
            if (
                bucket_id + 1 in buckets and
                abs(num - buckets[bucket_id + 1]) <= valueDiff
            ):
                return True

            buckets[bucket_id] = num

            # Remove element outside sliding window
            if i >= indexDiff:
                old_num = nums[i - indexDiff]
                old_bucket_id = old_num // bucket_size
                del buckets[old_bucket_id]

        return False

The implementation begins by computing the bucket size as valueDiff + 1.

The buckets dictionary stores at most one value per bucket. This works because if a bucket already contains a value, then any new value entering that same bucket automatically satisfies the required difference condition.

For every element, we compute its bucket ID using integer division. Python's floor division correctly handles negative numbers, which simplifies the implementation.

We first check the current bucket. Then we check neighboring buckets because values near bucket boundaries may still differ by at most valueDiff.

If no match is found, we insert the current number into its bucket.

The final section maintains the sliding window. Once the window exceeds indexDiff, we remove the oldest element from its bucket so that all remaining elements satisfy the index constraint.

Go Solution

package main

import "math"

func containsNearbyAlmostDuplicate(nums []int, indexDiff int, valueDiff int) bool {
	bucketSize := int64(valueDiff) + 1
	buckets := make(map[int64]int64)

	getBucketID := func(num int64) int64 {
		if num >= 0 {
			return num / bucketSize
		}
		return ((num + 1) / bucketSize) - 1
	}

	for i, num := range nums {
		n := int64(num)
		bucketID := getBucketID(n)

		// Same bucket
		if _, exists := buckets[bucketID]; exists {
			return true
		}

		// Left neighbor
		if val, exists := buckets[bucketID-1]; exists {
			if math.Abs(float64(n-val)) <= float64(valueDiff) {
				return true
			}
		}

		// Right neighbor
		if val, exists := buckets[bucketID+1]; exists {
			if math.Abs(float64(n-val)) <= float64(valueDiff) {
				return true
			}
		}

		buckets[bucketID] = n

		// Remove old element outside window
		if i >= indexDiff {
			oldNum := int64(nums[i-indexDiff])
			oldBucketID := getBucketID(oldNum)
			delete(buckets, oldBucketID)
		}
	}

	return false
}

The Go implementation is structurally identical to the Python solution, but there are several language-specific considerations.

Go integer division truncates toward zero rather than flooring toward negative infinity. Because of this, negative numbers require special handling in the getBucketID helper function.

All arithmetic is performed using int64 to avoid overflow when working with values near 10^9.

Go maps are used for bucket storage, and delete removes elements leaving the sliding window.

Worked Examples

Example 1

Input:

nums = [1,2,3,1]
indexDiff = 3
valueDiff = 0

Bucket size:

valueDiff + 1 = 1

i	num	bucket_id	buckets before	Action
0	1	1	{}	insert 1
1	2	2	{1:1}	insert 2
2	3	3	{1:1,2:2}	insert 3
3	1	1	{1:1,2:2,3:3}	same bucket found, return true

The second occurrence of 1 lands in the same bucket as the first occurrence.

Result:

true

Example 2

Input:

nums = [1,5,9,1,5,9]
indexDiff = 2
valueDiff = 3

Bucket size:

4

i	num	bucket_id	buckets before	Action
0	1	0	{}	insert
1	5	1	{0:1}	difference is 4, insert
2	9	2	{0:1,1:5}	difference is 4, insert
3	1	0	{1:5,2:9} after removal	insert
4	5	1	{0:1,2:9} after removal	insert
5	9	2	{0:1,1:5} after removal	insert

No valid pair is ever found.

Result:

false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each element is inserted, checked, and removed once
Space	O(indexDiff)	The sliding window stores at most indexDiff elements

The algorithm performs constant-time hash map operations for every array element. Since each number enters and leaves the bucket map exactly once, the total runtime is linear.

The bucket map only stores elements currently inside the sliding window, so its size never exceeds indexDiff.

Test Cases

sol = Solution()

# Provided examples
assert sol.containsNearbyAlmostDuplicate(
    [1, 2, 3, 1], 3, 0
) is True  # duplicate within index range

assert sol.containsNearbyAlmostDuplicate(
    [1, 5, 9, 1, 5, 9], 2, 3
) is False  # values too far apart

# Exact duplicate with minimal window
assert sol.containsNearbyAlmostDuplicate(
    [1, 1], 1, 0
) is True  # simplest valid duplicate

# Duplicate outside allowed index range
assert sol.containsNearbyAlmostDuplicate(
    [1, 2, 3, 1], 2, 0
) is False  # duplicate exists but too far away

# Neighboring values within valueDiff
assert sol.containsNearbyAlmostDuplicate(
    [1, 5, 6], 2, 1
) is True  # 5 and 6 differ by 1

# Negative numbers
assert sol.containsNearbyAlmostDuplicate(
    [-3, -2, -1], 2, 1
) is True  # adjacent negatives

# Large positive and negative values
assert sol.containsNearbyAlmostDuplicate(
    [-1000000000, 1000000000], 1, 1
) is False  # huge difference

# Window size one
assert sol.containsNearbyAlmostDuplicate(
    [1, 0, 1, 1], 1, 2
) is True  # adjacent valid pair

# valueDiff zero but no duplicates
assert sol.containsNearbyAlmostDuplicate(
    [1, 2, 3, 4], 3, 0
) is False  # exact match required

# Multiple valid candidates
assert sol.containsNearbyAlmostDuplicate(
    [7, 1, 3, 6], 3, 2
) is True  # 7 and 6 differ by 1

Test	Why
[1,2,3,1], 3, 0	Basic valid duplicate case
[1,5,9,1,5,9], 2, 3	No valid pair exists
[1,1], 1, 0	Smallest nontrivial valid input
[1,2,3,1], 2, 0	Duplicate exists but index constraint fails
[1,5,6], 2, 1	Non-equal values within allowed difference
[-3,-2,-1], 2, 1	Validates negative-number bucket handling
[-1e9,1e9], 1, 1	Tests large numeric range
[1,0,1,1], 1, 2	Valid pair appears in tight window
[1,2,3,4], 3, 0	Requires exact duplicates
[7,1,3,6], 3, 2	Multiple possible matching values

Edge Cases

valueDiff = 0

When valueDiff is zero, the problem becomes equivalent to finding duplicates within a sliding window.

This case is easy to mishandle because bucket size would become zero if we used valueDiff directly. The implementation avoids division-by-zero errors by defining:

$$bucketSize = valueDiff + 1$$

This guarantees a valid bucket width.

Negative Numbers

Negative values can break naive bucket calculations because integer division behaves differently across languages.

Python automatically floors negative division, which works naturally for bucket partitioning. Go truncates toward zero, so the implementation includes a custom helper function to correctly simulate floor division behavior.

Without this correction, negative values near bucket boundaries could be placed into incorrect buckets.

Elements Leaving the Sliding Window

A common bug is forgetting to remove old elements once they are farther than indexDiff away.

If outdated elements remain in the buckets map, the algorithm may incorrectly match elements whose indices violate the problem constraints.

The implementation removes:

nums[i - indexDiff]

as soon as the window becomes too large, ensuring that every stored element always satisfies the index-distance requirement relative to the current index.