Codility Challange: PrefixSet [Ruby solution]

prefix_set.rb

=begin
Codility Challange: PrefixSet
https://app.codility.com/programmers/task/prefix_set/

Solution: https://codility.com/media/train/solution-prefix-set.pdf
=end

def prefixSetGolden(arr)
  n = arr.size
  occur = {}
  result = nil
  (0...n).each do |i|
    if !occur.has_key?(arr[i])
      occur[arr[i]] = true
      result = i
    end
  end
  result
end

# test case
# prefixSetGolden [2,2,1,0,1]
# solution is 3.

This solution makes use of a Hash. The original solution provided by the Codility platform makes use of an occur array of size equal to the argument array. Each element of occur is false.

Original solution in python:

def prefixSetGolden(A):
  n = len(A)
  occur = [False] * n
  for i in xrange(n):
    if (occur[A[i]] == False):
      occur[A[i]] = True
      result = i
  return result

Using a hash should be much faster and uses less space. Also, lookup time of a hash is fast.