Facebook Pixel

220. Contains Duplicate III

HardArrayBucket SortOrdered SetSortingSliding Window
Leetcode Link

Problem Description

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

Your task is to determine whether there exists a pair of indices (i, j) in the array that satisfies all of the following conditions:

  1. The indices must be different: i != j
  2. The distance between indices must not exceed indexDiff: abs(i - j) <= indexDiff
  3. The difference between the values at these indices must not exceed valueDiff: abs(nums[i] - nums[j]) <= valueDiff

Return true if such a pair exists, otherwise return false.

In other words, you need to find two elements in the array that are:

  • Close enough in position (within indexDiff positions of each other)
  • Close enough in value (their difference is at most valueDiff)

For example, if nums = [1, 5, 9, 1, 5, 9], indexDiff = 2, and valueDiff = 3:

  • Indices (0, 3) won't work because abs(0 - 3) = 3 > indexDiff
  • Indices (1, 2) won't work because abs(5 - 9) = 4 > valueDiff
  • Indices (0, 1) would work because abs(0 - 1) = 1 <= indexDiff and abs(1 - 5) = 4 but this exceeds valueDiff, so it doesn't work
  • However, indices (3, 4) would work because abs(3 - 4) = 1 <= indexDiff and abs(1 - 5) = 4 but we need to check if there's a valid pair

The challenge is to efficiently check all possible pairs within the given constraints.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The naive approach would be to check every pair of indices within indexDiff distance, but this could be inefficient with time complexity O(n * indexDiff).

The key insight is that we only care about elements within a sliding window of size indexDiff + 1. As we move through the array, we can maintain a window of the most recent indexDiff + 1 elements. For each new element, we only need to check if any element in our current window satisfies the valueDiff condition.

But how do we efficiently check if there's an element in the window that's within valueDiff of our current element? If we keep the window elements in a sorted structure, we can use binary search to quickly find elements within the range [nums[i] - valueDiff, nums[i] + valueDiff].

Think of it this way: for a current element nums[i], we want to find if there exists any element x in our window such that:

  • nums[i] - valueDiff <= x <= nums[i] + valueDiff

Using a sorted set (like a balanced BST), we can:

  1. Use binary search to find the smallest element that's >= nums[i] - valueDiff
  2. Check if this element is also <= nums[i] + valueDiff
  3. If yes, we found a valid pair!

As we slide the window forward:

  • Add the current element to the sorted set
  • Remove the element that's now outside the window (more than indexDiff positions behind)

This approach reduces our time complexity to O(n log k) where k is the window size (indexDiff + 1), because we perform log-time operations (insert, delete, search) for each element in the array.

Solution Approach

The solution uses a sliding window technique combined with an ordered set (SortedSet) to efficiently find pairs that satisfy both the index and value constraints.

Here's the step-by-step implementation:

  1. Initialize a SortedSet: We create an empty SortedSet to maintain elements within our sliding window in sorted order.

  2. Iterate through the array: For each element nums[i] at index i:

    a. Search for a valid pair:

    • Use bisect_left(v - valueDiff) to find the index of the smallest element in the sorted set that is >= nums[i] - valueDiff
    • If such an element exists (i.e., j < len(s)), check if it's also <= nums[i] + valueDiff
    • If both conditions are met, we've found a valid pair and return True

    b. Add current element: Insert nums[i] into the sorted set

    c. Maintain window size:

    • If we've processed more than indexDiff elements (i.e., i >= indexDiff), remove the element that's now outside the window
    • The element to remove is nums[i - indexDiff] - the one that's exactly indexDiff + 1 positions behind

  3. Return False: If we complete the iteration without finding a valid pair, return False

Key Implementation Details:

  • The window size is implicitly maintained at most indexDiff + 1 elements
  • bisect_left performs binary search in O(log k) time where k is the window size
  • The sorted set ensures we can efficiently find elements within the value range
  • By removing elements that fall outside the index window, we ensure we only compare elements that satisfy the indexDiff constraint

Time Complexity: O(n log k) where n is the array length and k = min(n, indexDiff + 1) Space Complexity: O(k) for storing at most k elements in the sorted set

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a concrete example:

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

We'll maintain a sliding window of size at most indexDiff + 1 = 3 using a SortedSet.

Step-by-step execution:

i = 0, nums[0] = 2:

  • SortedSet is empty []
  • Search for elements in range [2-1, 2+1] = [1, 3]
  • No elements in set, so no match found
  • Add 2 to set: [2]
  • Window size (1) ≤ indexDiff, no removal needed

i = 1, nums[1] = 3:

  • SortedSet: [2]
  • Search for elements in range [3-1, 3+1] = [2, 4]
  • Binary search finds 2 at index 0
  • Check: Is 2 ≤ 4? Yes! Valid pair found: (0, 1)
  • Return True

The algorithm found that indices 0 and 1 form a valid pair because:

  • abs(0 - 1) = 1 ≤ indexDiff = 2 ✓
  • abs(2 - 3) = 1 ≤ valueDiff = 1 ✓

Alternative scenario to show window maintenance:

Let's say we had nums = [1, 5, 9, 1, 5], indexDiff = 2, valueDiff = 3:

i = 0: SortedSet: [] → [1] i = 1: SortedSet: [1] → [1, 5] (no match in range [2, 8]) i = 2: SortedSet: [1, 5] → [1, 5, 9] (no match in range [6, 12]) i = 3: SortedSet: [1, 5, 9]

  • Search range [1-3, 1+3] = [-2, 4]
  • Binary search finds 1 at index 0
  • Check: Is 1 ≤ 4? Yes! Valid pair found: (0, 3)?
  • Wait! Index difference: abs(0 - 3) = 3 > indexDiff = 2
  • But our window only contains indices 1, 2, 3 (we need to remove nums[0])
  • Remove nums[0] = 1: SortedSet becomes [5, 9]
  • Search again in [5, 9] for range [-2, 4]: no match
  • Add nums[3] = 1: [1, 5, 9]

This demonstrates how the sliding window ensures we only compare elements within indexDiff distance.

Solution Implementation

1from typing import List
2from sortedcontainers import SortedSet
3
4class Solution:
5    def containsNearbyAlmostDuplicate(
6        self, nums: List[int], indexDiff: int, valueDiff: int
7    ) -> bool:
8        """
9        Check if there exist two distinct indices i and j such that:
10        - abs(i - j) <= indexDiff
11        - abs(nums[i] - nums[j]) <= valueDiff
12      
13        Args:
14            nums: List of integers
15            indexDiff: Maximum allowed index difference
16            valueDiff: Maximum allowed value difference
17          
18        Returns:
19            True if such pair exists, False otherwise
20        """
21        # Use a sorted set to maintain a sliding window of values
22        # The window size is at most indexDiff + 1 elements
23        sorted_window = SortedSet()
24      
25        for current_index, current_value in enumerate(nums):
26            # Find the smallest value in the window that is >= (current_value - valueDiff)
27            # This is the lower bound of the valid range [v - valueDiff, v + valueDiff]
28            lower_bound_index = sorted_window.bisect_left(current_value - valueDiff)
29          
30            # Check if there exists a value in the valid range
31            # If such value exists, it must be at lower_bound_index position
32            if (lower_bound_index < len(sorted_window) and 
33                sorted_window[lower_bound_index] <= current_value + valueDiff):
34                return True
35          
36            # Add current value to the sliding window
37            sorted_window.add(current_value)
38          
39            # Maintain sliding window size by removing the element that's now too far
40            # Remove the element at index (current_index - indexDiff) when window exceeds size
41            if current_index >= indexDiff:
42                sorted_window.remove(nums[current_index - indexDiff])
43      
44        return False
45
1class Solution {
2    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
3        // Use TreeSet to maintain a sliding window of elements with efficient range queries
4        // TreeSet provides O(log n) time for ceiling/floor operations
5        TreeSet<Long> slidingWindow = new TreeSet<>();
6      
7        // Iterate through each element in the array
8        for (int currentIndex = 0; currentIndex < nums.length; currentIndex++) {
9            // Find the smallest element in the window that is >= (nums[i] - valueDiff)
10            // This helps us check if there exists an element in range [nums[i] - valueDiff, nums[i] + valueDiff]
11            Long ceilingValue = slidingWindow.ceiling((long) nums[currentIndex] - (long) valueDiff);
12          
13            // If such element exists and it's <= (nums[i] + valueDiff), 
14            // then we found two elements satisfying the value difference condition
15            if (ceilingValue != null && ceilingValue <= (long) nums[currentIndex] + (long) valueDiff) {
16                return true;
17            }
18          
19            // Add current element to the sliding window
20            slidingWindow.add((long) nums[currentIndex]);
21          
22            // Maintain the sliding window size by removing the element that's now outside the index range
23            // This ensures all elements in the window satisfy the index difference constraint
24            if (currentIndex >= indexDiff) {
25                slidingWindow.remove((long) nums[currentIndex - indexDiff]);
26            }
27        }
28      
29        // No pair of elements found that satisfies both conditions
30        return false;
31    }
32}
33
1class Solution {
2public:
3    bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
4        // Use a sorted set to maintain a sliding window of elements
5        // The set stores elements within the index range constraint
6        set<long> windowSet;
7      
8        for (int i = 0; i < nums.size(); ++i) {
9            // Find the smallest element in the set that is >= (nums[i] - valueDiff)
10            // This helps us check if there's any element in range [nums[i] - valueDiff, nums[i] + valueDiff]
11            auto lowerBoundIter = windowSet.lower_bound(static_cast<long>(nums[i]) - valueDiff);
12          
13            // If such element exists and it's <= (nums[i] + valueDiff), 
14            // we found a pair satisfying both constraints
15            if (lowerBoundIter != windowSet.end() && 
16                *lowerBoundIter <= static_cast<long>(nums[i]) + valueDiff) {
17                return true;
18            }
19          
20            // Add current element to the sliding window
21            windowSet.insert(static_cast<long>(nums[i]));
22          
23            // Maintain sliding window size by removing element that's out of index range
24            // When i >= indexDiff, remove the element at position (i - indexDiff)
25            if (i >= indexDiff) {
26                windowSet.erase(static_cast<long>(nums[i - indexDiff]));
27            }
28        }
29      
30        return false;
31    }
32};
33
1/**
2 * Checks if array contains two distinct indices i and j such that:
3 * - abs(i - j) <= indexDiff
4 * - abs(nums[i] - nums[j]) <= valueDiff
5 * 
6 * Uses a sliding window with a balanced BST (TreeSet) to efficiently find values within range
7 */
8function containsNearbyAlmostDuplicate(
9    nums: number[],
10    indexDiff: number,
11    valueDiff: number,
12): boolean {
13    const treeSet = new TreeSet<number>();
14  
15    for (let i = 0; i < nums.length; ++i) {
16        // Find the smallest value >= (nums[i] - valueDiff)
17        const ceilValue = treeSet.ceil(nums[i] - valueDiff);
18      
19        // If such value exists and is <= (nums[i] + valueDiff), we found a valid pair
20        if (ceilValue != null && ceilValue <= nums[i] + valueDiff) {
21            return true;
22        }
23      
24        // Add current element to the set
25        treeSet.add(nums[i]);
26      
27        // Maintain sliding window of size indexDiff
28        if (i >= indexDiff) {
29            treeSet.delete(nums[i - indexDiff]);
30        }
31    }
32  
33    return false;
34}
35
36// Type definition for comparison function
37type Compare<T> = (lhs: T, rhs: T) => number;
38
39/**
40 * Red-Black Tree Node
41 * Color: 0 = RED, 1 = BLACK
42 */
43class RBTreeNode<T = number> {
44    data: T;
45    count: number; // For handling duplicates
46    left: RBTreeNode<T> | null;
47    right: RBTreeNode<T> | null;
48    parent: RBTreeNode<T> | null;
49    color: number; // 0 = RED, 1 = BLACK
50  
51    constructor(data: T) {
52        this.data = data;
53        this.left = null;
54        this.right = null;
55        this.parent = null;
56        this.color = 0; // New nodes are RED by default
57        this.count = 1;
58    }
59
60    /**
61     * Returns the sibling node of this node
62     */
63    sibling(): RBTreeNode<T> | null {
64        if (!this.parent) return null;
65        return this.isOnLeft() ? this.parent.right : this.parent.left;
66    }
67
68    /**
69     * Checks if this node is the left child of its parent
70     */
71    isOnLeft(): boolean {
72        return this === this.parent!.left;
73    }
74
75    /**
76     * Checks if this node has at least one red child
77     */
78    hasRedChild(): boolean {
79        return (
80            Boolean(this.left && this.left.color === 0) ||
81            Boolean(this.right && this.right.color === 0)
82        );
83    }
84}
85
86/**
87 * Red-Black Tree implementation
88 * Self-balancing BST with O(log n) operations
89 */
90class RBTree<T> {
91    root: RBTreeNode<T> | null;
92    lt: (left: T, right: T) => boolean; // Less than comparator
93  
94    constructor(compare: Compare<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0)) {
95        this.root = null;
96        this.lt = (left: T, right: T) => compare(left, right) < 0;
97    }
98
99    /**
100     * Left rotation around the given node
101     */
102    rotateLeft(pivotNode: RBTreeNode<T>): void {
103        const rightChild = pivotNode.right!;
104        pivotNode.right = rightChild.left;
105
106        if (pivotNode.right) {
107            pivotNode.right.parent = pivotNode;
108        }
109      
110        rightChild.parent = pivotNode.parent;
111
112        if (!pivotNode.parent) {
113            this.root = rightChild;
114        } else if (pivotNode === pivotNode.parent.left) {
115            pivotNode.parent.left = rightChild;
116        } else {
117            pivotNode.parent.right = rightChild;
118        }
119
120        rightChild.left = pivotNode;
121        pivotNode.parent = rightChild;
122    }
123
124    /**
125     * Right rotation around the given node
126     */
127    rotateRight(pivotNode: RBTreeNode<T>): void {
128        const leftChild = pivotNode.left!;
129        pivotNode.left = leftChild.right;
130
131        if (pivotNode.left) {
132            pivotNode.left.parent = pivotNode;
133        }
134      
135        leftChild.parent = pivotNode.parent;
136
137        if (!pivotNode.parent) {
138            this.root = leftChild;
139        } else if (pivotNode === pivotNode.parent.left) {
140            pivotNode.parent.left = leftChild;
141        } else {
142            pivotNode.parent.right = leftChild;
143        }
144
145        leftChild.right = pivotNode;
146        pivotNode.parent = leftChild;
147    }
148
149    /**
150     * Swaps colors between two nodes
151     */
152    swapColor(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
153        const tempColor = node1.color;
154        node1.color = node2.color;
155        node2.color = tempColor;
156    }
157
158    /**
159     * Swaps data between two nodes
160     */
161    swapData(node1: RBTreeNode<T>, node2: RBTreeNode<T>): void {
162        const tempData = node1.data;
163        node1.data = node2.data;
164        node2.data = tempData;
165    }
166
167    /**
168     * Fixes Red-Black Tree properties after insertion
169     */
170    fixAfterInsert(currentNode: RBTreeNode<T>): void {
171        let parentNode = null;
172        let grandParentNode = null;
173
174        // Continue fixing while violations exist
175        while (currentNode !== this.root && currentNode.color !== 1 && currentNode.parent?.color === 0) {
176            parentNode = currentNode.parent;
177            grandParentNode = currentNode.parent.parent;
178
179            // Case A: Parent is left child of grandparent
180            if (parentNode === grandParentNode?.left) {
181                const uncleNode = grandParentNode.right;
182
183                // Case 1: Uncle is red - only recoloring needed
184                if (uncleNode && uncleNode.color === 0) {
185                    grandParentNode.color = 0;
186                    parentNode.color = 1;
187                    uncleNode.color = 1;
188                    currentNode = grandParentNode;
189                } else {
190                    // Case 2: Current is right child - left rotation needed
191                    if (currentNode === parentNode.right) {
192                        this.rotateLeft(parentNode);
193                        currentNode = parentNode;
194                        parentNode = currentNode.parent;
195                    }
196
197                    // Case 3: Current is left child - right rotation needed
198                    this.rotateRight(grandParentNode);
199                    this.swapColor(parentNode!, grandParentNode);
200                    currentNode = parentNode!;
201                }
202            } else {
203                // Case B: Parent is right child of grandparent
204                const uncleNode = grandParentNode!.left;
205
206                // Case 1: Uncle is red - only recoloring needed
207                if (uncleNode != null && uncleNode.color === 0) {
208                    grandParentNode!.color = 0;
209                    parentNode.color = 1;
210                    uncleNode.color = 1;
211                    currentNode = grandParentNode!;
212                } else {
213                    // Case 2: Current is left child - right rotation needed
214                    if (currentNode === parentNode.left) {
215                        this.rotateRight(parentNode);
216                        currentNode = parentNode;
217                        parentNode = currentNode.parent;
218                    }
219
220                    // Case 3: Current is right child - left rotation needed
221                    this.rotateLeft(grandParentNode!);
222                    this.swapColor(parentNode!, grandParentNode!);
223                    currentNode = parentNode!;
224                }
225            }
226        }
227      
228        // Root must always be black
229        this.root!.color = 1;
230    }
231
232    /**
233     * Deletes one occurrence of the value
234     */
235    delete(value: T): boolean {
236        const node = this.find(value);
237        if (!node) return false;
238      
239        node.count--;
240        if (!node.count) {
241            this.deleteNode(node);
242        }
243        return true;
244    }
245
246    /**
247     * Deletes all occurrences of the value
248     */
249    deleteAll(value: T): boolean {
250        const node = this.find(value);
251        if (!node) return false;
252        this.deleteNode(node);
253        return true;
254    }
255
256    /**
257     * Deletes a node from the tree and maintains Red-Black properties
258     */
259    deleteNode(nodeToDelete: RBTreeNode<T>): void {
260        // Helper function to find BST replacement node
261        function findBSTReplacement(node: RBTreeNode<T>): RBTreeNode<T> | null {
262            // Node has 2 children - find inorder successor
263            if (node.left && node.right) {
264                return findSuccessor(node.right);
265            }
266            // Node is leaf
267            if (!node.left && !node.right) return null;
268            // Node has single child
269            return node.left ?? node.right;
270        }
271      
272        // Helper function to find inorder successor
273        function findSuccessor(node: RBTreeNode<T>): RBTreeNode<T> {
274            let current = node;
275            while (current.left) {
276                current = current.left;
277            }
278            return current;
279        }
280
281        const replacementNode = findBSTReplacement(nodeToDelete);
282        const bothBlack = (replacementNode === null || replacementNode.color === 1) && nodeToDelete.color === 1;
283        const parentNode = nodeToDelete.parent!;
284
285        if (!replacementNode) {
286            // Node to delete is a leaf
287            if (nodeToDelete === this.root) {
288                this.root = null;
289            } else {
290                if (bothBlack) {
291                    // Both nodes are black - fix double black
292                    this.fixDoubleBlack(nodeToDelete);
293                } else {
294                    // One node is red - make sibling red if exists
295                    if (nodeToDelete.sibling()) {
296                        nodeToDelete.sibling()!.color = 0;
297                    }
298                }
299                // Remove node from parent
300                if (nodeToDelete.isOnLeft()) {
301                    parentNode.left = null;
302                } else {
303                    parentNode.right = null;
304                }
305            }
306            return;
307        }
308
309        if (!nodeToDelete.left || !nodeToDelete.right) {
310            // Node has exactly one child
311            if (nodeToDelete === this.root) {
312                // Replace root with child
313                nodeToDelete.data = replacementNode.data;
314                nodeToDelete.left = null;
315                nodeToDelete.right = null;
316            } else {
317                // Replace node with child
318                if (nodeToDelete.isOnLeft()) {
319                    parentNode.left = replacementNode;
320                } else {
321                    parentNode.right = replacementNode;
322                }
323                replacementNode.parent = parentNode;
324              
325                if (bothBlack) {
326                    this.fixDoubleBlack(replacementNode);
327                } else {
328                    replacementNode.color = 1;
329                }
330            }
331            return;
332        }
333
334        // Node has two children - swap with successor and recurse
335        this.swapData(replacementNode, nodeToDelete);
336        this.deleteNode(replacementNode);
337    }
338
339    /**
340     * Fixes double black violation after deletion
341     */
342    fixDoubleBlack(node: RBTreeNode<T>): void {
343        if (node === this.root) return;
344
345        const siblingNode = node.sibling();
346        const parentNode = node.parent!;
347      
348        if (!siblingNode) {
349            // No sibling - push double black up
350            this.fixDoubleBlack(parentNode);
351        } else {
352            if (siblingNode.color === 0) {
353                // Sibling is red
354                parentNode.color = 0;
355                siblingNode.color = 1;
356              
357                if (siblingNode.isOnLeft()) {
358                    this.rotateRight(parentNode);
359                } else {
360                    this.rotateLeft(parentNode);
361                }
362              
363                this.fixDoubleBlack(node);
364            } else {
365                // Sibling is black
366                if (siblingNode.hasRedChild()) {
367                    // Sibling has at least one red child
368                    if (siblingNode.left && siblingNode.left.color === 0) {
369                        if (siblingNode.isOnLeft()) {
370                            // Left-Left case
371                            siblingNode.left.color = siblingNode.color;
372                            siblingNode.color = parentNode.color;
373                            this.rotateRight(parentNode);
374                        } else {
375                            // Right-Left case
376                            siblingNode.left.color = parentNode.color;
377                            this.rotateRight(siblingNode);
378                            this.rotateLeft(parentNode);
379                        }
380                    } else {
381                        if (siblingNode.isOnLeft()) {
382                            // Left-Right case
383                            siblingNode.right!.color = parentNode.color;
384                            this.rotateLeft(siblingNode);
385                            this.rotateRight(parentNode);
386                        } else {
387                            // Right-Right case
388                            siblingNode.right!.color = siblingNode.color;
389                            siblingNode.color = parentNode.color;
390                            this.rotateLeft(parentNode);
391                        }
392                    }
393                    parentNode.color = 1;
394                } else {
395                    // Sibling has two black children
396                    siblingNode.color = 0;
397                    if (parentNode.color === 1) {
398                        this.fixDoubleBlack(parentNode);
399                    } else {
400                        parentNode.color = 1;
401                    }
402                }
403            }
404        }
405    }
406
407    /**
408     * Inserts a value into the tree
409     */
410    insert(data: T): boolean {
411        // Find insertion position
412        let parentNode = this.root;
413        while (parentNode) {
414            if (this.lt(data, parentNode.data)) {
415                if (!parentNode.left) break;
416                parentNode = parentNode.left;
417            } else if (this.lt(parentNode.data, data)) {
418                if (!parentNode.right) break;
419                parentNode = parentNode.right;
420            } else {
421                // Value already exists - increment count
422                parentNode.count++;
423                return false;
424            }
425        }
426
427        // Create and insert new node
428        const newNode = new RBTreeNode(data);
429        if (!parentNode) {
430            this.root = newNode;
431        } else if (this.lt(newNode.data, parentNode.data)) {
432            parentNode.left = newNode;
433        } else if (this.lt(parentNode.data, newNode.data)) {
434            parentNode.right = newNode;
435        } else {
436            parentNode.count++;
437            return false;
438        }
439      
440        newNode.parent = parentNode;
441        this.fixAfterInsert(newNode);
442        return true;
443    }
444
445    /**
446     * Finds a node with the given value
447     */
448    find(data: T): RBTreeNode<T> | null {
449        let currentNode = this.root;
450        while (currentNode) {
451            if (this.lt(data, currentNode.data)) {
452                currentNode = currentNode.left;
453            } else if (this.lt(currentNode.data, data)) {
454                currentNode = currentNode.right;
455            } else {
456                return currentNode;
457            }
458        }
459        return null;
460    }
461
462    /**
463     * Generator for in-order traversal
464     */
465    *inOrder(rootNode: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
466        if (!rootNode) return;
467        yield* this.inOrder(rootNode.left!);
468        yield rootNode.data;
469        yield* this.inOrder(rootNode.right!);
470    }
471
472    /**
473     * Generator for reverse in-order traversal
474     */
475    *reverseInOrder(rootNode: RBTreeNode<T> = this.root!): Generator<T, undefined, void> {
476        if (!rootNode) return;
477        yield* this.reverseInOrder(rootNode.right!);
478        yield rootNode.data;
479        yield* this.reverseInOrder(rootNode.left!);
480    }
481}
482
483/**
484 * TreeSet - A sorted set implementation using Red-Black Tree
485 * Maintains unique elements in sorted order
486 */
487class TreeSet<T = number> {
488    private _size: number;
489    private tree: RBTree<T>;
490    private compare: Compare<T>;
491  
492    constructor(
493        collection: T[] | Compare<T> = [],
494        compare: Compare<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0),
495    ) {
496        // Handle overloaded constructor
497        if (typeof collection === 'function') {
498            compare = collection;
499            collection = [];
500        }
501      
502        this._size = 0;
503        this.compare = compare;
504        this.tree = new RBTree(compare);
505      
506        // Initialize with collection
507        for (const value of collection) {
508            this.add(value);
509        }
510    }
511
512    /**
513     * Returns the number of elements in the set
514     */
515    size(): number {
516        return this._size;
517    }
518
519    /**
520     * Checks if the set contains a value
521     */
522    has(value: T): boolean {
523        return !!this.tree.find(value);
524    }
525
526    /**
527     * Adds a value to the set
528     */
529    add(value: T): boolean {
530        const wasSuccessful = this.tree.insert(value);
531        if (wasSuccessful) {
532            this._size++;
533        }
534        return wasSuccessful;
535    }
536
537    /**
538     * Removes a value from the set
539     */
540    delete(value: T): boolean {
541        const wasDeleted = this.tree.deleteAll(value);
542        if (wasDeleted) {
543            this._size--;
544        }
545        return wasDeleted;
546    }
547
548    /**
549     * Returns the smallest value >= the given value
550     */
551    ceil(value: T): T | undefined {
552        let currentNode = this.tree.root;
553        let result = null;
554      
555        while (currentNode) {
556            if (this.compare(currentNode.data, value) >= 0) {
557                result = currentNode;
558                currentNode = currentNode.left;
559            } else {
560                currentNode = currentNode.right;
561            }
562        }
563      
564        return result?.data;
565    }
566
567    /**
568     * Returns the largest value <= the given value
569     */
570    floor(value: T): T | undefined {
571        let currentNode = this.tree.root;
572        let result = null;
573      
574        while (currentNode) {
575            if (this.compare(value, currentNode.data) >= 0) {
576                result = currentNode;
577                currentNode = currentNode.right;
578            } else {
579                currentNode = currentNode.left;
580            }
581        }
582      
583        return result?.data;
584    }
585
586    /**
587     * Returns the smallest value > the given value
588     */
589    higher(value: T): T | undefined {
590        let currentNode = this.tree.root;
591        let result = null;
592      
593        while (currentNode) {
594            if (this.compare(value, currentNode.data) < 0) {
595                result = currentNode;
596                currentNode = currentNode.left;
597            } else {
598                currentNode = currentNode.right;
599            }
600        }
601      
602        return result?.data;
603    }
604
605    /**
606     * Returns the largest value < the given value
607     */
608    lower(value: T): T | undefined {
609        let currentNode = this.tree.root;
610        let result = null;
611      
612        while (currentNode) {
613            if (this.compare(currentNode.data, value) < 0) {
614                result = currentNode;
615                currentNode = currentNode.right;
616            } else {
617                currentNode = currentNode.left;
618            }
619        }
620      
621        return result?.data;
622    }
623
624    /**
625     * Returns the smallest element in the set
626     */
627    first(): T | undefined {
628        return this.tree.inOrder().next().value;
629    }
630
631    /**
632     * Returns the largest element in the set
633     */
634    last(): T | undefined {
635        return this.tree.reverseInOrder().next().value;
636    }
637
638    /**
639     * Removes and returns the smallest element
640     */
641    shift(): T | undefined {
642        const firstElement = this.first();
643        if (firstElement === undefined) return undefined;
644        this.delete(firstElement);
645        return firstElement;
646    }
647
648    /**
649     * Removes and returns the largest element
650     */
651    pop(): T | undefined {
652        const lastElement = this.last();
653        if (lastElement === undefined) return undefined;
654        this.delete(lastElement);
655        return lastElement;
656    }
657
658    /**
659     * Iterator protocol implementation
660     */
661    *[Symbol.iterator](): Generator<T, void, void> {
662        yield* this.values();
663    }
664
665    /**
666     * Returns an iterator over the keys (same as values for a set)
667     */
668    *keys(): Generator<T, void, void> {
669        yield* this.values();
670    }
671
672    /**
673     * Returns an iterator over the values in ascending order
674     */
675    *values(): Generator<T, undefined, void> {
676        yield* this.tree.inOrder();
677        return undefined;
678    }
679
680    /**
681     * Returns an iterator over the values in descending order
682     */
683    *rvalues(): Generator<T, undefined, void> {
684        yield* this.tree.reverseInOrder();
685        return undefined;
686    }
687}
688
689/**
690 * TreeMultiSet - A sorted multiset implementation using Red-Black Tree
691 * Allows duplicate elements while maintaining sorted order
692 */
693class TreeMultiSet<T = number> {
694    private _size: number;
695    private tree: RBTree<T>;
696    private compare: Compare<T>;
697  
698    constructor(
699        collection: T[] | Compare<T> = [],
700        compare: Compare<T> = (left: T, right: T) => (left < right ? -1 : left > right ? 1 : 0),
701    ) {
702        // Handle overloaded constructor
703        if (typeof collection === 'function') {
704            compare = collection;
705            collection = [];
706        }
707      
708        this._size = 0;
709        this.compare = compare;
710        this.tree = new RBTree(compare);
711      
712        // Initialize with collection
713        for (const value of collection) {
714            this.add(value);
715        }
716    }
717
718    /**
719     * Returns the total number of elements (including duplicates)
720     */
721    size(): number {
722        return this._size;
723    }
724
725    /**
726     * Checks if the multiset contains at least one occurrence of the value
727     */
728    has(value: T): boolean {
729        return !!this.tree.find(value);
730    }
731
732    /**
733     * Adds a value to the multiset
734     */
735    add(value: T): boolean {
736        this.tree.insert(value);
737        this._size++;
738        return true;
739    }
740
741    /**
742     * Removes one occurrence of the value
743     */
744    delete(value: T): boolean {
745        const wasSuccessful = this.tree.delete(value);
746        if (wasSuccessful) {
747            this._size--;
748        }
749        return wasSuccessful;
750    }
751
752    /**
753     * Returns the count of occurrences of the value
754     */
755    count(value: T): number {
756        const node = this.tree.find(value);
757        return node ? node.count : 0;
758    }
759
760    /**
761     * Returns the smallest value >= the given value
762     */
763    ceil(value: T): T | undefined {
764        let currentNode = this.tree.root;
765        let result = null;
766      
767        while (currentNode) {
768            if (this.compare(currentNode.data, value) >= 0) {
769                result = currentNode;
770                currentNode = currentNode.left;
771            } else {
772                currentNode = currentNode.right;
773            }
774        }
775      
776        return result?.data;
777    }
778
779    /**
780     * Returns the largest value <= the given value
781     */
782    floor(value: T): T | undefined {
783        let currentNode = this.tree.root;
784        let result = null;
785      
786        while (currentNode) {
787            if (this.compare(value, currentNode.data) >= 0) {
788                result = currentNode;
789                currentNode = currentNode.right;
790            } else {
791                currentNode = currentNode.left;
792            }
793        }
794      
795        return result?.data;
796    }
797
798    /**
799     * Returns the smallest value > the given value
800     */
801    higher(value: T): T | undefined {
802        let currentNode = this.tree.root;
803        let result = null;
804      
805        while (currentNode) {
806            if (this.compare(value, currentNode.data) < 0) {
807                result = currentNode;
808                currentNode = currentNode.left;
809            } else {
810                currentNode = currentNode.right;
811            }
812        }
813      
814        return result?.data;
815    }
816
817    /**
818     * Returns the largest value < the given value
819     */
820    lower(value: T): T | undefined {
821        let currentNode = this.tree.root;
822        let result = null;
823      
824        while (currentNode) {
825            if (this.compare(currentNode.data, value) < 0) {
826                result = currentNode;
827                currentNode = currentNode.right;
828            } else {
829                currentNode = currentNode.left;
830            }
831        }
832      
833        return result?.data;
834    }
835
836    /**
837     * Returns the smallest element in the multiset
838     */
839    first(): T | undefined {
840        return this.tree.inOrder().next().value;
841    }
842
843    /**
844     * Returns the largest element in the multiset
845     */
846    last(): T | undefined {
847        return this.tree.reverseInOrder().next().value;
848    }
849
850    /**
851     * Removes and returns one occurrence of the smallest element
852     */
853    shift(): T | undefined {
854        const firstElement = this.first();
855        if (firstElement === undefined) return undefined;
856        this.delete(firstElement);
857        return firstElement;
858    }
859
860    /**
861     * Removes and returns one occurrence of the largest element
862     */
863    pop(): T | undefined {
864        const lastElement = this.last();
865        if (lastElement === undefined) return undefined;
866        this.delete(lastElement);
867        return lastElement;
868    }
869
870    /**
871     * Iterator protocol implementation
872     */
873    *[Symbol.iterator](): Generator<T, void, void> {
874        yield* this.values();
875    }
876
877    /**
878     * Returns an iterator over all occurrences (same as values)
879     */
880    *keys(): Generator<T, void, void> {
881        yield* this.values();
882    }
883
884    /**
885     * Returns an iterator over all occurrences in ascending order
886     */
887    *values(): Generator<T, undefined, void> {
888        for (const value of this.tree.inOrder()) {
889            let occurrences = this.count(value);
890            while (occurrences--) {
891                yield value;
892            }
893        }
894        return undefined;
895    }
896
897    /**
898     * Returns an iterator over all occurrences in descending order
899     */
900    *rvalues(): Generator<T, undefined, void> {
901        for (const value of this.tree.reverseInOrder()) {
902            let occurrences = this.count(value);
903            while (occurrences--) {
904                yield value;
905            }
906        }
907        return undefined;
908    }
909}
910

Time and Space Complexity

Time Complexity: O(n × log k), where n is the length of the array nums and k is the indexDiff parameter.

  • The outer loop iterates through all n elements in the array.
  • For each element, we perform:
    • bisect_left() operation on the SortedSet: O(log k) time, since the set maintains at most k+1 elements due to the sliding window constraint.
    • Comparison and potential return: O(1) time.
    • add() operation to insert the current element: O(log k) time.
    • remove() operation when i >= indexDiff: O(log k) time to maintain the sliding window of size k+1.
  • Since we perform O(log k) operations for each of the n elements, the total time complexity is O(n × log k).

Space Complexity: O(min(n, k)) or more precisely O(min(n, indexDiff + 1))

  • The SortedSet s maintains a sliding window of elements.
  • At any point, the set contains at most indexDiff + 1 elements (elements within the current window).
  • In the worst case where indexDiff >= n-1, the set could contain all n elements.
  • Therefore, the space complexity is O(min(n, k)) where k represents indexDiff.

Common Pitfalls

1. Integer Overflow in Value Comparisons

When dealing with large integers, calculating current_value - valueDiff or current_value + valueDiff can cause integer overflow in languages with fixed integer sizes. In Python this isn't an issue due to arbitrary precision integers, but in languages like Java or C++, this can lead to incorrect results.

Example problematic scenario:

  • current_value = Integer.MAX_VALUE
  • valueDiff = 10
  • current_value + valueDiff would overflow

Solution: Instead of computing sorted_window[j] <= current_value + valueDiff, rearrange to avoid overflow:

# Instead of: sorted_window[j] <= current_value + valueDiff
# Use: sorted_window[j] - current_value <= valueDiff

2. Off-by-One Error in Window Size Management

A frequent mistake is incorrectly managing when to remove elements from the sliding window. The condition should be current_index >= indexDiff, not current_index > indexDiff.

Why this matters:

  • At index indexDiff, we have indexDiff + 1 elements in our window
  • The element at index 0 is now exactly indexDiff positions away from current position
  • We need to remove it to maintain the constraint

Correct implementation:

# Remove element when we've processed indexDiff + 1 elements
if current_index >= indexDiff:
    sorted_window.remove(nums[current_index - indexDiff])

3. Using Regular Set Instead of SortedSet

Using a regular Python set or HashSet won't work because we need to efficiently find elements within a value range. Binary search requires sorted order.

Wrong approach:

window = set()  # Regular set doesn't maintain order
# Can't efficiently find elements in range [v - valueDiff, v + valueDiff]

Correct approach:

from sortedcontainers import SortedSet
sorted_window = SortedSet()  # Maintains sorted order for binary search

4. Incorrect Boundary Check After Binary Search

After finding the lower bound index, forgetting to check if it's within bounds can cause index errors.

Problematic code:

lower_bound_index = sorted_window.bisect_left(current_value - valueDiff)
# Missing bounds check!
if sorted_window[lower_bound_index] <= current_value + valueDiff:
    return True

Correct code:

lower_bound_index = sorted_window.bisect_left(current_value - valueDiff)
if (lower_bound_index < len(sorted_window) and 
    sorted_window[lower_bound_index] <= current_value + valueDiff):
    return True

5. Edge Case: indexDiff = 0

When indexDiff = 0, we're looking for duplicate values at the same index, which is impossible since i != j. The algorithm handles this correctly, but it's worth noting that it will always return False unless there's an implementation error.

Test case to verify:

nums = [1, 1, 1]
indexDiff = 0
valueDiff = 0
# Should return False (can't have i != j with abs(i - j) <= 0)
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Sliding Window Maximum

https assets algo monster cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in the window The window

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More