Two simple Ruby solutions and some analysis


  • 0
    J
    # @param {Integer[]} nums
    # @return {Integer}
    def remove_duplicates(nums)
        non_dupe_index = 0
        nums.each do |num|
            if (non_dupe_index == 0 || num > nums[non_dupe_index - 1])
                nums[non_dupe_index] = num
                non_dupe_index += 1
            end
        end
        nums.replace(nums)
        non_dupe_index
    end
    

    This solution runs at 109 ms and beats 40.91%.

    Here is a faster solution that may stretch the constant memory restraint a bit;

    # @param {Integer[]} nums
    # @return {Integer}
    def remove_duplicates(nums)
        last = nil
        (0...nums.size).each do |i|
            num = nums[i]
            if last == num
                nums[i] = nil
            else
                last = num
            end
        end
        nums.replace(nums.compact)
        nums.size
    end
    

    This solution runs at 82ms and beats 86.36%.

    Basically .compact is super fast. But it's technical creating another array.

    Can we just do that in place?

    If we replace nums.replace(nums.compact) with nums.compact! it works and makes more sense, but performance drops to 95ms, which only beats 54.55%. Odd to say the least considering that we are basically doing the same thing.


  • 0
    J

    You don't need to replace the array.

    The challenge says:

    Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

    By using two pointers (as they do in the editorial solution) you can easily average ~80ms with an in place solution. No need to do unnecessary work if it's not required :)


  • 0
    J

    In the second example If you don't run .replace on the array, Ruby doesn't keep the modifications to the array parameter.

    But you are correct about the first example not needing it.


  • 0
    J

    @jamesfm Oh, I just wanted to point out that you can get the same performance and do it in place if you approach the problem using pointers.

    def remove_duplicates(nums)
      return 0 if nums.empty?
    
      first_pointer, second_pointer = 0, 1
    
      while second_pointer < nums.length
        if nums[first_pointer] != nums[second_pointer]
          first_pointer += 1
          nums[first_pointer] = nums[second_pointer]
        end
        second_pointer += 1
      end
    
      first_pointer + 1
    end
    

Log in to reply
 

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