forked from MTrajK/coding-problems
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsort_rgb_array.py
More file actions
109 lines (85 loc) · 2.41 KB
/
sort_rgb_array.py
File metadata and controls
109 lines (85 loc) · 2.41 KB
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
'''
Sort RGB Array
Given an array of strictly the characters 'R', 'G', and 'B', segregate
the values of the array so that all the Rs come first, the Gs come second, and the Bs come last.
You can only swap elements of the array.
Do this in linear time and in-place.
Input: ['G', 'B', 'R', 'R', 'B', 'R', 'G']
Output: ['R', 'R', 'R', 'G', 'G', 'B', 'B']
=========================================
Play with pointers/indices and swap elements. (only one iteration)
Save the last R, G and B indices, when adding some color, move the rest indices by 1.
Time Complexity: O(N)
Space Complexity: O(1)
Count R, G, B and populate the array after that. (2 iterations)
Time Complexity: O(N)
Space Complexity: O(1)
'''
############
# Solution #
############
def sort_rgb_array(arr):
n = len(arr)
# indexes/pointers of the last element of each color
r, g, b = 0, 0, 0
for i in range(n):
# swap the element and move the pointer
if arr[i] == 'R':
temp = arr[i]
arr[i] = arr[r]
arr[r] = temp
r += 1
# move pointer
if r > g:
g = r
# swap the element and move the pointer
if arr[i] == 'G':
temp = arr[i]
arr[i] = arr[g]
arr[g] = temp
g += 1
# move pointer
if g > b:
b = g
# swap the element and move the pointer
if arr[i] == 'B':
temp = arr[i]
arr[i] = arr[b]
arr[b] = temp
b += 1
return arr
##############
# Solution 2 #
##############
def sort_rgb_array_2(arr):
rgb = {
'R': 0,
'G': 0,
'B': 0
}
# count colors
for c in arr:
rgb[c] += 1
# adjust the intervals
rgb['G'] += rgb['R']
rgb['B'] += rgb['G']
# assign colors
for i in range(len(arr)):
if i < rgb['R']:
arr[i] = 'R'
elif i < rgb['G']:
arr[i] = 'G'
else:
arr[i] = 'B'
return arr
###########
# Testing #
###########
# Test 1
# Correct result => ['R', 'R', 'R', 'G', 'G', 'B', 'B']
print(sort_rgb_array(['G', 'B', 'R', 'R', 'B', 'R', 'G']))
print(sort_rgb_array_2(['G', 'B', 'R', 'R', 'B', 'R', 'G']))
# Test 2
# Correct result => ['R', 'R', 'G', 'G', 'B', 'B', 'B']
print(sort_rgb_array(['B', 'B', 'B', 'G', 'G', 'R', 'R']))
print(sort_rgb_array_2(['B', 'B', 'B', 'G', 'G', 'R', 'R']))