An Le An Le - 6 months ago 10
Ruby Question

Finding duplicate in an array -- How to make faster?

I wrote a function that returns true if an array contains duplicates, false otherwise. My runtime is only in the 50th percentile of submissions on Leet Code. Why? Isn't this O(n) and how can you make this faster?

def contains_duplicate(nums)
hsh = Hash.new(0)

nums.each do |num|
hsh[num] +=1
if hsh[num] > 1
return true
end
end
return false
end


Runtime hash submission only in the 50th percentile

*Edit
For the curious, here's the link to the coding problem on Leet Code: https:// leetcode.com/problems/contains-duplicate/

Yo peeps, I ran the suggested set code and got an even worse runtime:

def contains_duplicate(nums)
s = Set.new
nums.each { |num| return true unless s.add?(num) }
false
end


Runtime set submission in 20th percentile

**Fastest running time

def contains_duplicate(nums)
hsh = Hash.new(0)
count=0
nums.each do |num|
count+=1
hsh[num]=1
if hsh.size < count
return true
end
end
return false
end


http: //i.stack.imgur.com/Xx21p.png

Answer

I'm not familiar with ruby, but I can see that your loop requires 3 hash lookups per item, and hash lookups are the most expensive operation involved after allocating new items.

Try something like this, which requires only one lookup per item:

def contains_duplicate(nums)
  hsh = Hash.new(0)
  count=0
  nums.each do |num|
    count+=1
    hsh[num]=1
    if hsh.size < count
      return true
    end
  end
  return false
end
Comments