Class: Kata::Algorithms::SumOfThreeHash

Inherits:
SumOfThree
  • Object
show all
Defined in:
lib/kata/algorithms/sum_of_three/sum_of_three_hash.rb

Instance Attribute Summary collapse

Attributes inherited from SumOfThree

#array_of_integers

Instance Method Summary collapse

Constructor Details

#initialize(array_of_integers) ⇒ SumOfThreeHash

Returns a new instance of SumOfThreeHash.



8
9
10
11
 
# File 'lib/kata/algorithms/sum_of_three/sum_of_three_hash.rb', line 8

def initialize(array_of_integers)
  super
  self.integer_positions = build_hash(array_of_integers)
end

Instance Attribute Details

#integer_positions ⇒ Object

Returns the value of attribute integer_positions.



6
7
8
 
# File 'lib/kata/algorithms/sum_of_three/sum_of_three_hash.rb', line 6

def integer_positions
  @integer_positions
end

Instance Method Details

#find_three ⇒ Object

Tries to find 3 integers that sum up to 0. In other words given an array a, we want to find the 3 integers that satisfy the equation:

a[i] + a[j] + a[k] == 0

where i != j && i != k && j !=k

This equation can be equally written:

a[i] == - a[j] - a[k]

Hence, we are looking for pairs of integers in a, let’s say a and a, that their (- a - a) is another integer in the array.

The algorithm will use a hash to store the integers of the array and their position. Then it will iterate all the pairs j, k and will try to see whether their (-a-a) is in the hash and in which position. One might say, why do we keep an array of positions of each integer and not just keep a true/false flag to indicate that the result exists in the hash. This is done to avoid cases in which (-a-a) == a or (-a-a) == a For example, if the initial array is [-4, 8, 5], then if we just build the hash h = => true, 8 => true, 5 => true, for j == 0 and k == 1, the (-a-a) == (+4-8) == -4 and -4 exists in the hash and we falsely get the result -4, -8, -4. If we know that -4 => [0] we can see that 0 is == j and does not count as a valid found position.

Note that this algorithm average and worst case performance is O(n^2) Note also that seaching in a hash entry to find a position that is different from j, k at hand is now done with Array#index, which does linear search. If the initial array has a lot of duplicates the search might take long.



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/kata/algorithms/sum_of_three/sum_of_three_hash.rb', line 46

def find_three
  j = 0
  size_of_array = array_of_integers.size
  while j < size_of_array
    k = j + 1
    while k < size_of_array
      i = - array_of_integers[j] - array_of_integers[k]
      hash_entry = integer_positions[i]
      # there has to be at least one integer position in the hash_entry which is not j or k
      return [array_of_integers[j], array_of_integers[k], i] unless hash_entry.nil? || hash_entry.index {|item| ![j, k].include?(item)}.nil?
      k += 1
    end
    j += 1
  end
  []
end