Javascript solution that beats 100%


  • 0
    C
    /**
     * @param {number[]} nums
     * @param {number} k
     * @param {number} t
     * @return {boolean}
     */
    var containsNearbyAlmostDuplicate = function(nums, k, t) {
        if (!nums || nums.length < 2) return false;
        
        var indices = [nums.length];
        
        // initialize indices array to [0,1,2,3,...].
        for (i = 0; i < nums.length; ++i) {
            indices[i] = i;
        }
        
        // sort indices base on their values.
        indices = indices.sort(function(a, b) {
            return nums[a] - nums[b];
        });
        
        // loop through the indices array.
        var i, j;
        for (i = 0; i < nums.length - 1; ++i) {
            var x = indices[i];
            
            for (j = i + 1; j < nums.length; ++j) {
                var y = indices[j];
                var diff = nums[y] - nums[x];
                var di = y > x ? y - x : x - y;
                
                // stop if the difference exceeds t.
                if (diff > t) break;
                
                if (di <= k) return true;
            }
        }
        
        return false
    };

  • 0
    O

    Because nobody submit by javascript. Your time complexity is high


  • 0
    C

    I don't think one can faster than O(nlongn)


  • 0

Log in to reply
 

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