1def assert_equals(x, y)
 2  raise [x, y].inspect unless x == y
 3end
 4
 5=begin
 6Sorting algorithm would yield.
 7time: O(nlogn)
 8
 9Let's see if we can do this in O(n)
10
11
12             t
13 h
14|3|3|2|1|3|2|1|
15
16=end
17
18class Solution
19  # time: O(n)
20  # space: O(1)
21  def self.run(items)
22    h = 0
23    t = items.size - 1
24
25    while h < t
26      puts [h, items, t].inspect
27
28      if items[h] == 1
29        h += 1
30      elsif items[t] == 3
31        t -= 1
32      elsif items[h] == 3
33        tmp = items[h]
34        items[h] = items[t]
35        items[t] = tmp
36      elsif items[t] == 1
37        tmp = items[t]
38        items[t] = items[h]
39        items[h] = tmp
40      else
41        t -= 1
42      end
43    end
44
45    items
46  end
47end
48
49assert_equals(Solution.run([3, 3, 2, 1, 3, 2, 1]), [1, 1, 2, 2, 3, 3, 3])