Contains Duplicate Iii - Leetcode Solution

The "Contains Duplicate III" problem on LeetCode asks us to determine if there are any two elements in an array that differ no more than k indexes apart and have an absolute difference of at most t. The problem statement gives the following constraints:

• The array can contain negative integers.
• k must be a non-negative integer.
• t must be a non-negative integer.

Here's an example:

Input: nums = [1,2,3,1], k = 3, t = 0 Output: true Explanation: Because nums[0] and nums[3] are both 1 and differ no more than 3 indexes apart.

To solve this problem, we can use two pointers. We will maintain a window of size k and a binary search tree (BST) to store the elements within the window. For each element in the array, we will check if there exists an element in the BST that is within t of it. If so, we return true, since we've found a duplicate that satisfies the constraints. If not, we add the current element to the BST and move the window forward, removing the first element of the window from the BST.

Here's the code:

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> window; // set is ordered automatically
        for (int i = 0; i < nums.size(); i++) {
            
            // check if there exists an element in the window that is within t of nums[i]
            auto it = window.lower_bound(static_cast<long>(nums[i]) - t);
            if (it != window.end() && *it <= static_cast<long>(nums[i]) + t) {
                return true;
            }
            
            // insert nums[i] into the window and move the window forward
            window.insert(nums[i]);
            if (window.size() > k) {
                window.erase(nums[i - k]);
            }
        }
        return false;
    }
};

The time complexity of this solution is O(n log k), since inserting and erasing elements from a BST takes logarithmic time in the worst case. The space complexity is O(k), since we are storing at most k elements in the BST at any given time.

1