Skip to content

Instantly share code, notes, and snippets.

@jumph4x

jumph4x/gist:3442159

Created August 23, 2012 21:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jumph4x/3442159 to your computer and use it in GitHub Desktop.
Save jumph4x/3442159 to your computer and use it in GitHub Desktop.
Download ZIP
Subset Check
Raw
gistfile1.rb
def is_subset?(a,b)
return true if b and b.is_a? Array and b.empty? # O(1)
hash = {} # O(1)
a.each{|v| hash[v] = true} # O(n) outer, O(1) inner, O(n) total
b.map{|v| hash[v] }.uniq == [true] # O(n) outer, O(1) inner, O(n) total
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment