"""
Google phone interview - Remove repeating numbers
Given a 1-d array candy crush, return the shortest array after removing all the continuous same numbers (the repeating number >= 3)
input: 1-d array [1, 3, 3, 3, 2, 2, 2, 3, 1]
return: [1, 1]
Time complexity should be better than O(n^2)
Mod edit: To slow down the posting of O(n^2) and O(n) "correct" solutions, here is another testcase:
[3,1,2,2,2,1,1,1,2,2,3,1,1,2,2,2,1,1,1,2,3] should
return [3,1,3,2,3]
"""


# BFS
def RemoveRepeatingNumbers(array):
    stack_runs = []
    stack_arrays = [array]
    res = array

    while len(stack_arrays) > 0:
        # reseting info from last loop
        i = 0
        repeat_nums = None
        # current_array
        array = stack_arrays[0]

        for j in range(1, len(array)):
            # checking list[i] == list[j]
            if array[j] != array[i]:
                # reseting j to one less than i for the next run through the loop
                i = j
                # checking for old stored repeating digits
                if repeat_nums != None:
                    # adding repeat nums to stack
                    stack_runs.append(repeat_nums)
                    repeat_nums = None
            # checking for repeating digits
            elif (j - i) >= 2:
                repeat_nums = (i, j)

        # check for runs at the end of array [2,1,1,1] --- > finds the [1,1,1]
        if repeat_nums != None and array[-1] == array[-2] == array[-3]:
            # adding repeat nums to stack
            stack_runs.append(repeat_nums)

        # remove consecutive digit runs
        for i, j in stack_runs:
            new_array = array[:i] + array[j + 1:]
            stack_arrays.append(new_array)

        # empty stacks & delete current array & check for new answer
        stack_runs = []
        if len(res) > len(array):
            res = array
        del stack_arrays[0]

    return res


print(RemoveRepeatingNumbers([1, 3, 3, 3, 2, 2, 2, 3, 1]))
print(RemoveRepeatingNumbers([3, 1, 2, 2, 2, 1, 1, 1, 2, 2, 3, 1, 1, 2, 2, 2, 1, 1, 1, 2, 3]))
print(RemoveRepeatingNumbers([2, 1, 1, 1, 2, 2, 2, 1, 3, 3, 3, 1, 2, 2, 2, 1, 1, 1, 2]))
print(RemoveRepeatingNumbers([2, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 2, 3]))
print(RemoveRepeatingNumbers([1, 1, 2, 2, 3, 1, 3, 2, 2, 1, 1]))
print(RemoveRepeatingNumbers([1, 3, 3, 3, 2, 2, 2, 3, 1]))
print(RemoveRepeatingNumbers([1, 4, 4, 4, 3, 3, 3, 2, 2, 2, 4, 3, 3, 3, 4, 1, 1]))
print(RemoveRepeatingNumbers([1, 1, 1]))
print(RemoveRepeatingNumbers([1, 2, 3]))