Solve in O(nlogn) time

1 files changed, 22 insertions, 0 deletions

diff --git a/2020/08/24/main.rb b/2020/08/24/main.rb
index 102cf91..b3742b3 100644
--- a/2020/08/24/main.rb
+++ b/2020/08/24/main.rb
@@ -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]))