Summary

This article is for intermediate readers. It introduces the following ideas:\nBinary Search Tree, HashMap, and Buckets.

Solutions

Approach #1 (Naive Linear Search) [Time Limit Exceeded]

Intuition

Compare each element with the previous $$k$$ elements and see if their difference is at most $$t$$ .

Algorithm

This problem requires us to find $$i$$ and $$j$$ such that the following conditions are satisfied:

\n
1. $$\\bigl| i-j \\bigr| \\le k$$ \n
\n
2. $$\\bigl| \\mathrm{nums}[i] - \\mathrm{nums}[j] \\bigr| \\le t$$ \n
\n

The naive approach is the same as Approach #1 in Contains Duplicate II solution, which keeps a virtual sliding window that holds the newest $$k$$ elements. In this way, Condition 1 above is always satisfied. We then check if Condition 2 is also satisfied by applying linear search.

Java

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {\n    for (int i = 0; i < nums.length; ++i) {\n        for (int j = Math.max(i - k, 0); j < i; ++j) {\n            if (Math.abs(nums[i] - nums[j]) <= t) return true;\n        }\n    }\n    return false;\n}\n// Time limit exceeded.\n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n \\min(k,n))$$ .\nIt costs $$O(\\min(k, n))$$ time for each linear search. Note that we do at most $$n$$ comparisons in one search even if $$k$$ can be larger than $$n$$ .

  \n
\n
• \n

  Space complexity : $$O(1)$$ .\nWe only used constant auxiliary space.

  \n
\n

Approach #2 (Binary Search Tree) [Accepted]

Intuition

\n
• \n

  If elements in the window are maintained in sorted order, we can apply binary search twice to check if Condition 2 is satisfied.

  \n
\n
• \n

  By utilizing self-balancing Binary Search Tree, one can keep the window ordered at all times with logarithmic time insert and delete.

  \n
\n

Algorithm

The real bottleneck of Approach #1 is due to all elements in the sliding window are being scanned to check if Condition 2 is satisfied. Could we do better?

If elements in the window are in sorted order, we can apply Binary Search twice to search for the two boundaries $$x+t$$ and $$x-t$$ for each element $$x$$ .

Unfortunately, the window is unsorted. A common mistake here is attempting to maintain a sorted array. Although searching in a sorted array costs only logarithmic time, keeping the order of the elements after insert and delete operation is not as efficient. Imagine you have a sorted array with $$k$$ elements and you are adding a new item $$x$$ . Even if you can find the correct position in $$O(\\log k)$$ time, you still need $$O(k)$$ time to insert $$x$$ into the sorted array. The reason is that you need to shift all elements after the insert position one step backward. The same reasoning applies to removal as well. After removing an item from position $$i$$ , you need to shift all elements after $$i$$ one step forward. Thus, we gain nothing in speed compared to the naive linear search approach above.

To gain an actual speedup, we need a dynamic data structure that supports faster insert, search and delete. Self-balancing Binary Search Tree (BST) is the right data structure. The term Self-balancing means the tree automatically keeps its height small after arbitrary insert and delete operations. Why does self-balancing matter? That is because most operations on a BST take time directly proportional to the height of the tree. Take a look at the following non-balanced BST which is skewed to the left:

            6\n           /\n          5\n         /\n        4\n       /\n      3\n     /\n    2\n   /\n  1\n

Figure 1. A non-balanced BST that is skewed to the left.

Searching in the above BST degrades to linear time, which is like searching in a linked list. Now compare to the BST below which is balanced:

          4\n        /   \\\n       2     6\n      / \\   /\n     1   3  5\n

Figure 2. A balanced BST.

Assume that $$n$$ is the total number of nodes in the tree, a balanced binary tree maintains its height in the order of $$h = \\log n$$ . Thus it supports $$O(h) = O(\\log n)$$ time for each of insert, search and delete operations.

Here is the entire algorithm in pseudocode:

\n
• Initialize an empty BST set
\n
• Loop through the array, for each element $$x$$ \n
  \n
  • Find the smallest element $$s$$ in set that is greater than or equal to $$x$$ , return true if $$s - x \\leq t$$ \n
  \n
  • Find the greatest element $$g$$ in set that is smaller than or equal to $$x$$ , return true if $$x - g \\leq t$$ \n
  \n
  • Put $$x$$ in set
  \n
  • If the size of the set is larger than $$k$$ , remove the oldest item.
  \n
  \n
\n
• Return false
\n

One may consider the smallest element $$s$$ that is greater or equal to $$x$$ as the successor of $$x$$ in the BST, as in: "What is the next greater value of $$x$$ ?". Similarly, we consider the greatest element $$g$$ that is smaller or equal to $$x$$ as the predecessor of $$x$$ in the BST, as in: "What is the previous smaller value of $$x$$ ?". These two values $$s$$ and $$g$$ are the two closest neighbors from $$x$$ . Thus by checking the distance from them to $$x$$ , we can conclude if Condition 2 is satisfied.

Java

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {\n    TreeSet<Integer> set = new TreeSet<>();\n    for (int i = 0; i < nums.length; ++i) {\n        // Find the successor of current element\n        Integer s = set.ceiling(nums[i]);\n        if (s != null && s <= nums[i] + t) return true;\n\n        // Find the predecessor of current element\n        Integer g = set.floor(nums[i]);\n        if (g != null && nums[i] <= g + t) return true;\n\n        set.add(nums[i]);\n        if (set.size() > k) {\n            set.remove(nums[i - k]);\n        }\n    }\n    return false;\n}\n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n \\log (\\min(n,k)))$$ .\nWe iterate through the array of size $$n$$ . For each iteration, it costs $$O(\\log \\min(k, n))$$ time (search, insert or delete) in the BST, since the size of the BST is upper bounded by both $$k$$ and $$n$$ .

  \n
\n
• \n

  Space complexity : $$O(\\min(n,k))$$ .\nSpace is dominated by the size of the BST, which is upper bounded by both $$k$$ and $$n$$ .

  \n
\n

Note

\n
• \n

  When the array\'s elements and $$t$$ \'s value are large, they can cause overflow in arithmetic operation. Consider using a larger size data type instead, such as long.

  \n
\n
• \n

  C++\'s std::set, std::set::upper_bound and std::set::lower_bound are equivalent to Java\'s TreeSet, TreeSet::ceiling and TreeSet::floor, respectively. Python does not provide a Self-balancing BST through its library.

  \n
\n

Approach #3 (Buckets) [Accepted]

Intuition

Inspired by bucket sort, we can achieve linear time complexity in our problem using buckets as window.

Algorithm

Bucket sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, using a different sorting algorithm. Here is an illustration of buckets.

Figure 3. Illustration of buckets.

From the above example, we have 8 unsorted integers. We create 5 buckets covering the inclusive ranges of $$[0,9], [10,19], [20, 29], [30, 39], [40, 49]$$ individually. Each of the eight elements is in a particular bucket. For element with value $$x$$ , its bucket label is $$x / w$$ and here we have $$w = 10$$ . Sort each bucket using some other sorting algorithm and then collect all of them bucket by bucket.

Back to our problem, the critical issue we are trying to solve is:

\n

\n
1. For a given element $$x$$ is there an item in the window that is within the range of $$[x-t, x+t]$$ ?
\n
2. Could we do this in constant time?
\n

\n

Let us consider an example where each element is a person\'s birthday. Your birthday, say some day in March, is the new element $$x$$ . Suppose that each month has $$30$$ days and you want to know if anyone has a birthday within $$t = 30$$ days of yours. Immediately, we can rule out all other months except February, March, April.

The reason we know this is because each birthday belongs to a bucket we called month! And the range covered by the buckets are the same as distance $$t$$ which simplifies things a lot. Any two elements that are not in the same or adjacent buckets must have a distance greater than $$t$$ .

We apply the above bucketing principle and design buckets covering the ranges of $$..., [0,t], [t+1, 2t+1], ...$$ . We keep the window using this buckets. Then, each time, all we need to check is the bucket that $$x$$ belongs to and its two adjacent buckets. Thus, we have a constant time algorithm for searching almost duplicate in the window.

One thing worth mentioning is the difference from bucket sort \xe2\x80\x93 Each of our buckets contains at most one element at any time, because two elements in a bucket means "almost duplicate" and we can return early from the function. Therefore, a HashMap with an element associated with a bucket label is enough for our purpose.

Java

public class Solution {\n    // Get the ID of the bucket from element value x and bucket width w\n    // In Java, `-3 / 5 = 0` and but we need `-3 / 5 = -1`.\n    private long getID(long x, long w) {\n        return x < 0 ? (x + 1) / w - 1 : x / w;\n    }\n\n    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {\n        if (t < 0) return false;\n        Map<Long, Long> d = new HashMap<>();\n        long w = (long)t + 1;\n        for (int i = 0; i < nums.length; ++i) {\n            long m = getID(nums[i], w);\n            // check if bucket m is empty, each bucket may contain at most one element\n            if (d.containsKey(m))\n                return true;\n            // check the neighbor buckets for almost duplicate\n            if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)\n                return true;\n            if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)\n                return true;\n            // now bucket m is empty and no almost duplicate in neighbor buckets\n            d.put(m, (long)nums[i]);\n            if (i >= k) d.remove(getID(nums[i - k], w));\n        }\n        return false;\n    }\n}\n

Complexity Analysis

\n
• \n

  Time complexity : $$O(n)$$ .\nFor each of the $$n$$ elements, we do at most three searches, one insert, and one delete on the HashMap, which costs constant time on average. Thus, the entire algorithm costs $$O(n)$$ time.

  \n
\n
• \n

  Space complexity : $$O(\\min(n,k))$$ .\nSpace is dominated by the HashMap, which is linear to the size of its elements. The size of the HashMap is upper bounded by both $$n$$ and $$k$$ . Thus the space complexity is $$O(\\min(n, k))$$ .

  \n
\n

See Also

\n
• Problem 217 Contains Duplicate
\n
• Problem 219 Contains Duplicate II
\n