Contains Duplicate III

Contains Duplicate III

What is this problem about?

The Contains Duplicate III interview question is the most complex version. You need to find two distinct indices i and j such that:

1. abs(nums[i] - nums[j]) <= t (Value difference)
2. abs(i - j) <= k (Index difference)

Why is this asked in interviews?

This is a HARD difficulty problem frequently asked by Google and Airbnb. The Contains Duplicate III coding problem tests advanced data structure usage. You can't use a simple Hash Set because you aren't looking for an exact match, but a value near the current one.

Algorithmic pattern used

This follows the Array, Bucket Sort, Sorting, Sliding Window, Ordered Set interview pattern.

1. Ordered Set approach (O(N log K)): Use a self-balancing BST (like TreeSet in Java) to store the sliding window of size k. For each new element x, find the smallest element >= x - t. If that element is <= x + t, a match is found.
2. Bucket Sort approach (O(N)): Divide numbers into "buckets" of size t+1. If two numbers fall in the same bucket, the condition is met. If not, check adjacent buckets.

Example explanation

Array: [1, 5, 9, 1], k = 2, t = 3

1. Bucket size = 4. 1 goes into bucket 0.
2. 5 goes into bucket 1. Check bucket 0 and 2. 1 is in bucket 0, but 5-1=4 > 3.
3. 9 goes into bucket 2. Check bucket 1 and 3. 5 is in bucket 1, but 9-5=4 > 3.
4. Remove 1 from bucket 0 (it's > k away). ... and so on.

Common mistakes candidates make

• Integer Overflow: Calculating nums[i] - nums[j] can overflow standard 32-bit integers. Use 64-bit integers.
• Complexity: Trying to sort the entire window repeatedly (O(N * K log K)), which is too slow.
• Bucket logic errors: Not correctly handling negative numbers in bucket indexing.

Interview preparation tip

Master the Ordered Set (BST) operations in your chosen language. Knowing how to efficiently find the "ceiling" or "floor" of a value in a sorted collection is a common requirement for "nearby value" problems.