220. Contains Duplicate III

• Difficulty: Medium

• Topics: Sort, Ordered Map

• Similar Questions:

  • Contains Duplicate

  • Contains Duplicate II

Problem:

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Solutions:

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (k < 0 || t < 0) return false;
        long kl = abs(k); // long! not int!
        long tl = abs(t); // long! not int!
        set<long> heap;
        int initHeapSize = min(long(nums.size()), kl);


        for (int i = 0; i < initHeapSize; ++i) {
            auto it = heap.lower_bound(nums[i] - tl);
            if (it != heap.end() && *it <= nums[i] + tl) return true; // if not using long, overflow happens.
            heap.insert(nums[i]);
        }

        for (int i = kl ; i < nums.size(); ++i) {
            auto it = heap.lower_bound(nums[i] - tl);
            if (it != heap.end() && *it - nums[i] <= tl) return true;
            heap.insert(nums[i]);
            heap.erase(nums[i - k]);
        }

        return false;
    }
};