Simple and elegant C++ 20ms solution, easy to understand


  • 4
    J
    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            vector<pair<int, int>> a;
            for(int i = 0; i < nums.size(); ++i){
                a.push_back(make_pair(nums[i], i));
            }
            sort(a.begin(), a.end(), [](const pair<int, int> & a, const pair<int, int> & b)->bool{ return a.first < b.first; });
            int fast = 0, slow = 0;
            for(fast = 1; fast < nums.size(); ++fast){
                while((long long)a[fast].first - a[slow].first > t) ++slow;
                for(int i = slow; i < fast; ++i){
                    if(abs(a[i].second - a[fast].second) <= k) return 1;
                }
            }
            return 0;
        }
    };

  • 0
    R

    complexity of the above code is O(n^2) ??


  • 0
    J

    Time complexity is O(n^2) in the worst case, in addition to O(nLogn) of sorting. On average it would be more efficient with a smaller value of t.


  • 0
    A

    @JonnyKong But why would you need to sort first. With sort, the values are ordered, but the indices are unordered. Orignially we have indices ordered while values unordered. So you can skip the sort and directly apply the fast and slow on indices which gives better time complexity: O(n*k).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.