220. Contains Duplicate III

HardArrayBucket SortOrdered SetSortingSliding Window

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 and j are different (i != j).
The absolute difference between the indices i and j does not exceed indexDiff (abs(i - j) <= indexDiff).
The absolute difference between the values at indices i and j does not exceed valueDiff (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 array nums.
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) using bisect_left.
Once we have that element, if there is one within the valid range v + valueDiff, then we have found indices i and j that satisfy both conditions for indexDiff and valueDiff.
If we haven't returned true yet, we add the current element v 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 the indexDiff based on the current index i, we remove the element from the sorted set that corresponds to the index i - 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 called s, which will hold the candidates that could potentially form a valid pair with the current element in terms of valueDiff.
We then enumerate over our input array nums using a for loop, giving us both the index i and the value v at each iteration.
For the current value v, we want to find if there is a value in our sorted set s that does not differ from v by more than valueDiff. To achieve this, we perform a binary search in the sorted set for the left boundary v - valueDiff using the bisect_left function. This returns the index j of the first element in s that is not less than v - valueDiff.
After finding this index j, we check if it is within the bounds of the sorted set and if the element at this index s[j] does not exceed v + valueDiff. If these conditions are met, we have found a pair that satisfies the valueDiff condition, and we return true.
If no valid pair is found yet, we add the current value v to the sorted set s using add() 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 from s that are too far from the current index i. Specifically, if i >= indexDiff, we remove the element that corresponds to the index i - indexDiff using the remove() method.
Finally, if the loop finishes without returning true, we conclude that no valid pair exists and return false.

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 Evaluator

Example 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 as s.
We iterate over each value v in nums along with its index i.
At index i = 0, value v = 1.
- There are no elements in s yet, so we add v to s. Set s now contains [1].
At index i = 1, value v = 2.
- We use binary search to check for v - valueDiff = 1 in s.
- The smallest element greater than or equal to 1 is 1.
- It is within valueDiff from 2. However, since s has only one element, which is from the current index, we don't consider it.
- We add v to s. Set s now contains [1, 2].
At index i = 2, value v = 3.
- We use binary search to check for v - valueDiff = 2 in s.
- The smallest element greater than or equal to 2 is 2.
- It is within valueDiff from 3.
- We return true since we found 2 which is within valueDiff from 3 and whose index 1 is within indexDiff from the current index 2.

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): The bisect_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 a SortedSet 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know