Задача с собеседования в Zynga

Дан массив целых чисел asteroids, представляющий астероиды, расположенные в ряд. Индексы элементов массива соответствуют их относительному положению в пространстве.
Для каждого астероида абсолютное значение (модуль) определяет его размер, а знак - направление движения (положительный означает движение вправо, отрицательный - влево). Все астероиды движутся с одинаковой скоростью.
Определите состояние астероидов после всех столкновений. Если два астероида встречаются, взрывается меньший из них. Если их размеры равны, взрываются оба. Два астероида, движущиеся в одном направлении, никогда не встретятся.

Пример 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Объяснение: 10 и -5 сталкиваются, в результате остаётся 10. 5 и 10 никогда не столкнутся.

Пример 2:
Input: asteroids = [8,-8]
Output: []
Объяснение: 8 и -8 сталкиваются, взрывая друг друга.

Пример 3:
Input: asteroids = [10,2,-5]
Output: [10]
Объяснение: 2 и -5 сталкиваются, в результате остаётся -5. 10 и -5 сталкиваются, остаётся 10.

Пример 4:
Input: asteroids = [3,5,-6,2,-1,4]
Output: [-6,2,4]
Объяснение: Астероид -6 взрывает астероиды 5 и 3, затем продолжает двигаться влево. С другой стороны, астероид 2 взрывает астероид -1 и продолжает двигаться вправо, не сталкиваясь с астероидом 4.

Ограничения:
2 <= asteroids.length <= 10⁴
-1000 <= asteroids[i] <= 1000
asteroids[i] != 0

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Столкновение происходит между соседними астероидами (они могут не быть соседями в изначальном массиве, а стать ими после взрывов), летящими в разные стороны (с противоположными знаками). И только в том случае, когда астероид, летящий вправо, находится левее астероида, летящего влево. Иначе астероиды просто разлетятся в разные стороны и никогда не столкнутся. Так произойдёт, например, при asteroids = [-1, -2, 1, 2]. Однако при [1, -1, 2, -2], они взорвут друг друга, и стек окажется пуст.

- Используем стек для хранения астероидов, которые ещё не столкнулись или пережили столкновение. Стек удобен тем, что позволяет проверять верхний астероид (последний добавленный) на столкновение с левым. Верхний - ближайший справа к левому, при его взрыве левый продолжит движение и проверит следующий (добавленный раньше) астероид в стеке, который автоматически станет новым ближайшим.

- Симулируем движение:
В цикле while (while позволяет проверять левый астероид на столкновение с несколькими правыми подряд) имитируем столкновение: стек должен быть не пуст, текущий астероид должен лететь влево, а верхний астероид в стеке - лететь вправо:
Чтобы определить, какой взорвётся, высчитываем разницу между их размерами посредством суммирования. Так как мы зашли в цикл while, текущий a всегда отрицательный, а stack[-1] - положительный, знак diff покажет, какой астероид больше:
- если diff отрицательный - левый больше => правый взрывается => удаляем его из стека => левый остаётся и продолжает цикл while, проверяя следующий астероид в стеке;
- если diff положительный - правый больше => левый взрывается, правый остаётся в стеке => обнуляем значение левого, цикл while завершается, так как условие a < 0 больше не выполняется;
- если значение diff равно нулю - размеры равны => оба взрываются => обнуляем левый и удаляем правый из стека, цикл завершается.

- Если после столкновений текущий астероид не равен 0, значит, он выжил. Добавляем его в стек.

Сложность
O(n) - по времени (проходим по массиву 1 раз, каждый астероид может быть добавлен в стек или удалён из него не более 1 раза)
O(n) - по памяти (в худшем случае храним в стеке все элементы массива)

Код
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []

for a in asteroids:
while stack and a < 0 < stack[-1]:
diff = a + stack[-1]
if diff < 0:
stack.pop()
elif diff > 0:
a = 0
else:
a = 0
stack.pop()

if a:
stack.append(a)

return stack

@algoses