Is Contains Duplicate III easy or hard?

Contains Duplicate III is classified as a Hard problem because it combines two constraints: index distance and value difference. Efficient solutions require either ordered set range queries or a non-obvious bucket partitioning trick.

Contains Duplicate III Python/Java solution

Python solutions typically use a sorted container or the bucket-hash technique with dictionaries. Java implementations often use TreeSet for the ordered sliding window or HashMap for bucket storage. Both languages can implement the O(n log k) TreeSet method or the O(n) bucket optimization.

How to solve Contains Duplicate III in O(n)?

Use the bucketing technique. Divide numbers into buckets of width t + 1 so that any two values within distance t must fall into the same or adjacent buckets. For each element, check its bucket and neighboring buckets in a hash map while maintaining a sliding window of size k. All operations are constant time, giving O(n) time complexity.

What is the best approach for Contains Duplicate III?

The most common interview solution uses a sliding window with an ordered set such as TreeSet or a balanced BST. It keeps the last k elements sorted so you can quickly find values within the range [nums[i] - t, nums[i] + t]. This gives O(n log k) time and O(k) space while directly enforcing both index and value constraints.

Is Contains Duplicate III asked at Google/Amazon/Meta?

Contains Duplicate III appears in interviews at large tech companies because it tests multiple concepts together: sliding window constraints, ordered data structures, and hashing tricks. Variations of this problem have been reported in interviews at companies like Google, Amazon, and Meta.

What data structure is used in Contains Duplicate III?

Common solutions rely on ordered sets (TreeSet or balanced BST) or hash maps for bucket storage. The TreeSet approach supports efficient range queries within a sliding window, while the bucket solution uses hashing to group numbers into value ranges.

What is the time complexity of Contains Duplicate III?

Time complexity depends on the approach used. The sliding window with TreeSet runs in O(n log k) because each insertion and range query costs O(log k). The bucket-based method improves this to O(n) average time by using hash buckets of size t + 1.

Description Hints 2 Solution Video 12:36

220. Contains Duplicate III

Hard25.2% acceptance8 companies

You are given an integer array nums and two integers indexDiff and valueDiff.

Find a pair of indices (i, j) such that:

i != j,
abs(i - j) <= indexDiff.
abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

Constraints:

2 <= nums.length <= 10⁵
-10⁹ <= nums[i] <= 10⁹
1 <= indexDiff <= nums.length
0 <= valueDiff <= 10⁹

Asked at 8 companies

Netflix Airbnb Palantir Microsoft

Google Amazon Meta Bloomberg

Topics

Hints open one at a time

Hint 1

Time complexity O(n logk) - This will give an indication that sorting is involved for k elements.

Hint 2

Use already existing state to evaluate next state - Like, a set of k sorted numbers are only needed to be tracked. When we are processing the next number in array, then we can utilize the existing sorted state and it is not necessary to sort next overlapping set of k numbers again.

12:36

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution