Contains Duplicate III

Hard Arrays & Hashing Sliding Window · Hash Map Original on LeetCode

Contains Duplicate III is a hard arrays & hashing problem solved with the sliding window · hash map pattern. The best approach, optimal (buckets of width valuediff + 1), runs in O(n) time and O(k) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.

Problem

You are given an integer array nums and two integers indexDiff and valueDiff. Decide whether there are two different indices i and j such that:

  • |i - j| <= indexDiff, and
  • |nums[i] - nums[j]| <= valueDiff.

Return true if such a pair exists, otherwise false.

Examples

Example 1

Input
nums = [10, 3, 15, 6], indexDiff = 2, valueDiff = 3
Output
true
Why
Indices 1 and 3 are 2 apart and |3 - 6| = 3, which is within valueDiff.

Example 2

Input
nums = [1, 9, 17, 25], indexDiff = 3, valueDiff = 7
Output
false
Why
Every pair of values differs by at least 8.

Example 3

Input
nums = [-4, 20, 0, -5], indexDiff = 2, valueDiff = 1
Output
false
Why
-4 and -5 differ by 1, but their indices are 3 apart, more than indexDiff.

Constraints

  • 2 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 1 <= indexDiff <= nums.length
  • 0 <= valueDiff <= 10^9

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 18 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute forceO(n · indexDiff)O(1)
Sorted windowO(n log k)O(k)
Optimal (buckets of width valueDiff + 1)O(n)O(k)

1Brute force

TimeO(n · indexDiff)Each element is compared with up to indexDiff later elements.
SpaceO(1)Only loop indices.

For each index, compare it with the next indexDiff elements and check whether any value is within valueDiff.

  1. For i from 0 to n - 1, for j from i + 1 to min(n - 1, i + indexDiff).
  2. If |nums[i] - nums[j]| <= valueDiff (computed in 64 bits), return true.
  3. Return false.
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n && j <= i + indexDiff; j++) {
                if (Math.abs((long) nums[i] - nums[j]) <= valueDiff) return true;
            }
        }
        return false;
    }
}

2Sorted window

TimeO(n log k)Each step does a search, an insert and a delete on a balanced tree of at most k = indexDiff values.
SpaceO(k)The window holds at most indexDiff values.

Keep the last indexDiff values in a sorted structure. For the current value x, find the smallest stored value that is at least x - valueDiff. If it exists and is at most x + valueDiff, the answer is true. Then add x and drop the value that just left the window.

  1. For each index i with value x:
  2. Find the ceiling of x - valueDiff in the window; if it is <= x + valueDiff, return true.
  3. Insert x. If the window holds more than indexDiff values, remove nums[i - indexDiff].
  4. Return false at the end.
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Long> window = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            Long ceil = window.ceiling(x - valueDiff);
            if (ceil != null && ceil <= x + valueDiff) return true;
            window.add(x);
            if (i >= indexDiff) window.remove((long) nums[i - indexDiff]);
        }
        return false;
    }
}

3Optimal (buckets of width valueDiff + 1)

TimeO(n)Each element does a constant number of hash map operations.
SpaceO(k)The map holds at most indexDiff buckets, one per value in the window.

Split the number line into buckets of width w = valueDiff + 1, so bucket id = floor(x / w). Two values in the same bucket differ by at most valueDiff, so a second value in a bucket means true. Values in buckets further than one apart differ by more than valueDiff, so only the two neighbouring buckets need a real check. Each bucket holds at most one value from the window, so a hash map from bucket id to value is enough.

  1. w = valueDiff + 1 (as a 64-bit number).
  2. For each index i with value x, id = floorDiv(x, w).
  3. If the map has id, return true.
  4. If the map has id - 1 with |x - value| <= valueDiff, or id + 1 with the same test, return true.
  5. Store map[id] = x. If i >= indexDiff, remove the bucket of nums[i - indexDiff].
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        long w = (long) valueDiff + 1;
        Map<Long, Long> buckets = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            long id = Math.floorDiv(x, w);
            if (buckets.containsKey(id)) return true;
            Long left = buckets.get(id - 1);
            if (left != null && x - left <= valueDiff) return true;
            Long right = buckets.get(id + 1);
            if (right != null && right - x <= valueDiff) return true;
            buckets.put(id, x);
            if (i >= indexDiff) buckets.remove(Math.floorDiv((long) nums[i - indexDiff], w));
        }
        return false;
    }
}

Edge cases to test

  • valueDiff = 0: the question becomes "is there an exact duplicate within indexDiff"
  • Values at both ends of the range, where differences overflow 32-bit ints
  • Negative values: bucket ids must round down, not toward zero
  • indexDiff equal to the array length

Hints

Hint 1

Only the last indexDiff elements matter when you are at index i.

Hint 2

Among those, you only need the smallest value that is >= nums[i] - valueDiff. A sorted structure finds it fast.

Hint 3

Put values into buckets of width valueDiff + 1. Two values in the same bucket always qualify; only the neighbouring buckets need a real check.

FAQ

What is the best time complexity for Contains Duplicate III?

Optimal (buckets of width valueDiff + 1) runs in O(n) time and O(k) extra space. Each element does a constant number of hash map operations.

Which pattern does Contains Duplicate III use?

It is a arrays & hashing problem that uses the sliding window · hash map pattern. Other problems with the same pattern: Number of Substrings Containing All Three Characters, Minimum Window Substring, Longest Substring with At Most K Distinct Characters.

Is there a brute force solution for Contains Duplicate III?

Yes. Brute force takes O(n · indexDiff) time and O(1) space. For each index, compare it with the next indexDiff elements and check whether any value is within valueDiff.

Which edge cases should I test for Contains Duplicate III?

valueDiff = 0: the question becomes "is there an exact duplicate within indexDiff"; Values at both ends of the range, where differences overflow 32-bit ints; Negative values: bucket ids must round down, not toward zero; indexDiff equal to the array length.