220. Contains Duplicate III
Problem Description
This problem requires us to determine if there exist two indices i
and j
in an integer array nums
such that:
- The indices
i
andj
are different (i != j
). - The absolute difference between the indices
i
andj
does not exceedindexDiff
(abs(i - j) <= indexDiff
). - The absolute difference between the values at indices
i
andj
does not exceedvalueDiff
(abs(nums[i] - nums[j]) <= valueDiff
).
We must return true
if such a pair of indices exists and false
otherwise.
The challenge lies in doing this efficiently, as the brute force approach of checking all pairs would take too much time for large arrays.
Intuition
The key to solving this problem efficiently is to maintain a set of elements from nums
that have recently been processed and fall within the indexDiff
range of the current index. Since we need to check the valueDiff
condition efficiently, a sorted set is used.
Here's the intuition process to arrive at the solution:
-
We initialize a sorted set
s
which helps to access elements in sorted order and provides efficient operations to find if an element exists within a certain range. -
We then iterate through each element
v
in the arraynums
. -
For each element, we find the smallest element in the sorted set that would satisfy the
valueDiff
condition. This is done by searching for the left boundary (v - valueDiff
) usingbisect_left
. -
Once we have that element, if there is one within the valid range
v + valueDiff
, then we have found indicesi
andj
that satisfy both conditions forindexDiff
andvalueDiff
. -
If we haven't returned
true
yet, we add the current elementv
to the sorted set. This is because it might be a part of a valid pair with a later element. -
We then check the size of the sorted set relative to the
indexDiff
. If the set size indicates that an element is too old and cannot satisfy theindexDiff
based on the current indexi
, we remove the element from the sorted set that corresponds to the indexi - indexDiff
. -
If we complete the iteration without finding a valid pair, we return
false
, indicating no such pair exists.
By using a sorted set and keeping track of the indices, we ensure that we are always looking at a window of indexDiff
for potential pairs, and checking for valueDiff
within this window is efficient, thanks to the sorted nature of the set.
Learn more about Sorting and Sliding Window patterns.
Solution Approach
The solution provided uses the SortedSet
data structure from the sortedcontainers
Python module. This data structure maintains its elements in ascending order and supports fast insertion, deletion, and queries, which are essential to our approach.
Let's break down the algorithm step-by-step:
-
We begin by creating an empty
SortedSet
calleds
, which will hold the candidates that could potentially form a valid pair with the current element in terms ofvalueDiff
. -
We then enumerate over our input array
nums
using a for loop, giving us both the indexi
and the valuev
at each iteration. -
For the current value
v
, we want to find if there is a value in our sorted sets
that does not differ fromv
by more thanvalueDiff
. To achieve this, we perform a binary search in the sorted set for the left boundaryv - valueDiff
using thebisect_left
function. This returns the indexj
of the first element ins
that is not less thanv - valueDiff
. -
After finding this index
j
, we check if it is within the bounds of the sorted set and if the element at this indexs[j]
does not exceedv + valueDiff
. If these conditions are met, we have found a pair that satisfies thevalueDiff
condition, and we returntrue
. -
If no valid pair is found yet, we add the current value
v
to the sorted sets
usingadd()
method because it may become a part of a valid pair with a later element in the array. -
To maintain the
indexDiff
condition, we need to remove elements froms
that are too far from the current indexi
. Specifically, ifi >= indexDiff
, we remove the element that corresponds to the indexi - indexDiff
using theremove()
method. -
Finally, if the loop finishes without returning
true
, we conclude that no valid pair exists and returnfalse
.
This algorithm works effectively because the SortedSet
maintains the order of elements at all times, so checking for the valueDiff
condition is very efficient, and by using the index conditions, we keep updating the set so that it only contains relevant elements that could form a valid pair considering the indexDiff
.
Overall, the use of SortedSet
optimizes the brute force approach which would be clear when matching face to face with a potentially large nums
array, where a less efficient process would result in a time complexity that is too high.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach:
Given nums = [1, 2, 3, 1]
, indexDiff = 3
, and valueDiff = 1
.
-
We start with an empty
SortedSet
, which we denote ass
. -
We iterate over each value
v
innums
along with its indexi
. -
At index
i = 0
, valuev = 1
.- There are no elements in
s
yet, so we addv
tos
. Sets
now contains[1]
.
- There are no elements in
-
At index
i = 1
, valuev = 2
.- We use binary search to check for
v - valueDiff = 1
ins
. - The smallest element greater than or equal to
1
is1
. - It is within
valueDiff
from2
. However, sinces
has only one element, which is from the current index, we don't consider it. - We add
v
tos
. Sets
now contains[1, 2]
.
- We use binary search to check for
-
At index
i = 2
, valuev = 3
.- We use binary search to check for
v - valueDiff = 2
ins
. - The smallest element greater than or equal to
2
is2
. - It is within
valueDiff
from3
. - We return
true
since we found2
which is withinvalueDiff
from3
and whose index1
is withinindexDiff
from the current index2
.
- We use binary search to check for
Therefore, the conditions are satisfied and the function would return true
.
Solution Implementation
1from sortedcontainers import SortedSet
2from typing import List
3
4class Solution:
5 def containsNearbyAlmostDuplicate(self, nums: List[int], index_diff: int, value_diff: int) -> bool:
6 # Create a SortedSet to maintain a sorted list of numbers
7 # we have seen so far.
8 sorted_set = SortedSet()
9
10 # Loop through each number in the given list along with its index
11 for i, num in enumerate(nums):
12 # Find the left boundary where number becomes greater than or equal to num-value_diff.
13 left_boundary_index = sorted_set.bisect_left(num - value_diff)
14
15 # Check if there exists a value within the range [num-value_diff, num+value_diff]
16 # inside our SortedSet.
17 if left_boundary_index < len(sorted_set) and sorted_set[left_boundary_index] <= num + value_diff:
18 return True # If found, return True as the condition is satisfied.
19
20 # If not found, add the current number to the SortedSet.
21 sorted_set.add(num)
22
23 # If the SortedSet's size exceeds the allowed indexDiff,
24 # we remove the oldest element from the SortedSet to maintain the sliding window constraint.
25 if i >= index_diff:
26 sorted_set.remove(nums[i - index_diff])
27
28 # If we never return True within the loop, there is no such pair which satisfies the condition,
29 # hence we return False.
30 return False
31
1class Solution {
2 public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
3 // Use TreeSet to maintain a sorted set.
4 TreeSet<Long> sortedSet = new TreeSet<>();
5
6 // Iterate through the array of numbers.
7 for (int i = 0; i < nums.length; ++i) {
8 // Try finding a value in the set within the range of (value - valueDiff) and (value + valueDiff).
9 Long floorValue = sortedSet.ceiling((long) nums[i] - (long) valueDiff);
10 if (floorValue != null && floorValue <= (long) nums[i] + (long) valueDiff) {
11 // If such a value is found, return true.
12 return true;
13 }
14
15 // Add the current number to the sorted set.
16 sortedSet.add((long) nums[i]);
17
18 // If the sorted set size exceeded the allowed index difference, remove the oldest value.
19 if (i >= indexDiff) {
20 sortedSet.remove((long) nums[i - indexDiff]);
21 }
22 }
23
24 // Return false if no such pair is found in the set.
25 return false;
26 }
27}
28
1#include <vector>
2#include <set>
3using namespace std;
4
5class Solution {
6public:
7 // Function to determine if the array contains nearby almost duplicate elements
8 bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
9 // Initialize a set to keep track of values in the window defined by indexDiff
10 set<long> windowSet;
11 for (int i = 0; i < nums.size(); ++i) {
12 // Find the lower bound of the acceptable value difference
13 auto lower = windowSet.lower_bound((long) nums[i] - valueDiff);
14 // If an element is found within the value range, return true
15 if (lower != windowSet.end() && *lower <= (long) nums[i] + valueDiff) {
16 return true;
17 }
18 // Insert the current element into the set
19 windowSet.insert((long) nums[i]);
20 // If our window exceeds the permitted index difference, remove the oldest value
21 if (i >= indexDiff) {
22 windowSet.erase((long) nums[i - indexDiff]);
23 }
24 }
25 // If no duplicates are found in the given range, return false
26 return false;
27 }
28};
29
1// Define the interfaces and global variables
2interface ICompare<T> {
3 (lhs: T, rhs: T): number;
4}
5
6interface IRBTreeNode<T> {
7 data: T;
8 count: number;
9 left: IRBTreeNode<T> | null;
10 right: IRBTreeNode<T> | null;
11 parent: IRBTreeNode<T> | null;
12 color: number;
13 // Methods like sibling, isOnLeft, and hasRedChild are removed as they should be part of the class
14}
15
16const RED = 0;
17const BLACK = 1;
18let root: IRBTreeNode<any> | null = null; // Global tree root
19
20// Define global methods
21function createNode<T>(data: T): IRBTreeNode<T> {
22 return {
23 data: data,
24 count: 1,
25 left: null,
26 right: null,
27 parent: null,
28 color: RED // Newly created nodes are red
29 };
30}
31
32// Example usage of creating a node
33const node = createNode(10);
34
35// Define the rotate functions
36function rotateLeft<T>(pt: IRBTreeNode<T>): void {
37 if (!pt.right) {
38 throw new Error("Cannot rotate left without a right child");
39 }
40 let right = pt.right;
41 pt.right = right.left;
42 if (pt.right) pt.right.parent = pt;
43
44 right.parent = pt.parent;
45 if (!pt.parent) {
46 root = right;
47 }
48 // ... Rest of the rotateLeft logic
49}
50
51function rotateRight<T>(pt: IRBTreeNode<T>): void {
52 // ... Implement rotateRight logic
53}
54
55// Define other necessary functions like find, insert, delete, etc...
56
Time and Space Complexity
Time Complexity
The time complexity of the given code primarily depends on the number of iterations over the nums
array, the operations performed with the SortedSet
, and maintaining the indexDiff
constraint. The main operations within the loop are:
- Checking for a nearby almost duplicate (
bisect_left
and comparison): Thebisect_left
method in a sorted set is typically O(log n), where n is the number of elements in the set. - Adding a new element to the sorted set (
s.add(v)
): Inserting an element into aSortedSet
is also O(log n) as it keeps the set sorted. - Removing the oldest element when the
indexDiff
is exceeded (s.remove(nums[i - indexDiff])
): This is O(log n) to find the element and O(n) to remove it because removing an element from a sorted set can require shifting all elements to the right of the removed element.
Since each of these operations is called once per iteration and the remove
operation has the higher complexity of O(n), the time complexity per iteration is O(n). However, since the size of the sorted set is capped by the indexDiff
, let’s use k to denote indexDiff
as the maximum number of elements the sorted set can contain. The complexity now becomes O(k) for insertion and removal, and the complexity of bisect_left
is O(log k). Therefore, the time complexity is O(n * log k) where n is the length of the input array and k is indexDiff
.
Space Complexity
The space complexity is determined by the maximum size of the sorted set s
, which can grow up to the largest indexDiff
. Therefore, the space complexity is O(k), where k is the maximum number of entries in the SortedSet
, which is bounded by indexDiff
.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
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
https algomonster s3 us east 2 amazonaws com 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
LeetCode 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 we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.