Contains Duplicate III

Problem Description

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. Return true if such pair exists or false otherwise.

Key Insights

• The problem requires checking pairs of indices within a specified range and ensuring the values at those indices also meet a certain difference condition.
• A brute-force approach would involve checking all pairs, leading to a time complexity of O(n^2), which is not feasible for large arrays.
• A more efficient approach can be achieved using a sliding window combined with a data structure that allows for ordered retrieval of elements, such as a balanced tree or a sorted list.

Space and Time Complexity

Time Complexity: O(n log k) where k is indexDiff, due to maintaining a sliding window of at most size k in a sorted order.
Space Complexity: O(k) for the sliding window storage.

Solution

To solve this problem, we can use a sliding window approach along with a data structure that allows for efficient insertion and searching of elements. We maintain a window of size indexDiff and use a sorted data structure to keep the numbers within that window. For each new number added to the window, we check if there exists another number in the window such that the absolute difference in values is less than or equal to valueDiff.

Code Solutions