Find All Duplicates in an Array

S
```# Find All Duplicates in an Array
#
# Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array),
# some elements appear twice and others appear once.
#
# Find all the elements that appear twice in this array.
#
# Could you do it without extra space and in O(n) runtime?
#
# Example:
# Input:
# [4,3,2,7,8,2,3,1]
#
# Output:
# [2,3]

require 'benchmark'

array = [4, 3, 2, 7, 8, 2, 3, 1]
long_array = [4, 3, 2, 7, 8, 2, 3, 1] * 100

#
# Approach: Hash table
#

#
# Complexity Analysis
#
# Time complexity: O(n) average case.
#

def find_duplicates(array)
result_hash = {}
result_array = []

# loop through array and build a hash with counters
# where the key is the array element and the counter is the value
# increase counter when duplicate is found
array.each do |num|
if result_hash[num].nil?
result_hash[num] = 1
else
result_hash[num] += 1
end
end

# loop through hash and look for values > 1
result_hash.each do |k, v|
result_array.push(k) if v > 1
end

# return keys
result_array
end

Benchmark.bmbm do |x|
x.report('execute algorithm 3') do
print(find_duplicates(array))
print(find_duplicates(long_array))
end
end
```