Asteroid Collision - Practice Coding Problems

Asteroid Collision - Problem

We are given an array asteroids of integers representing asteroids in a row. The indices represent their relative position in space.

For each asteroid, the absolute value represents its size, and the sign represents its direction (positive meaning right, negative meaning left). Each asteroid moves at the same speed.

Find out the state of the asteroids after all collisions. If two asteroids meet, the smaller one will explode. If both are the same size, both will explode. Two asteroids moving in the same direction will never meet.

Input & Output

Example 1 — Basic Collision

$ Input: asteroids = [5,10,-5]

› Output: [5,10]

💡 Note: The 10 and -5 collide. Since 10 > 5, the -5 explodes. The 5 and 10 never collide.

Example 2 — Chain Reaction

$ Input: asteroids = [8,-8]

› Output: []

💡 Note: The 8 and -8 collide and both explode, leaving an empty array.

Example 3 — Multiple Collisions

$ Input: asteroids = [10,2,-5]

› Output: [10]

💡 Note: The 2 and -5 collide, -5 wins. Then 10 and -5 collide, 10 wins.

Constraints

2 ≤ asteroids.length ≤ 10⁴
-1000 ≤ asteroids[i] ≤ 1000
asteroids[i] ≠ 0

Visualization

Tap to expand

Understanding the Visualization

Input

Array of asteroids with size and direction [5, 10, -5]

Collision

Right-moving (10) meets left-moving (-5)

Result

Larger asteroid survives: [5, 10]

Key Takeaway

🎯 Key Insight: Use a stack to handle collisions between right-moving and left-moving asteroids efficiently

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is that only right-moving asteroids (positive) can collide with left-moving asteroids (negative). Use a stack to efficiently handle chain reactions by processing asteroids left to right. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Solution	O(n)	O(n)	Use stack to handle collisions as we process asteroids left to right
Brute Force Simulation	O(n²)	O(n)	Repeatedly scan for collisions until no more occur

Stack-Based Solution — Algorithm Steps

Step 1: Process each asteroid from left to right
Step 2: For right-moving asteroids, push to stack
Step 3: For left-moving asteroids, resolve collisions with stack top
Step 4: Return remaining asteroids in stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Right-Moving

Add positive asteroids to stack

Handle Collision

Left-moving asteroid collides with stack top

Chain Reaction

Continue collisions until stable state

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* asteroids, int size, int* returnSize) {
    int* stack = malloc(size * sizeof(int));
    int stackSize = 0;
    
    for (int i = 0; i < size; i++) {
        int asteroid = asteroids[i];
        
        if (asteroid > 0) {
            // Right-moving asteroid, no collision yet
            stack[stackSize++] = asteroid;
        } else {
            // Left-moving asteroid, handle collisions
            int asteroidSize = abs(asteroid);
            
            // Keep colliding with right-moving asteroids in stack
            while (stackSize > 0 && stack[stackSize - 1] > 0 && 
                   stack[stackSize - 1] < asteroidSize) {
                stackSize--;
            }
            
            // Check if collision results in mutual destruction
            if (stackSize > 0 && stack[stackSize - 1] == asteroidSize) {
                stackSize--; // Both explode
            } else if (stackSize == 0 || stack[stackSize - 1] < 0) {
                // No collision or collision with another left-moving
                stack[stackSize++] = asteroid;
            }
            // If stack top > asteroidSize, left-moving asteroid explodes (do nothing)
        }
    }
    
    *returnSize = stackSize;
    return stack;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int asteroids[1000];
    int size = 0;
    
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        asteroids[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(asteroids, size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each asteroid is pushed and popped from stack at most once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n asteroids in worst case (all moving right)

⚡ Linearithmic Space

158.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler