O(n log n) JavaScript solution beats 95%.


  • 0
    R

    JavaScript's built-in sort is pretty bad, so I wrote out the code for Heap sort. Quick sort would probably be faster, but I'm currently in a heapsort kind of mood these days.

    The first thing we do is map the input array so that each element is an object containing its value and its original index. Then we sort the mapped array by index. Once it's sorted, it becomes a simple game of using two pointers (left and right), and scanning along the mapped array. They will begin at position 0 and 1, and we will compare the elements in mapped in those two positions. If their value and index difference falls within k and t, return true, otherwise if their values are close enough (but index difference is too large), we only move the right pointer up. Else, we move the left pointer up (and if the left ever catches up to right, then we move right up by 1).

    var containsNearbyAlmostDuplicate = function(nums, k, t) {
        if (k <= 0 || nums.length <= 1 || t < 0) return false;
    
        let mapped = nums.map((num,idx) => {
           return {val: num, index: idx}; 
        });
    
        // Sort mapped by the val property. I wrote and used heapSort for this, but you could use whatever method you want, including JavaScript's built-in Array.sort((a,b) a.val - b.val);
    
        let leftPointer = 0, rightPointer = 1;
        while (rightPointer < mapped.length) {
            
            let diff = Math.abs(mapped[leftPointer].val - mapped[rightPointer].val);
            let range = Math.abs(mapped[leftPointer].index - mapped[rightPointer].index);
            if (diff <= t && range <= k) {
                return true;
            } else if (diff <= t) {
                rightPointer++;
            } else {
                leftPointer++;
                if (rightPointer === leftPointer) rightPointer++;
            }
        }
        return false;
    };
    

  • 1
    F

    @robtaussig this doesn't seem to pass for me. I've used build-in sort for proof of concept and it fails on inputs

    [1,0,1,1]
    1
    0
    

  • 0
    F

    I failed in this way too.After the analysis of the condition judgments, an additional judgment was added to the code.And then it worked. By the way, I've also used JavaScript's built-in Array.sort(). Here is the complete code:

    
    var containsNearbyAlmostDuplicate = function(nums, k, t) {
        if (k <= 0 || nums.length <= 1 || t < 0) return false;
    
        let mapped = nums.map((num,idx) => {
           return {val: num, index: idx}; 
        });
    
        // Sort mapped by the val property. I wrote and used heapSort for this, but you could use whatever method you want, including JavaScript's built-in Array.sort((a,b) a.val - b.val);
        
        mapped.sort((a,b) => {return a.val - b.val});
    
        let leftPointer = 0, rightPointer = 1;
        while (rightPointer < mapped.length) {
            
            let diff = Math.abs(mapped[leftPointer].val - mapped[rightPointer].val);
            let range = Math.abs(mapped[leftPointer].index - mapped[rightPointer].index);
            if (diff <= t && range <= k) {
                return true;
            } else if (diff <= t) {
                rightPointer++;
            } else {
                leftPointer++;
                if (rightPointer === leftPointer) rightPointer++;
            }
            
            //Here is the additional condition judgment
            if(diff <= t && rightPointer >= mapped.length){
                leftPointer++;
                if(leftPointer < mapped.length - 1) rightPointer = leftPointer++;
            }
        }
        return false;
    };
    
    

Log in to reply
 

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