Contains Duplicate III

07/16/2016 Binary Search Tree

Question
Solution

Question

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

Solution

Result: Accepted Time: 20 ms

Here should be some explanations.

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        const int ncnt = nums.size();
        vector<pair<int,int>> vect(ncnt);
        for(int i = 0 ; i < ncnt; i++)
            vect[i].first = nums[i],vect[i].second=i;
        sort(vect.begin(),vect.end());
        for(int i = 0,j = 0; i < ncnt; j=++i)
            while( ++j < ncnt && vect[j].first - t <= vect[i].first)
                if(abs(vect[i].second-vect[j].second) <= k)
                    return true;
        return false;
    }
};

Complexity Analytics

Time Complexity: $O(nlog(n))$
Space Complexity: $O(n)$