Contains Duplicate III solution and explanation
Google
9 more videos on this problem
Contains Duplicate iii | LeetCode 220 | C++, PythonKnowledge Center · 12:36 · 22K views
LeetCode 220: Contains Duplicate III - Interview Prep Ep 47Fisher Coder · 22:10 · 16K views
contains duplicate iii | contains duplicate III | leetcode 220 | two solutionsNaresh Gupta · 13:17 · 13K views
Leetcode - Contains Duplicate III (Python)Timothy H Chang · 8:42 · 7K views
Contains Duplicate III - Leetcode 220 ⚡SortedSet Sliding Window | PythonDKodeTree · 14:30 · 2K views
Contains Duplicate III | LeetCode 220 | September LeetCoding Challenge | 2nd Septembercode.thinkerspoint · 22:20 · 1K views
【每日一题】220. Contains Duplicate III, 04/20/2019Huifeng Guan · 23:35 · 1K views
Contains Duplicate III | LeetCode 220 | Java, PythonLearn Code Repeat · 17:18 · 1K views
Daily Leetcode #155: Sep 02, 2020 - 220. Contains Duplicate IIIProgramming Live with Larry · 22:31 · 1K views
Leetcode [220] Contains Duplicate IIISDE Skills · 23:31 · 945 views
The problem
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 <= 105-109 <= nums[i] <= 1091 <= indexDiff <= nums.length0 <= valueDiff <= 109
Approach overview
Problem Overview: Given an integer array, determine whether two different indices i and j exist such that |i - j| ≤ k and |nums[i] - nums[j]| ≤ t. The challenge is enforcing both the index distance and value distance constraints efficiently without checking every pair.
Approach 1: Sliding Window with TreeSet (O(n log k) time, O(k) space)
This approach maintains a sliding window of size k containing the last k elements while iterating through the array. An ordered structure like TreeSet (Java) or a balanced sorted container is used so you can quickly find the closest numbers to the current value. For each element nums[i], search the set for the smallest number greater than or equal to nums[i] - t. If that candidate is ≤ nums[i] + t, the condition is satisfied. Insert the current value into the set and remove the element that slides out when the window exceeds size k. Ordered lookup and insertion take O(log k), giving total O(n log k) time with O(k) space. This technique combines sliding window logic with an ordered set to enforce both constraints efficiently.
Approach 2: Bucketing Technique (O(n) time, O(n) space)
The bucket method achieves linear time by grouping numbers into ranges of width t + 1. If two numbers differ by at most t, they must fall into either the same bucket or adjacent buckets. For each element, compute its bucket ID using integer division. First check whether the current bucket already contains a number. Then check the neighboring buckets because their values could still be within distance t. Store the current number in its bucket and maintain the k-sized window by removing the bucket corresponding to nums[i - k]. Each lookup, insertion, and deletion is constant time using a hash map, producing O(n) time and O(n) space. This approach relies on value partitioning rather than ordering and is closely related to bucket sort ideas applied to an array traversal.
Recommended for interviews: The sliding window with an ordered set is often the expected solution because it demonstrates understanding of balanced search trees and range queries. The bucket approach is more optimal at O(n) but requires a key insight about bucket width and careful handling of negative numbers and overflow. Showing the TreeSet solution first proves you understand the constraint interaction, while implementing the bucket technique signals stronger algorithmic intuition.
Approach 1: Sliding Window with TreeSet
This approach uses a sliding window technique to maintain a set of the current window elements. TreeSet (or equivalent in other languages) is used to efficiently handle range-based queries within the window. By maintaining a set of elements within indexDiff, we can quickly check if there is a number within valueDiff of the current number.
from sortedcontainers import SortedList
def contains_nearby_almost_duplicate(nums, indexDiff, valueDiff):
if indexDiff <= 0 or valueDiff < 0:
return False
sorted_list = SortedList()
for i in range(len(nums)):
if i > indexDiff:
sorted_list.remove(nums[i - indexDiff - 1])
pos1 = SortedList.bisect_left(sorted_list, nums[i] - valueDiff)
pos2 = SortedList.bisect_right(sorted_list, nums[i] + valueDiff)
if pos1 != pos2:
return True
sorted_list.add(nums[i])
return Falseimport java.util.TreeSet;
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
if (indexDiff <= 0 || valueDiff < 0) return false;
TreeSet<Long> set = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
long num = (long) nums[i];
Long floor = set.floor(num + valueDiff);
Long ceil = set.ceiling(num - valueDiff);
if ((floor != null && floor >= num) || (ceil != null && ceil <= num)) {
return true;
}
set.add(num);
if (i >= indexDiff)
set.remove((long) nums[i - indexDiff]);
}
return false;
}
}This solution utilizes SortedList from sortedcontainers to mimic the functionality of a TreeSet, allowing range-based queries within the sliding window. The list is maintained such that it contains elements within indexDiff.
Time complexity: O(n log k), similar to Java's TreeSet method.
Space complexity: O(k) due to the sliding window of size indexDiff.
Approach 2: Bucketing Technique
This approach involves bucketing the numbers using their division by (valueDiff + 1). Each bucket can contain numbers that satisfy the valueDiff condition. We keep track of active buckets for indices falling within the indexDiff range.
def contains_nearby_almost_duplicate(nums, indexDiff, valueDiff):
if valueDiff < 0:
return False
buckets = {}
w = valueDiff + 1
for i, num in enumerate(nums):
bucket = num // w
if bucket in buckets:
return True
if bucket - 1 in buckets and num - buckets[bucket - 1] < w:
return True
if bucket + 1 in buckets and buckets[bucket + 1] - num < w:
return True
buckets[bucket] = num
if i >= indexDiff:
del buckets[nums[i - indexDiff] // w]
return Falseimport java.util.HashMap;
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
if (valueDiff < 0) return false;
HashMap<Long, Long> buckets = new HashMap<>();
long w = (long) valueDiff + 1;
for (int i = 0; i < nums.length; i++) {
long num = (long) nums[i] - Integer.MIN_VALUE;
long bucket = num / w;
if (buckets.containsKey(bucket)
|| (buckets.containsKey(bucket - 1) && num - buckets.get(bucket - 1) < w)
|| (buckets.containsKey(bucket + 1) && buckets.get(bucket + 1) - num < w)) {
return true;
}
if (buckets.size() >= indexDiff) {
long lastBucket = ((long) nums[i - indexDiff] - Integer.MIN_VALUE) / w;
buckets.remove(lastBucket);
}
buckets.put(bucket, num);
}
return false;
}
}This method uses bucketing similar to the Java implementation. By translating numbers into bucket indices based on the value size, we efficiently map and check potential candidates.
Time complexity: O(n) due to constant time average bucket operations.
Space complexity: O(k), with a hash to maintain up to k buckets.
Approach 3: Sliding Window + Ordered Set
We maintain a sliding window of size k, and the elements in the window are kept in order.
We traverse the array nums. For each element nums[i], we look for the first element in the ordered set that is greater than or equal to nums[i] - t. If the element exists, and this element is less than or equal to nums[i] + t, it means we have found a pair of elements that meet the conditions, and we return true. Otherwise, we insert nums[i] into the ordered set, and if the size of the ordered set exceeds k, we need to remove the earliest added element from the ordered set.
The time complexity is O(n times log k), where n is the length of the array nums. For each element, we need O(log k) time to find the element in the ordered set, and there are n elements in total, so the total time complexity is O(n times log k).
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
set<long> s;
for (int i = 0; i < nums.size(); ++i) {
auto it = s.lower_bound((long) nums[i] - valueDiff);
if (it != s.end() && *it <= (long) nums[i] + valueDiff) return true;
s.insert((long) nums[i]);
if (i >= indexDiff) s.erase((long) nums[i - indexDiff]);
}
return false;
}
};function containsNearbyAlmostDuplicate(
nums: number[],
indexDiff: number,
valueDiff: number,
): boolean {
const ts = new TreeSet<number>();
for (let i = 0; i < nums.length; ++i) {
const x = ts.ceil(nums[i] - valueDiff);
if (x != null && x <= nums[i] + valueDiff) {
return true;
}
ts.add(nums[i]);
if (i >= indexDiff) {
ts.delete(nums[i - indexDiff]);
}
}
return false;
}
type Compare<T> = (lhs: T, rhs: T) => number;
class RBTreeNode<T = number> {
data: T;
count: number;
left: RBTreeNode<T> | null;
right: RBTreeNode<T> | null;
parent: RBTreeNode<T> | null;
color: number;
constructor(data: T) {
this.data = data;
this.left = this.right = this.parent = null;
this.color = 0;
this.count = 1;
}
sibling(): RBTreeNode<T> | null {
if (!this.parent) return null; // sibling null if no parent
return this.isOnLeft() ? this.parent.right : this.parent.left;
}
isOnLeft(): boolean {
return this === this.parent!.left;
}
hasRedChild(): boolean {
return (
Boolean(this.left && this.left.color === 0) ||
Boolean(this.right && this.right.color === 0)
);
}
}
class RBTree<T> {
root: RBTreeNode<T> | null;
lt: (l: T, r: T) => boolean;
constructor(compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0)) {
this.root = null;
this.lt = (l: T, r: T) => compare(l, r) < 0;
}
rotateLeft(pt: RBTreeNode<T>): void {
const right = pt.right!;
pt.right = right.left;
if (pt.right) pt.right.parent = pt;
right.parent = pt.parent;
if (!pt.parent) this.root = right;
else if (pt === pt.parent.left) pt.parent.left = right;
else pt.parent.right = right;
right.left = pt;
pt.parent = right;
}
rotateRight(pt: RBTreeNode<T>): void {
const left = pt.left!;
pt.left = left.right;
if (pt.left) pt.left.parent = pt;
left.parent = pt.parent;
if (!pt.parent) this.root = left;
else if (pt === pt.parent.left) pt.parent.left = left;
else pt.parent.right = left;
left.right = pt;
pt.parent = left;
}
swapColor(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.color;
p1.color = p2.color;
p2.color = tmp;
}
swapData(p1: RBTreeNode<T>, p2: RBTreeNode<T>): void {
const tmp = p1.data;
p1.data = p2.data;
p2.data = tmp;
}
fixAfterInsert(pt: RBTreeNode<T>): void {
let parent = null;
let grandParent = null;
while (pt !== this.root && pt.color !== 1 && pt.parent?.color === 0) {
parent = pt.parent;
grandParent = pt.parent.parent;
/* Case : A
Parent of pt is left child of Grand-parent of pt */
if (parent === grandParent?.left) {
const uncle = grandParent.right;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle && uncle.color === 0) {
grandParent.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent;
} else {
/* Case : 2
pt is right child of its parent
Left-rotation required */
if (pt === parent.right) {
this.rotateLeft(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is left child of its parent
Right-rotation required */
this.rotateRight(grandParent);
this.swapColor(parent!, grandParent);
pt = parent!;
}
} else {
/* Case : B
Parent of pt is right child of Grand-parent of pt */
const uncle = grandParent!.left;
/* Case : 1
The uncle of pt is also red
Only Recoloring required */
if (uncle != null && uncle.color === 0) {
grandParent!.color = 0;
parent.color = 1;
uncle.color = 1;
pt = grandParent!;
} else {
/* Case : 2
pt is left child of its parent
Right-rotation required */
if (pt === parent.left) {
this.rotateRight(parent);
pt = parent;
parent = pt.parent;
}
/* Case : 3
pt is right child of its parent
Left-rotation required */
this.rotateLeft(grandParent!);
this.swapColor(parent!, grandParent!);
pt = parent!;
}
}
}
this.root!.color = 1;
}
delete(val: T): boolean {
const node = this.find(val);
if (!node) return false;
node.count--;
if (!node.count) this.deleteNode(node);
return true;
}
deleteAll(val: T): boolean {
const node = this.find(val);
if (!node) return false;
this.deleteNode(node);
return true;
}
deleteNode(v: RBTreeNode<T>): void {
const u = BSTreplace(v);
// True when u and v are both black
const uvBlack = (u === null || u.color === 1) && v.color === 1;
const parent = v.parent!;
if (!u) {
// u is null therefore v is leaf
if (v === this.root) this.root = null;
// v is root, making root null
else {
if (uvBlack) {
// u and v both black
// v is leaf, fix double black at v
this.fixDoubleBlack(v);
} else {
// u or v is red
if (v.sibling()) {
// sibling is not null, make it red"
v.sibling()!.color = 0;
}
}
// delete v from the tree
if (v.isOnLeft()) parent.left = null;
else parent.right = null;
}
return;
}
if (!v.left || !v.right) {
// v has 1 child
if (v === this.root) {
// v is root, assign the value of u to v, and delete u
v.data = u.data;
v.left = v.right = null;
} else {
// Detach v from tree and move u up
if (v.isOnLeft()) parent.left = u;
else parent.right = u;
u.parent = parent;
if (uvBlack) this.fixDoubleBlack(u);
// u and v both black, fix double black at u
else u.color = 1; // u or v red, color u black
}
return;
}
// v has 2 children, swap data with successor and recurse
this.swapData(u, v);
this.deleteNode(u);
// find node that replaces a deleted node in BST
function BSTreplace(x: RBTreeNode<T>): RBTreeNode<T> | null {
// when node have 2 children
if (x.left && x.right) return successor(x.right);
// when leaf
if (!x.left && !x.right) return null;
// when single child
return x.left ?? x.right;
}
// find node that do not have a left child
// in the subtree of the given node
function successor(x: RBTreeNode<T>): RBTreeNode<T> {
let temp = x;
while (temp.left) temp = temp.left;
return temp;
}
}
fixDoubleBlack(x: RBTreeNode<T>): void {
if (x === this.root) return; // Reached root
const sibling = x.sibling();
const parent = x.parent!;
if (!sibling) {
// No sibiling, double black pushed up
this.fixDoubleBlack(parent);
} else {
if (sibling.color === 0) {
// Sibling red
parent.color = 0;
sibling.color = 1;
if (sibling.isOnLeft()) this.rotateRight(parent);
// left case
else this.rotateLeft(parent); // right case
this.fixDoubleBlack(x);
} else {
// Sibling black
if (sibling.hasRedChild()) {
// at least 1 red children
if (sibling.left && sibling.left.color === 0) {
if (sibling.isOnLeft()) {
// left left
sibling.left.color = sibling.color;
sibling.color = parent.color;
this.rotateRight(parent);
} else {
// right left
sibling.left.color = parent.color;
this.rotateRight(sibling);
this.rotateLeft(parent);
}
} else {
if (sibling.isOnLeft()) {
// left right
sibling.right!.color = parent.color;
this.rotateLeft(sibling);
this.rotateRight(parent);
} else {
// right right
sibling.right!.color = sibling.color;
sibling.color = parent.color;
this.rotateLeft(parent);
}
}
parent.color = 1;
} else {
// 2 black children
sibling.color = 0;
if (parent.color === 1) this.fixDoubleBlack(parent);
else parent.color = 1;
}
}
}
}
insert(data: T): boolean {
// search for a position to insert
let parent = this.root;
while (parent) {
if (this.lt(data, parent.data)) {
if (!parent.left) break;
else parent = parent.left;
} else if (this.lt(parent.data, data)) {
if (!parent.right) break;
else parent = parent.right;
} else break;
}
// insert node into parent
const node = new RBTreeNode(data);
if (!parent) this.root = node;
else if (this.lt(node.data, parent.data)) parent.left = node;
else if (this.lt(parent.data, node.data)) parent.right = node;
else {
parent.count++;
return false;
}
node.parent = parent;
this.fixAfterInsert(node);
return true;
}
find(data: T): RBTreeNode<T> | null {
let p = this.root;
while (p) {
if (this.lt(data, p.data)) {
p = p.left;
} else if (this.lt(p.data, data)) {
p = p.right;
} else break;
}
return p ?? null;
}
*inOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.inOrder(root.left!)) yield v;
yield root.data;
for (const v of this.inOrder(root.right!)) yield v;
}
*reverseInOrder(root: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
if (!root) return;
for (const v of this.reverseInOrder(root.right!)) yield v;
yield root.data;
for (const v of this.reverseInOrder(root.left!)) yield v;
}
}
class TreeSet<T = number> {
_size: number;
tree: RBTree<T>;
compare: Compare<T>;
constructor(
collection: T[] | Compare<T> = [],
compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
) {
if (typeof collection === 'function') {
compare = collection;
collection = [];
}
this._size = 0;
this.compare = compare;
this.tree = new RBTree(compare);
for (const val of collection) this.add(val);
}
size(): number {
return this._size;
}
has(val: T): boolean {
return !!this.tree.find(val);
}
add(val: T): boolean {
const successful = this.tree.insert(val);
this._size += successful ? 1 : 0;
return successful;
}
delete(val: T): boolean {
const deleted = this.tree.deleteAll(val);
this._size -= deleted ? 1 : 0;
return deleted;
}
ceil(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(p.data, val) >= 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
floor(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(val, p.data) >= 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
higher(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(val, p.data) < 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
lower(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(p.data, val) < 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
first(): T | undefined {
return this.tree.inOrder().next().value;
}
last(): T | undefined {
return this.tree.reverseInOrder().next().value;
}
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
pop(): T | undefined {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
*[Symbol.iterator](): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*keys(): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*values(): Generator<T, undefined, void> {
for (const val of this.tree.inOrder()) yield val;
return undefined;
}
/**
* Return a generator for reverse order traversing the set
*/
*rvalues(): Generator<T, undefined, void> {
for (const val of this.tree.reverseInOrder()) yield val;
return undefined;
}
}
class TreeMultiSet<T = number> {
_size: number;
tree: RBTree<T>;
compare: Compare<T>;
constructor(
collection: T[] | Compare<T> = [],
compare: Compare<T> = (l: T, r: T) => (l < r ? -1 : l > r ? 1 : 0),
) {
if (typeof collection === 'function') {
compare = collection;
collection = [];
}
this._size = 0;
this.compare = compare;
this.tree = new RBTree(compare);
for (const val of collection) this.add(val);
}
size(): number {
return this._size;
}
has(val: T): boolean {
return !!this.tree.find(val);
}
add(val: T): boolean {
const successful = this.tree.insert(val);
this._size++;
return successful;
}
delete(val: T): boolean {
const successful = this.tree.delete(val);
if (!successful) return false;
this._size--;
return true;
}
count(val: T): number {
const node = this.tree.find(val);
return node ? node.count : 0;
}
ceil(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(p.data, val) >= 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
floor(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(val, p.data) >= 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
higher(val: T): T | undefined {
let p = this.tree.root;
let higher = null;
while (p) {
if (this.compare(val, p.data) < 0) {
higher = p;
p = p.left;
} else {
p = p.right;
}
}
return higher?.data;
}
lower(val: T): T | undefined {
let p = this.tree.root;
let lower = null;
while (p) {
if (this.compare(p.data, val) < 0) {
lower = p;
p = p.right;
} else {
p = p.left;
}
}
return lower?.data;
}
first(): T | undefined {
return this.tree.inOrder().next().value;
}
last(): T | undefined {
return this.tree.reverseInOrder().next().value;
}
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
pop(): T | undefined {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
*[Symbol.iterator](): Generator<T, void, void> {
yield* this.values();
}
*keys(): Generator<T, void, void> {
for (const val of this.values()) yield val;
}
*values(): Generator<T, undefined, void> {
for (const val of this.tree.inOrder()) {
let count = this.count(val);
while (count--) yield val;
}
return undefined;
}
/**
* Return a generator for reverse order traversing the multi-set
*/
*rvalues(): Generator<T, undefined, void> {
for (const val of this.tree.reverseInOrder()) {
let count = this.count(val);
while (count--) yield val;
}
return undefined;
}
}public class Solution {
public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k <= 0 || t < 0) return false;
var index = new SortedList<int, object>();
for (int i = 0; i < nums.Length; ++i) {
if (index.ContainsKey(nums[i])) {
return true;
}
index.Add(nums[i], null);
var j = index.IndexOfKey(nums[i]);
if (j > 0 && (long)nums[i] - index.Keys[j - 1] <= t) {
return true;
}
if (j < index.Count - 1 && (long)index.Keys[j + 1] - nums[i] <= t) {
return true;
}
if (index.Count > k) {
index.Remove(nums[i - k]);
}
}
return false;
}
}func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
n := len(nums)
left, right := 0, 0
rbt := redblacktree.NewWithIntComparator()
for right < n {
cur := nums[right]
right++
if p, ok := rbt.Floor(cur); ok && cur-p.Key.(int) <= t {
return true
}
if p, ok := rbt.Ceiling(cur); ok && p.Key.(int)-cur <= t {
return true
}
rbt.Put(cur, struct{}{})
if right-left > k {
rbt.Remove(nums[left])
left++
}
}
return false
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window with TreeSet | Time complexity: |
| Bucketing Technique | Time complexity: |
| Sliding Window + Ordered Set | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with TreeSet | O(n log k) | O(k) | General interview solution when ordered range queries are easy to implement |
| Bucketing Technique | O(n) | O(n) | Best performance when constant-time hashing is available and bucket logic is implemented carefully |
Frequently asked questions
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.