clean O(n) bucket solution, C++


  • 1
    T

    The basic idea is to put each number into corresponding bucket, then check those two constraints. The bucket size should be t+1(consider edge case t = 0). Each bucket only stores the largest index of numbers in it.

    For each number,

    1. find the index of bucket it belongs to
    2. check those two constraints with the current bucket and adjacent buckets.

    Time : O(n)
    space : O(t)

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, long t) {
            if (nums.size() < 2 || t < 0 || k < 0) return false;
            int minx = INT_MAX, maxx = INT_MIN;
            //find the minimum and maximum to determine the number of buckets
            for (auto & i : nums) {
                minx = min(minx, i);
                maxx = max(maxx, i);
            }
            int n = ((long)maxx - (long)minx) / (t + 1) + 1;
            //initialize by -(k + 1)
            vector<int> buckets(n, -(k + 1));
            for (int i = 0, j; i < nums.size(); i++) {
                //get the index of bucket
                j = ((long)nums[i] - (long)minx) / (t + 1);
                //check the two constraints
                if ((i - buckets[j] <= k) || (j && i - buckets[j - 1] <= k && (long)nums[i] - (long)nums[buckets[j - 1]] <= t) || (j < n - 1 && i - buckets[j + 1] <= k && (long)nums[buckets[j + 1]] - (long)nums[i] <= t))
                    return true;
                buckets[j] = i;
            }
            return false;
        }
    };
    

Log in to reply
 

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