220. Contains Duplicate III

220. Contains Duplicate III (Medium)

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

Related Topics:
Sort, Ordered Map

Similar Questions:

• Contains Duplicate (Easy)
• Contains Duplicate II (Easy)

Solution 1.

// OJ: https://leetcode.com/problems/contains-duplicate-iii/
// Author: github.com/lzl124631x
// Time: O(NlogK)
// Space: O(K)
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& A, int k, int t) {
        if (t < 0) return false;
        multiset<long> s;
        for (int i = 0; i < A.size(); ++i) {
            if (i > k) s.erase(s.find(A[i - k - 1]));
            if (s.lower_bound((long)A[i] - t) != s.upper_bound((long)A[i] + t)) return true;
            s.insert(A[i]);
        }
        return false;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/contains-duplicate-iii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(K)
// Ref: https://leetcode.com/problems/contains-duplicate-iii/discuss/61645/AC-O(N)-solution-in-Java-using-buckets-with-explanation
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& A, int k, int t) {
        if (A.size() < 2 || k < 1 || t < 0) return false;
        unordered_map<long, long> m;
        for (int i = 0; i < A.size(); ++i) {
            if (i > k) m.erase(((long)A[i - k - 1] - INT_MIN) / ((long)t + 1));
            long n = (long)A[i] - INT_MIN, id = n / ((long)t + 1);
            if (m.count(id) || (m.count(id - 1) && A[i] - m[id - 1] <= t) || (m.count(id + 1) && m[id + 1] - A[i] <= t)) return true; 
            m[id] = A[i];
        }
        return false;
    }
};