#### Find All Duplicates in an Array

J
V
# 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 1: Brute force
#

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

def find_duplicates(array)
current_num = array[0]
result_array = []

array.count.times do |i|
array.count.times do |j|
next if i == j || current_num != array[j]

result_array.push(current_num)
end

current_num = array[i + 1]
end

result_array.uniq
end

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

#
# Approach 2: Sort and Compare Adjacent Elements
#

# Intuition

# After sorting a list of elements, all elements of equivalent value get placed together.
# Thus, when you sort an array, equivalent elements form contiguous blocks.

#
# Complexity Analysis
#
# Time complexity: O(n log n)
#

def find_duplicates(array)
sorted_array = array.sort
result_array = []

(1..sorted_array.count).each do |i|
next if sorted_array[i] != sorted_array[i - 1]

result_array.push(sorted_array[i])
end

result_array.uniq
end

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