Asteroid Collision

📋

Problem

Imagine a line of asteroids moving in space, some moving left and some moving right. When they collide, only the bigger one survives. Can you predict which asteroids remain after all collisions?

You are given an array of integers asteroids representing asteroids in a row. 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. When two asteroids moving in opposite directions collide, the smaller one explodes. If both are the same size, both explode. Asteroids moving in the same direction will never collide. Return an array representing the state of the asteroids after all collisions.

1 ≤ asteroids.length ≤ 10^5-1000 ≤ asteroids[i] ≤ 1000asteroids[i] != 0

Edge cases: All asteroids moving in the same direction → output is the same as inputAll asteroids moving left → output is the same as inputAll asteroids moving right → output is the same as input

</>

IDE

def asteroidCollision(asteroids: list[int]) -> list[int]:public int[] asteroidCollision(int[] asteroids)vector<int> asteroidCollision(vector<int> &asteroids)function asteroidCollision(asteroids)

def asteroidCollision(asteroids):
    # Write your solution here
    pass

class Solution {
    public int[] asteroidCollision(int[] asteroids) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> asteroidCollision(vector<int> &asteroids) {
    // Write your solution here
    return {};
}

function asteroidCollision(asteroids) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [5, 10, -5]No collision simulation performed; returns input as is.✅ Implement stack simulation to resolve collisions between right and left moving asteroids.

Wrong: [10, -5]Fails to remove smaller asteroid on collision; only removes one side or none.✅ When collision occurs, remove smaller asteroid from stack or skip adding current asteroid accordingly.

Wrong: [10, 2, -5]Greedy approach stops after first collision; does not resolve all collisions for current asteroid.✅ Use a while loop to resolve collisions until current asteroid is destroyed or no collision possible.

Wrong: [1, -1, -2, -2]Equal size collisions not removing both asteroids; one remains incorrectly.✅ Pop stack top and skip adding current asteroid when sizes are equal.

Wrong: TLE or timeoutUsing O(n^2) brute force simulation with nested loops.✅ Implement O(n) stack simulation to handle collisions efficiently.

✓

Test Cases

Focus on handling base cases like empty or single-element arrays correctly.

Ensure your collision logic fully resolves all interactions, not just the first one.

Optimize your solution to linear time using a stack to avoid timeouts.

t1_01basic

Input{"asteroids":[5,10,-5]}

Expected[5,10]

⏱ Performance - must finish in 2000ms

The asteroid 10 and -5 collide, -5 explodes. 5 and 10 never collide.

💡 Consider how asteroids moving right and left collide only when they meet.

💡 Use a stack to simulate collisions: push right-moving asteroids, resolve collisions with left-moving ones.

💡 When a left-moving asteroid meets a smaller right-moving one, pop the smaller; if equal size, pop both.

Why it failed: Failed basic collision logic: likely not handling collisions between right and left moving asteroids correctly. Fix by simulating with a stack and resolving collisions when a left-moving asteroid meets right-moving ones.

✓ Correctly simulates collisions using stack approach.

t1_02basic

Input{"asteroids":[8,-8]}

Expected[]

⏱ Performance - must finish in 2000ms

Asteroids 8 and -8 collide and both explode because they are equal size.

💡 Check what happens when two asteroids of equal size collide.

💡 Ensure both asteroids are removed from the stack when sizes are equal.

💡 Pop the right-moving asteroid and discard the left-moving one as well when sizes match.

Why it failed: Incorrect handling of equal size collisions: both asteroids must be removed. Fix by popping the stack and skipping adding the current asteroid when sizes match.

✓ Handles equal size collisions correctly by removing both asteroids.

t2_01edge

Input{"asteroids":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input returns empty output.

💡 Consider the behavior when no asteroids are present.

💡 The output should be empty if input is empty.

💡 Return an empty list immediately if input length is zero.

Why it failed: Fails empty input case: code likely does not handle zero-length input properly. Fix by adding a check for empty input and returning empty list.

✓ Correctly returns empty list for empty input.

t2_02edge

Input{"asteroids":[10]}

Expected[10]

⏱ Performance - must finish in 2000ms

Single asteroid remains as is since no collisions possible.

💡 Check behavior with only one asteroid.

💡 No collisions can occur with a single asteroid.

💡 Return the input list as is when length is one.

Why it failed: Fails single element case: code may incorrectly modify or remove single asteroid. Fix by ensuring single asteroid is returned unchanged.

✓ Correctly returns single asteroid unchanged.

t2_03edge

Input{"asteroids":[-1,-2,-3]}

Expected[-1,-2,-3]

⏱ Performance - must finish in 2000ms

All asteroids moving left; no collisions occur.

💡 Asteroids moving in the same direction never collide.

💡 Check if all asteroids have the same sign.

💡 Return the input as is if all move left or all move right.

Why it failed: Fails all same direction case: code may incorrectly simulate collisions when none should occur. Fix by skipping collision logic if all asteroids move in same direction.

✓ Correctly returns all left-moving asteroids unchanged.

t3_01corner

Input{"asteroids":[10,2,-5]}

Expected[10]

⏱ Performance - must finish in 2000ms

Smaller right-moving asteroid 2 explodes when colliding with -5; 10 remains.

💡 Beware of greedy approach that removes only first collision.

💡 Check all collisions until no more possible for current asteroid.

💡 Use a while loop to resolve collisions with stack top until stable.

Why it failed: Fails greedy collision resolution: stops after first collision instead of resolving all. Fix by looping to resolve collisions until current asteroid is destroyed or stack top is safe.

✓ Correctly resolves all collisions for each asteroid.

t3_02corner

Input{"asteroids":[1,-1,-2,-2]}

Expected[-2,-2]

⏱ Performance - must finish in 2000ms

1 and -1 collide and both explode; remaining -2, -2 move left.

💡 Check that collisions between equal size asteroids remove both.

💡 Ensure stack top is popped and current asteroid discarded on equal size.

💡 Do not add current asteroid if it explodes in collision.

Why it failed: Fails equal size collision removal in chain: code may add exploded asteroid to stack. Fix by skipping push when equal size collision occurs.

✓ Correctly removes both asteroids on equal size collision.

t3_03corner

Input{"asteroids":[5,10,-10,-5]}

Expected[]

⏱ Performance - must finish in 2000ms

10 and -10 collide and both explode; then 5 and -5 collide and both explode; no asteroids remain.

💡 Check for multiple sequential collisions in stack simulation.

💡 Ensure stack top is updated after each collision before next.

💡 Use a loop to handle multiple collisions until stable.

Why it failed: Fails multiple sequential collisions: code may not update stack top after each collision. Fix by looping collision checks until no more collisions possible.

✓ Correctly handles multiple sequential collisions.

t4_01performance

Input{"asteroids":[1000,-999,998,-997,996,-995,994,-993,992,-991,990,-989,988,-987,986,-985,984,-983,982,-981,980,-979,978,-977,976,-975,974,-973,972,-971,970,-969,968,-967,966,-965,964,-963,962,-961,960,-959,958,-957,956,-955,954,-953,952,-951,950,-949,948,-947,946,-945,944,-943,942,-941,940,-939,938,-937,936,-935,934,-933,932,-931,930,-929,928,-927,926,-925,924,-923,922,-921,920,-919,918,-917,916,-915,914,-913,912,-911,910,-909,908,-907,906,-905,904,-903,902,-901]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 alternating large asteroids; O(n) stack simulation must complete within 2s.

💡 Brute force O(n^2) simulation will time out on large inputs.

💡 Use stack-based O(n) approach to handle collisions efficiently.

💡 Avoid nested loops; process each asteroid once with stack.

Why it failed: TLE due to O(n^2) brute force simulation. Fix by implementing O(n) stack simulation approach.

✓ Efficient O(n) stack simulation confirmed by passing performance test.

Practice

1. Consider the following Python code that evaluates Reverse Polish Notation expressions. What is the final output when the input tokens are ["4", "13", "5", "/", "+"]?

class Solution:
    def evalRPN(self, tokens):
        import operator
        ops = {
            '+': operator.add,
            '-': operator.sub,
            '*': operator.mul,
            '/': lambda x, y: int(x / y),
        }
        stack = []
        for token in tokens:
            if token in ops:
                right = stack.pop()
                left = stack.pop()
                stack.append(ops[token](left, right))
            else:
                stack.append(int(token))
        return stack.pop()

sol = Solution()
print(sol.evalRPN(["4", "13", "5", "/", "+"]))

easy

A. 2

B. 6

C. 8

D. 10

Solution

1. Step 1: Trace stack operations

   Push 4, push 13, push 5; then '/' operator pops 5 and 13, computes int(13/5) = 2, push 2; then '+' operator pops 2 and 4, computes 4+2=6, push 6.

2. Step 2: Final stack pop

   Pop the last element 6 as the result.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Stack correctly reflects intermediate results [OK]

Hint: Remember integer division truncates toward zero [OK]

Common Mistakes:

• Swapping left and right operands
• Using float division instead of int
• Off-by-one in stack pops

2. You are given two arrays nums1 and nums2, where nums1 is a subset of nums2. For each element in nums1, you want to find the first greater element to its right in nums2. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Use a monotonic stack to precompute the next greater element for all elements in nums2, then map results for nums1.

B. Use nested loops to check each element of nums1 against all elements to its right in nums2.

C. Use dynamic programming to store the next greater element for each index in nums2.

D. Sort nums2 and use binary search to find the next greater element for each element in nums1.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the next greater element for each element in nums1 based on their positions in nums2, which is a classic next greater element problem.

2. Step 2: Identify the optimal approach

   Using a monotonic stack to precompute next greater elements for all nums2 elements allows O(n) processing, then mapping results for nums1 is O(m), leading to an overall O(n + m) time complexity.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Monotonic stack approach is well-known for next greater element problems [OK]

Hint: Monotonic stack precomputes next greater efficiently [OK]

Common Mistakes:

• Using nested loops leads to O(m*n) time, too slow for large inputs
• Sorting nums2 loses original order, invalidating next greater logic
• Dynamic programming is not applicable here as no overlapping subproblems

3. You are given a circular array of integers and need to find, for each element, the next greater element when traversing the array circularly. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking each element's next greater by scanning forward twice

B. Greedy approach selecting next greater element by local comparisons only

C. Dynamic programming with memoization of next greater elements

D. Monotonic stack with explicit circular array copy to simulate circular traversal

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the next greater element for each item in a circular array, which means elements after the end wrap around to the start.

2. Step 2: Identify algorithmic pattern

   Brute force is O(n²), greedy/local comparisons fail on circular wrap, and DP is not naturally suited. Monotonic stack with explicit circular array copy simulates circular traversal efficiently in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Monotonic stack with doubled array -> O(n) time [OK]

Hint: Circular array + next greater -> monotonic stack with doubling [OK]

Common Mistakes:

• Assuming greedy local comparisons suffice for circular arrays
• Thinking DP applies directly without circular simulation
• Believing brute force is optimal for large inputs

4. What is the time complexity of the optimal monotonic stack algorithm for detecting the 132 pattern in an array of length n?

medium

A. O(n) because each element is pushed and popped at most once

B. O(n^2) due to nested loops inside the stack operations

C. O(n log n) due to sorting implicit in stack operations

D. O(n^3) because of triple nested conditions

Solution

1. Step 1: Identify operations per element

   Each element is pushed onto the stack once and popped at most once, so total stack operations are O(n).

2. Step 2: Confirm no nested loops

   The algorithm iterates once over the array, with inner while loop popping elements but total pops across all iterations sum to n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time confirmed by amortized stack operations [OK]

Hint: Stack push/pop amortized to O(n) total [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Thinking stack operations imply sorting
• Confusing with brute force complexity

5. Suppose you want to extend the one-queue stack implementation to support a multiPop(k) operation that pops the top k elements at once. Which modification maintains correct stack order and efficient operations?

hard

A. Perform k consecutive pop() calls on the queue, each O(1), total O(k).

B. Modify push to rotate the queue k times after each push to prepare for multiPop.

C. Use two queues instead, transferring elements to support batch pop efficiently.

D. Store elements in a separate stack data structure internally to support multiPop efficiently.

Solution

1. Step 1: Understand multiPop operation

   multiPop(k) means popping top k elements in stack order.

2. Step 2: Analyze one-queue approach

   Since pop is O(1), performing k pops consecutively is O(k) and maintains order.

3. Step 3: Evaluate other options

   Rotating queue k times after push breaks order; two queues add complexity; using stack internally violates constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Consecutive pops maintain order and are efficient in one-queue approach [OK]

Hint: multiPop(k) = k consecutive O(1) pops in one-queue stack [OK]

Common Mistakes:

• Trying to rotate queue multiple times per push unnecessarily
• Switching to two queues without reason
• Using stack internally violating problem constraints