1 files changed, 49 insertions, 0 deletions
diff --git a/2020/08/16/main.rb b/2020/08/16/main.rb
new file mode 100644
index 0000000..9a533c6
--- /dev/null
+++ b/2020/08/16/main.rb
@@ -0,0 +1,49 @@
+def assert_equals(x, y)
+  raise [x, y].inspect unless x == y
+end
+
+=begin
+Sorting algorithm would yield.
+time: O(nlogn)
+
+Let's see if we can do this in O(n)
+
+
+             t
+ h
+|3|3|2|1|3|2|1|
+
+=end
+
+class Solution
+  # time: O(n)
+  # space: O(1)
+  def self.run(items)
+    h = 0
+    t = items.size - 1
+
+    while h < t
+      puts [h, items, t].inspect
+
+      if items[h] == 1
+        h += 1
+      elsif items[t] == 3
+        t -= 1
+      elsif items[h] == 3
+        tmp = items[h]
+        items[h] = items[t]
+        items[t] = tmp
+      elsif items[t] == 1
+        tmp = items[t]
+        items[t] = items[h]
+        items[h] = tmp
+      else
+        t -= 1
+      end
+    end
+
+    items
+  end
+end
+
+assert_equals(Solution.run([3, 3, 2, 1, 3, 2, 1]), [1, 1, 2, 2, 3, 3, 3])