1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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])
|
