JavaScript O(N^2) O(1) space but elegant!!


  • 0
    K

    The idea is to loop through the nums array once, for each number, compare it to the previous two numbers. The array is sorted, so we know that if the current number is equal to both the previous two numbers, we can remove and splice it from the array. I am not 100% on the space requirements of the splice function, but think it is an in place operation. The time complexity is O(n^2) because it is possible the entire array is full of duplicates and we would have to shift all the elements in the nums array left one index each time.

    var removeDuplicates = function(nums) {
        if(nums.length <= 2) return;
        let i = 2
        
        while(i < nums.length) {
            let prev = nums[i-1]  
            let prevPrev = nums[i-2]
            
            if(nums[i] === prev && nums[i] === prevPrev) {
                nums.splice(i, 1)
                continue;
            }
            i++
        }
    };
    
    

Log in to reply
 

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