1def assert(value)
 2  raise value.inspect unless value
 3end
 4
 5class Solution
 6  # time: O(n^3)
 7  # space: O(1)
 8  def self.run(items)
 9    for i in (0...items.size)
10      for p in (i+1...items.size)
11        for q in (p+1...items.size)
12          x = items[i] ** 2
13          y = items[p] ** 2
14          z = items[q] ** 2
15
16          return true if (x + y) == z
17        end
18      end
19    end
20
21    false
22  end
23
24  # time: O(nlogn) + O(n) == O(nlogn)
25  # space: O(n)
26  def self.run(items)
27    h, t = 0, items.size - 1
28    items.sort! # nlogn
29    cache = {}
30
31    until h >= t
32      head = items[h] ** 2
33      tail = items[t] ** 2
34      expected = tail - head
35      return true if cache[expected]
36
37      cache[head] = true
38      cache[tail] = true
39
40      expected > tail ? t-=1 : h+=1
41    end
42
43    nil
44  end
45end
46
47assert(Solution.run([3, 12, 5, 13]))
48assert(!Solution.run([1]))
49assert(!Solution.run([1, 2]))
50assert(!Solution.run([1, 2, 3]))
51assert(Solution.run([3, 4, 5]))
52puts "YAY!"