For example,
# list A
A = [1, 2, 3, 3, 4, 4, 4, 5, 6]
# list B
B = [1, 2, 3, 3, 4, 5, 5, 5, 6]
are given, and we have to check if elements of the lists have the pattern of [x, x, y, y, y].
list A should return "True": [1, 2, 3, 3, 4, 4, 4, 5, 6]
list B should return "False" as '4' intercepts in the middle: [1, 2, 3, 3, 4, 5, 5, 5, 6]
Just check every possible subarray of length 5 for the pattern. Straightforward way would be:
a = [1, 2, 3, 3, 4, 4, 4, 5, 6]
b = [1, 2, 3, 3, 4, 5, 5, 5, 6]
def is_pattern(alist):
for i in range(0, len(alist) - 4):
sub = alist[i:i + 5]
if sub[0] == sub[1] and (sub[2] == sub[3] == sub[4]):
return True
return False
assert is_pattern(a) is True
assert is_pattern(b) is False
O(n) solution is to iterate the list and count X and Y appearances. Once it breaks the pattern, restore the values accordingly.
Once you find 2 or more appearances you can count Y appearances and return true once it reaches 3.
Otherwise, if count x is less than 2, restore it. If count x is 2 or more but current value doesn't equal to the earlier y, set count x to be count y and set count y to be 1.
a = [1, 2, 3, 3, 3, 4, 4, 4, 5, 6]
b = [1, 2, 3, 3, 4, 5, 5, 5, 6]
c = [1,1,1,1,1]
d = [1, 2, 3, 3, 3, 4, 4, 5, 5, 5, 6]
def is_x_y(arr):
count_x, count_y = 0, 0
x, y = None, None
for val in arr:
if not x:
x = val
if x == val:
count_x += 1
elif count_x >= 2:
if not y:
y = val
if y == val:
count_y +=1
else:
count_x = count_y
x = y
count_y = 1
y = val
else:
count_x = 0
x = None
if count_x >= 2 and count_y == 3:
return True
return False
print(is_x_y(a))
print(is_x_y(b))
print(is_x_y(c))
print(is_x_y(d))
True
False
False
True
if x, x, x, x, x also match your pattern, change the return True condition to also return True on count_x = 5:
if count_x == 5 or (count_x >= 2 and count_y == 3):
return True