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])