def assert(value)
  raise value.inspect unless value
end

class Solution
  # time: O(n^3)
  # space: O(1)
  def self.run(items)
    for i in (0...items.size)
      for p in (i+1...items.size)
        for q in (p+1...items.size)
          x = items[i] ** 2
          y = items[p] ** 2
          z = items[q] ** 2

          return true if (x + y) == z
        end
      end
    end

    false
  end

  # time: O(nlogn) + O(n) == O(nlogn)
  # space: O(n)
  def self.run(items)
    h, t = 0, items.size - 1
    items.sort! # nlogn
    cache = {}

    until h >= t
      head = items[h] ** 2
      tail = items[t] ** 2
      expected = tail - head
      return true if cache[expected]

      cache[head] = true
      cache[tail] = true

      expected > tail ? t-=1 : h+=1
    end

    nil
  end
end

assert(Solution.run([3, 12, 5, 13]))
assert(!Solution.run([1]))
assert(!Solution.run([1, 2]))
assert(!Solution.run([1, 2, 3]))
assert(Solution.run([3, 4, 5]))
puts "YAY!"