Commit 773f8df

@@ -20,6 +20,28 @@ class Solution
 
     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]))