{x}
blog image

Contains Duplicate III

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

Find a pair of indices (i, j) such that:

  • i != j,
  • abs(i - j) <= indexDiff.
  • abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

 

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

 

Constraints:

  • 2 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 1 <= indexDiff <= nums.length
  • 0 <= valueDiff <= 109

Solution Explanation: Sliding Window + Ordered Set

This problem asks whether there exists a pair of indices (i, j) in the input array nums that satisfy three conditions:

  1. i != j
  2. abs(i - j) <= indexDiff
  3. abs(nums[i] - nums[j]) <= valueDiff

A brute-force approach would check all pairs of indices, resulting in O(n²) time complexity. However, we can optimize this using a sliding window and an ordered set (like a TreeSet in Java or a SortedSet in Python).

Algorithm:

  1. Initialization: We use an ordered set (s) to store elements within the current sliding window. The window size is determined by indexDiff.

  2. Iteration: We iterate through the nums array. For each element nums[i]:

    • Check for a nearby almost duplicate: We use the ordered set's bisect_left (Python) or ceiling (Java) method to efficiently find the smallest element in the set that is greater than or equal to nums[i] - valueDiff. If such an element exists and is less than or equal to nums[i] + valueDiff, then we've found a pair satisfying the conditions, and we return true.

    • Add to the window: We add nums[i] to the ordered set s.

    • Remove from the window: If the window size exceeds indexDiff, we remove nums[i - indexDiff] (the element that's no longer within the window) from the set.

  3. No nearby almost duplicate: If the loop completes without finding a pair, we return false.

Time Complexity Analysis:

  • The outer loop iterates n times (where n is the length of nums).
  • Inside the loop, the operations on the ordered set (insertion, removal, and finding the ceiling/bisect_left) take O(log k) time on average, where k is the maximum window size (indexDiff).
  • Therefore, the overall time complexity is O(n log k). This is significantly better than the O(n²) of the brute-force approach.

Space Complexity Analysis:

The space complexity is O(k) because the ordered set s stores at most k elements at any given time.

Code Examples (Python & Java):

Python:

import bisect
from sortedcontainers import SortedSet
 
class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        s = SortedSet()
        for i, v in enumerate(nums):
            idx = s.bisect_left(v - valueDiff)  # Find the index of the smallest element >= v - valueDiff
            if idx < len(s) and s[idx] <= v + valueDiff: # Check if an element within valueDiff exists
                return True
            s.add(v)
            if i >= indexDiff:
                s.remove(nums[i - indexDiff])
        return False
 

Java:

import java.util.TreeSet;
 
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        TreeSet<Long> s = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Long ceiling = s.ceiling((long) nums[i] - valueDiff); // Find the smallest element >= nums[i] - valueDiff
            if (ceiling != null && ceiling <= (long) nums[i] + valueDiff) {
                return true;
            }
            s.add((long) nums[i]);
            if (i >= indexDiff) {
                s.remove((long) nums[i - indexDiff]);
            }
        }
        return false;
    }
}

The other languages (C++, Go, TypeScript, C#) demonstrate similar implementations, leveraging their respective ordered set data structures. The core algorithm remains consistent across all languages.