LeetCode 735 - Asteroid Collision

The problem gives us a list of integers representing asteroids moving through space in a straight line. Each integer contains two pieces of information: - The absolute value represents the asteroid's size. - The sign represents the direction: - Positive numbers move to the right.

leetcodemediumarraystacksimulation

LeetCode Problem 735

Difficulty: 🟡 Medium
Topics: Array, Stack, Simulation

Solution

Problem Understanding

The problem gives us a list of integers representing asteroids moving through space in a straight line. Each integer contains two pieces of information:

  • The absolute value represents the asteroid's size.

  • The sign represents the direction:

  • Positive numbers move to the right.

  • Negative numbers move to the left.

All asteroids move at the same speed. When two asteroids moving toward each other meet, a collision occurs. The smaller asteroid is destroyed. If both asteroids have the same size, both are destroyed. Asteroids moving in the same direction never collide.

The goal is to return the final state of all surviving asteroids after every possible collision has been resolved.

For example, in the input [5, 10, -5], the asteroid 10 is moving right and -5 is moving left. Since they move toward each other, they collide. The asteroid 10 survives because its size is larger. The asteroid 5 never collides with 10 because both move to the right.

The constraints tell us that the array can contain up to 10^4 asteroids. This means an inefficient simulation that repeatedly scans the array and removes elements could become too slow. We need a solution that processes collisions efficiently, ideally in linear time.

Several edge cases are important:

  • Multiple consecutive collisions can happen, such as [10, 2, -5].
  • Equal-sized asteroids destroy each other completely, such as [8, -8].
  • Asteroids moving in the same direction never interact.
  • A large negative asteroid may destroy many smaller positive asteroids before stopping.
  • Asteroids at the beginning or end of the array may never collide with anything.

A key observation is that collisions only happen when a right-moving asteroid appears before a left-moving asteroid. That means we only need to consider situations where a positive number is followed later by a negative number.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly scan the array looking for adjacent asteroids that will collide.

Whenever we find a pair where the left asteroid is moving right and the right asteroid is moving left, we resolve the collision according to the rules:

  • Remove the smaller asteroid.
  • Remove both if their sizes are equal.

After modifying the array, we restart scanning because new collisions may now become possible.

This approach works because it directly simulates the physical process. However, it is inefficient because removing elements from arrays repeatedly is expensive, and the same asteroids may be revisited many times.

In the worst case, each collision may require shifting many elements, leading to quadratic time complexity.

Optimal Stack Approach

The key insight is that collisions only matter between:

  • A previously seen right-moving asteroid
  • And the current left-moving asteroid

This naturally suggests using a stack.

The stack represents asteroids that are still alive after processing previous collisions. When we encounter a new asteroid:

  • If it moves right, it cannot collide with earlier asteroids, so we push it onto the stack.
  • If it moves left, it may collide with right-moving asteroids already on the stack.

We repeatedly compare the current left-moving asteroid with the top of the stack until one of these happens:

  • The current asteroid explodes.
  • The stack asteroid explodes.
  • Both explode.
  • No more collisions are possible.

This works efficiently because each asteroid is pushed and popped at most once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) or O(n) Repeatedly scans and modifies the array
Optimal O(n) O(n) Uses a stack to resolve collisions efficiently

Algorithm Walkthrough

  1. Initialize an empty stack.

The stack will store asteroids that have survived so far. 2. Iterate through each asteroid in the input array.

We process asteroids from left to right because their positions in the array represent spatial order. 3. If the current asteroid is moving right, push it onto the stack.

A right-moving asteroid cannot collide with earlier asteroids because they are all positioned to its left. 4. If the current asteroid is moving left, check for collisions.

A collision is only possible when:

  • The stack is not empty
  • The top asteroid is moving right
  • The current asteroid is moving left
  1. Compare asteroid sizes during collisions.

Let:

  • top be the right-moving asteroid on the stack
  • current be the left-moving asteroid

There are three possibilities:

  • If abs(current) > top, the stack asteroid explodes.

Remove the stack asteroid and continue checking for more collisions.

  • If abs(current) == top, both asteroids explode.

Remove the stack asteroid and stop processing the current asteroid.

  • If abs(current) < top, the current asteroid explodes.

Stop processing the current asteroid. 6. If the current asteroid survives all collisions, push it onto the stack. 7. After processing all asteroids, return the stack.

Why it works

The stack always maintains the surviving asteroids in their correct order. Any unresolved collision must involve the current left-moving asteroid and the most recent surviving right-moving asteroid. Earlier asteroids cannot skip over later ones, so resolving collisions against the stack top is sufficient. Since every possible collision is handled exactly when it becomes relevant, the final stack represents the correct surviving configuration.

Python Solution

from typing import List

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

        for asteroid in asteroids:
            alive = True

            while alive and asteroid < 0 and stack and stack[-1] > 0:
                if stack[-1] < -asteroid:
                    stack.pop()
                elif stack[-1] == -asteroid:
                    stack.pop()
                    alive = False
                else:
                    alive = False

            if alive:
                stack.append(asteroid)

        return stack

The implementation uses a stack to store surviving asteroids.

The outer loop processes each asteroid one at a time. For every asteroid, the variable alive tracks whether the asteroid survives after potential collisions.

The while loop runs only when a collision is possible. This requires:

  • The current asteroid moving left
  • The stack containing a right-moving asteroid on top

Inside the loop:

  • If the current asteroid is larger, the stack asteroid is removed.
  • If both are equal, both are destroyed.
  • If the stack asteroid is larger, the current asteroid is destroyed.

If the current asteroid survives all collisions, it is added to the stack.

At the end, the stack contains the final surviving asteroids in order.

Go Solution

func asteroidCollision(asteroids []int) []int {
    stack := []int{}

    for _, asteroid := range asteroids {
        alive := true

        for alive && asteroid < 0 && len(stack) > 0 && stack[len(stack)-1] > 0 {
            top := stack[len(stack)-1]

            if top < -asteroid {
                stack = stack[:len(stack)-1]
            } else if top == -asteroid {
                stack = stack[:len(stack)-1]
                alive = false
            } else {
                alive = false
            }
        }

        if alive {
            stack = append(stack, asteroid)
        }
    }

    return stack
}

The Go implementation follows the same logic as the Python version.

Slices are used as stacks. The top element is accessed using stack[len(stack)-1], and popping is done with slicing.

Go does not distinguish between empty and nil slices in a way that affects this algorithm, so initializing with []int{} is sufficient.

Integer overflow is not a concern because asteroid sizes are bounded by 1000.

Worked Examples

Example 1

Input:

[5, 10, -5]
Step Current Asteroid Stack Before Action Stack After
1 5 [] Push [5]
2 10 [5] Push [5, 10]
3 -5 [5, 10] Collides with 10, -5 destroyed [5, 10]

Final result:

[5, 10]

Example 2

Input:

[8, -8]
Step Current Asteroid Stack Before Action Stack After
1 8 [] Push [8]
2 -8 [8] Equal sizes, both destroyed []

Final result:

[]

Example 3

Input:

[10, 2, -5]
Step Current Asteroid Stack Before Action Stack After
1 10 [] Push [10]
2 2 [10] Push [10, 2]
3 -5 [10, 2] 2 destroyed [10]
4 -5 [10] -5 destroyed by 10 [10]

Final result:

[10]

Example 4

Input:

[3, 5, -6, 2, -1, 4]
Step Current Asteroid Stack Before Action Stack After
1 3 [] Push [3]
2 5 [3] Push [3, 5]
3 -6 [3, 5] 5 destroyed [3]
4 -6 [3] 3 destroyed []
5 -6 [] Push [-6]
6 2 [-6] Push [-6, 2]
7 -1 [-6, 2] -1 destroyed by 2 [-6, 2]
8 4 [-6, 2] Push [-6, 2, 4]

Final result:

[-6, 2, 4]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each asteroid is pushed and popped at most once
Space O(n) The stack may store all asteroids

The time complexity is linear because every asteroid enters the stack at most once and leaves the stack at most once. Even though there is a nested while loop, the total number of stack operations across the entire algorithm is bounded by O(n).

The space complexity is O(n) in the worst case when no collisions occur and every asteroid remains in the stack.

Test Cases

from typing import List

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

        for asteroid in asteroids:
            alive = True

            while alive and asteroid < 0 and stack and stack[-1] > 0:
                if stack[-1] < -asteroid:
                    stack.pop()
                elif stack[-1] == -asteroid:
                    stack.pop()
                    alive = False
                else:
                    alive = False

            if alive:
                stack.append(asteroid)

        return stack

solution = Solution()

assert solution.asteroidCollision([5, 10, -5]) == [5, 10]  # smaller negative asteroid destroyed
assert solution.asteroidCollision([8, -8]) == []  # equal-sized asteroids destroy each other
assert solution.asteroidCollision([10, 2, -5]) == [10]  # chain collision
assert solution.asteroidCollision([3, 5, -6, 2, -1, 4]) == [-6, 2, 4]  # multiple independent collisions

assert solution.asteroidCollision([1, 2, 3]) == [1, 2, 3]  # all moving right
assert solution.asteroidCollision([-1, -2, -3]) == [-1, -2, -3]  # all moving left
assert solution.asteroidCollision([1, -2]) == [-2]  # larger negative asteroid survives
assert solution.asteroidCollision([2, -1]) == [2]  # larger positive asteroid survives
assert solution.asteroidCollision([1, -1]) == []  # exact cancellation

assert solution.asteroidCollision([4, 3, 2, -10]) == [-10]  # one asteroid destroys many
assert solution.asteroidCollision([10, -2, -3, -4]) == [10]  # large positive survives repeated attacks
assert solution.asteroidCollision([-2, -1, 1, 2]) == [-2, -1, 1, 2]  # no collisions possible

assert solution.asteroidCollision([1, 2, -2, -1]) == []  # cascading equal collisions
assert solution.asteroidCollision([5]) == [5]  # single asteroid
assert solution.asteroidCollision([-5]) == [-5]  # single negative asteroid
Test Why
[5, 10, -5] Validates standard collision behavior
[8, -8] Validates equal-size destruction
[10, 2, -5] Validates chain collisions
[3, 5, -6, 2, -1, 4] Validates multiple independent collision regions
[1, 2, 3] Validates no collisions when moving right
[-1, -2, -3] Validates no collisions when moving left
[1, -2] Validates larger negative asteroid survival
[2, -1] Validates larger positive asteroid survival
[1, -1] Validates exact cancellation
[4, 3, 2, -10] Validates repeated popping from stack
[10, -2, -3, -4] Validates one large positive surviving many collisions
[-2, -1, 1, 2] Validates separated directions without collisions
[1, 2, -2, -1] Validates cascading equal collisions
[5] Validates minimal single-element case
[-5] Validates minimal single negative case

Edge Cases

One important edge case occurs when multiple collisions happen in sequence. For example, [10, 2, -5] requires the asteroid -5 to first destroy 2 and then collide again with 10. A naive implementation that only checks one collision per asteroid would fail here. The stack-based solution correctly continues processing collisions in a loop until the asteroid either explodes or survives.

Another tricky case is equal-sized asteroids such as [8, -8]. Both asteroids must disappear completely. Some implementations accidentally leave one asteroid behind because they do not handle the equality case separately. This implementation explicitly checks for equality and removes both asteroids.

A third important edge case is when no collisions are possible, such as [-2, -1, 1, 2]. Even though positive and negative asteroids exist together, they move away from each other because the negative asteroids are already to the left. The algorithm correctly avoids collisions by only checking when a right-moving asteroid is on the stack and the current asteroid moves left.

Another subtle edge case involves one large asteroid destroying many smaller ones, such as [4, 3, 2, -10]. The asteroid -10 must repeatedly collide until all smaller right-moving asteroids are removed. The while loop ensures this chain reaction is processed completely before continuing.

Finally, arrays where all asteroids move in the same direction require no collisions at all. The stack handles this naturally because the collision condition is never triggered, so all asteroids remain unchanged.