Practice/Amazon/Leetcode 735. Asteroid Collision

Leetcode 735. Asteroid Collision

CodingMust

Problem

You are monitoring space debris traveling in a straight line. Each piece of debris is represented by an integer where:

• The absolute value represents its size
• A positive value means it's moving to the right
• A negative value means it's moving to the left

All debris pieces travel at the same speed. When two pieces collide:

• The smaller piece explodes and disappears
• If both pieces are the same size, both explode
• The larger piece continues moving

Collisions only occur between debris moving toward each other (a piece moving right followed by a piece moving left). Determine which debris pieces remain after all collisions have occurred.

Requirements

1. Return an array representing the final state of debris pieces after all collisions
2. Debris pieces moving in the same direction never collide
3. Process collisions in the order they would naturally occur
4. Handle chain reactions where one debris piece may collide with multiple others

Constraints

• 2 ≤ debris.length ≤ 10,000
• -1000 ≤ debris[i] ≤ 1000
• debris[i] ≠ 0
• Expected time complexity: O(n) where n is the number of debris pieces
• Expected space complexity: O(n)

Examples

Example 1:

Input: debris = [5, 10, -5] Output: [5, 10] Explanation: The debris piece 10 moving right collides with -5 moving left. Since 10 > 5, the piece with size 5 explodes, leaving [5, 10].

Example 2:

Input: debris = [8, -8] Output: [] Explanation: The debris pieces 8 and -8 collide. Since they have equal size, both explode, leaving no debris.

Example 3:

Input: debris = [-2, -1, 1, 2] Output: [-2, -1, 1, 2] Explanation: The pieces moving left (-2, -1) never collide with the pieces moving right (1, 2) because they're moving away from each other.

Example 4:

Input: debris = [10, 2, -5] Output: [10] Explanation: First, 2 and -5 collide, -5 wins. Then 10 and -5 collide, 10 wins.