Asteroid Collision

▶

Steps

setup

Initialize empty stack

Start with an empty stack to hold surviving asteroids as we process the input list.

💡 The stack will simulate the state of asteroids after collisions; starting empty means no asteroids processed yet.

Line:

stack = []

💡 The stack is the core data structure to track surviving asteroids.

traverse

Process first asteroid 5

Take the first asteroid 5 from the input and prepare to push it onto the stack since the stack is empty.

💡 No collision is possible because the stack is empty, so the asteroid will survive.

Line:

for a in asteroids:
    alive = True

💡 The first asteroid always survives because there is nothing to collide with.

insert

Push asteroid 5 onto stack

Since asteroid 5 is alive and no collision occurs, push it onto the stack.

💡 Pushing means the asteroid survived all checks and will be part of the final result unless future collisions remove it.

Line:

if alive:
    stack.append(a)

💡 Asteroid 5 is now stored as a survivor on the stack.

traverse

Process second asteroid 10

Move to the second asteroid 10 and prepare to check for collisions with the stack top.

💡 We must check if asteroid 10 collides with any asteroid on the stack before pushing it.

Line:

for a in asteroids:
    alive = True

💡 Collision checks start when the new asteroid is negative and stack top is positive; here 10 is positive so no collision.

insert

Push asteroid 10 onto stack

Asteroid 10 is positive and no collision condition is met, so push it onto the stack.

💡 Positive asteroids moving right do not collide with previous positive asteroids moving right.

Line:

if alive:
    stack.append(a)

💡 Stack now holds two surviving asteroids moving right.

traverse

Process third asteroid -5

Now process asteroid -5, which moves left and may collide with asteroids moving right on the stack top.

💡 Negative asteroid moving left can collide with positive asteroids moving right on the stack top.

Line:

for a in asteroids:
    alive = True

💡 Collision checks will start because stack top is positive and current asteroid is negative.

compare

Check collision: stack top 10 vs asteroid -5

Compare top of stack 10 (positive) with current asteroid -5 (negative) to determine collision outcome.

💡 Collision occurs only if stack top > 0 and current asteroid < 0, which is true here.

Line:

while alive and stack and stack[-1] > 0 and a < 0:

💡 Collision condition met, so we must compare sizes to decide which asteroid explodes.

compare

Compare sizes: 10 vs 5 (absolute of -5)

Since 10 > 5, asteroid -5 explodes and will not be pushed onto the stack.

💡 If stack top is larger, the incoming asteroid explodes and is discarded.

Line:

elif stack[-1] == -a:
    stack.pop()
    alive = False
else:
    alive = False

💡 The smaller asteroid moving left explodes when colliding with a larger asteroid moving right.

insert

Skip pushing asteroid -5 since it exploded

Since asteroid -5 exploded (alive is False), it is not pushed onto the stack.

💡 Only asteroids that survive collisions are pushed onto the stack.

Line:

if alive:
    stack.append(a)

💡 The stack remains unchanged after processing asteroid -5.

reconstruct

Return final stack as surviving asteroids

All asteroids processed; return the stack containing surviving asteroids [5, 10].

💡 The stack now holds the final answer representing asteroids that did not explode.

Line:

return stack

💡 The final stack is the output of the algorithm.

def asteroidCollision(asteroids):
    stack = []  # STEP 1: Initialize empty stack
    for a in asteroids:  # STEP 2,4,6: Traverse each asteroid
        alive = True  # STEP 2,4,6: Assume asteroid is alive
        while alive and stack and stack[-1] > 0 and a < 0:  # STEP 7: Collision check
            if stack[-1] < -a:  # STEP 8: Stack top smaller, pop it
                stack.pop()  # STEP 8: Pop smaller asteroid
            elif stack[-1] == -a:  # STEP 8: Equal size, both explode
                stack.pop()  # STEP 8: Pop equal asteroid
                alive = False  # STEP 8: Current asteroid explodes
            else:  # STEP 8: Stack top larger, current explodes
                alive = False  # STEP 8: Current asteroid explodes
        if alive:  # STEP 3,5,9: Push surviving asteroid
            stack.append(a)
    return stack  # STEP 10: Return survivors

if __name__ == '__main__':
    print(asteroidCollision([5,10,-5]))  # Output: [5, 10]

📊

Asteroid Collision - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the stack simulates collisions and why some asteroids explode while others survive, making the algorithm's logic clear without needing to read code.

no_op

Stack (top→bottom)

empty

no_opElement[0]: 5

Stack (top→bottom)

empty

pushElement[0]: 5

Stack (top→bottom)

5

↑ pushed: 5

no_opElement[1]: 10

Stack (top→bottom)

5

pushElement[1]: 10

Stack (top→bottom)

10

5

↑ pushed: 10

no_opElement[2]: -5

Stack (top→bottom)

10

5

peekElement[2]: -5

Stack (top→bottom)

10

5

no_opElement[2]: -5

Stack (top→bottom)

10

5

no_opElement[2]: -5

Stack (top→bottom)

10

5

no_opElement[2]: -5

Stack (top→bottom)

10

5

Contributes: [5,10]

Key Takeaways

✓ The stack simulates the state of surviving asteroids after each collision, making the problem manageable.

This insight is hard to see from code alone because the stack's dynamic changes are subtle without visualization.

✓ Only asteroids moving in opposite directions (positive on stack top and negative incoming) can collide, triggering the while loop.

Understanding this condition clarifies why some asteroids are pushed immediately and others cause collisions.

✓ When a collision occurs, the larger asteroid survives and the smaller explodes, which is reflected by popping from the stack or skipping push.

Seeing the exact moment an asteroid is popped or skipped helps grasp the collision resolution logic concretely.

Practice

1. You need to evaluate a string expression containing non-negative integers and the operators +, -, *, and /, without any parentheses. The expression must respect operator precedence (multiplication and division before addition and subtraction). Which approach guarantees correct evaluation of such expressions?

easy

A. Use a stack to immediately evaluate multiplication and division, then sum the results for addition and subtraction.

B. Evaluate the expression strictly from left to right, ignoring operator precedence.

C. Use dynamic programming to store intermediate results for all subexpressions.

D. Sort the operators by precedence and evaluate all operators of the same precedence level in separate passes.

Solution

1. Step 1: Understand operator precedence

   Multiplication and division must be evaluated before addition and subtraction to get the correct result.

2. Step 2: Recognize stack-based immediate evaluation

   Using a stack to immediately compute * and / while postponing + and - ensures correct precedence without complex parsing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Stack-based immediate evaluation is the classic pattern for this problem [OK]

Hint: Stack handles precedence by immediate * and / evaluation [OK]

Common Mistakes:

• Ignoring operator precedence
• Trying to evaluate left to right
• Using DP unnecessarily

2. The following code attempts to find the longest valid parentheses substring using a stack-based approach. Identify the line containing the subtle bug that causes incorrect results for inputs starting with valid parentheses at index 0.

def longestValidParentheses(s: str) -> int:
    stack = []
    max_len = 0
    stack.append(-1)  # Initialize stack with -1
    for i, ch in enumerate(s):
        if ch == '(': 
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                max_len = max(max_len, i - stack[-1])
    return max_len

medium

A. Line 4: stack initialized with -1

B. Line 9: popping from stack without checking if empty

C. Line 3: stack initialized as empty list

D. Line 12: resetting stack with current index when empty

Solution

1. Step 1: Analyze stack pop operation

   Line 9 pops from stack without checking if stack is empty, which can cause runtime error or incorrect behavior if stack is empty.

2. Step 2: Understand initialization and reset logic

   Stack initialized with -1 (line 4) is correct to handle valid substrings starting at index 0; resetting stack with current index (line 12) is also correct.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Pop without empty check leads to subtle bugs on edge cases [OK]

Hint: Popping stack without empty check causes subtle bugs [OK]

Common Mistakes:

• Forgetting to initialize stack with -1
• Not checking stack emptiness before pop
• Incorrect reset of stack after imbalance

3. The following code attempts to solve the Next Greater Element II problem using a monotonic stack and explicit circular array copy. Identify the line containing the subtle bug that causes incorrect results on some inputs.

from typing import List

def nextGreaterElements(nums: List[int]) -> List[int]:
    n = len(nums)
    doubled = nums + nums
    answer = [-1] * n
    stack = []
    for i, num in enumerate(doubled):
        while stack and doubled[stack[-1]] < num:
            idx = stack.pop()
            if idx < n:
                answer[idx] = num
        if i < n:
            stack.append(i)  # Bug here
    return answer

medium

A. Line pushing indices onto stack only when i < n

B. Line popping from stack while top element is less than current num

C. Line initializing answer array with -1

D. Line creating doubled array by concatenation

Solution

1. Step 1: Understand stack push condition

   Only pushing indices when i < n means indices from second pass (i ≥ n) are never pushed, so some elements' next greater values are missed.

2. Step 2: Identify correct push strategy

   To simulate circular array correctly, indices should be pushed for the entire doubled array, or a different approach used. Restricting push to i < n causes missing updates.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bug is in restricting stack pushes to first pass only [OK]

Hint: Pushing indices only in first pass misses circular wrap [OK]

Common Mistakes:

• Not pushing indices in second pass causing incomplete updates
• Using values instead of indices in stack
• Not initializing answer array with -1

4. Consider the following buggy code for validating parentheses. Which line contains the subtle bug that can cause a runtime error or incorrect result?

def isValid(s: str) -> bool:
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if stack[-1] != pairs[char]:
                return False
            stack.pop()
        else:
            return False
    return not stack

medium

A. Line checking if stack[-1] != pairs[char]

B. Line popping from stack: stack.pop()

C. Line appending opening bracket: stack.append(char)

D. Line iterating over characters: for char in s

Solution

1. Step 1: Identify potential runtime errors

   Accessing stack[-1] without checking if stack is empty can cause IndexError if stack is empty.

2. Step 2: Check code logic

   Before comparing stack[-1], code must verify stack is not empty. Missing this check causes runtime error or incorrect acceptance.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing empty stack check before stack[-1] access [OK]

Hint: Always check stack emptiness before accessing top [OK]

Common Mistakes:

• Forgetting to check if stack is empty before popping or peeking

5. Suppose the problem is modified so that digits can be removed multiple times (i.e., you can remove the same digit repeatedly if it appears multiple times), or the input string can contain non-digit characters. Which modification to the original algorithm is necessary to handle these changes correctly?

hard

A. Use a frequency map to track digit counts and remove digits greedily based on frequency

B. Switch to a brute force approach generating all subsequences since greedy no longer applies

C. Preprocess input to filter out non-digit characters and apply the same monotonic stack algorithm without changes

D. Modify the stack to allow re-insertion of digits and skip non-digit characters during iteration

Solution

1. Step 1: Analyze impact of repeated removals and non-digit chars

   Allowing multiple removals of the same digit requires the stack to handle re-insertion or multiple passes. Non-digit chars must be skipped to avoid errors.

2. Step 2: Identify necessary algorithm modification

   The stack must be adapted to allow re-insertion or multiple removals, and iteration must skip non-digit characters to maintain correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Handling input sanitization and stack flexibility is key for this variant [OK]

Hint: Stack must handle re-insertions and skip invalid chars [OK]

Common Mistakes:

• Assuming original algorithm works unchanged
• Ignoring input sanitization
• Switching to brute force unnecessarily