linear algorithm to find item that does not have a match

1 files changed, 22 insertions, 0 deletions

diff --git a/2020/08/18/main.rb b/2020/08/18/main.rb
new file mode 100644
index 0000000..1847003
--- /dev/null
+++ b/2020/08/18/main.rb
@@ -0,0 +1,22 @@
+def assert_equal(x, y)
+  raise [x, y].inspect unless x == y
+end
+
+class Solution
+  # time: O(n)
+  # space: O(n)
+  def self.run(items)
+    cache = Hash.new do |hash, key|
+      hash[key] = 2
+    end
+
+    for i in (0...items.size)
+      item = items[i]
+      cache[item] -= 1
+    end
+
+    cache.values.find { |value| value > 0 }
+  end
+end
+
+assert_equal 1, Solution.run([4, 3, 2, 4, 1, 3, 2])