735. Asteroid Collision #

Problem #

We are given an array asteroids of integers 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.

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.

Example 1:

Input: 
asteroids = [5, 10, -5]
Output: [5, 10]
Explanation: 
The 10 and -5 collide resulting in 10.  The 5 and 10 never collide.

Example 2:

Input: 
asteroids = [8, -8]
Output: []
Explanation: 
The 8 and -8 collide exploding each other.

Example 3:

Input: 
asteroids = [10, 2, -5]
Output: [10]
Explanation: 
The 2 and -5 collide resulting in -5.  The 10 and -5 collide resulting in 10.

Example 4:

Input: 
asteroids = [-2, -1, 1, 2]
Output: [-2, -1, 1, 2]
Explanation: 
The -2 and -1 are moving left, while the 1 and 2 are moving right.
Asteroids moving the same direction never meet, so no asteroids will meet each other.

Note:

• The length of asteroids will be at most 10000.
• Each asteroid will be a non-zero integer in the range [-1000, 1000]..

Problem Summary #

Given an integer array asteroids, representing asteroids in the same row. For each element in the array, its absolute value represents the size of the asteroid, and its sign represents the direction the asteroid moves (positive means moving right, negative means moving left). Each asteroid moves at the same speed. Find all asteroids remaining after collisions. Collision rules: when two asteroids collide with each other, the smaller asteroid will explode. If the two asteroids are the same size, both asteroids will explode. Two asteroids moving in the same direction will never collide.

Solution Approach #

This problem is similar to problem 1047. It is also a similar “matching elimination” game, but for collisions here, after a large asteroid collides with a small asteroid, the large asteroid wins and the small asteroid disappears directly. Simulate it with a stack according to the rules in the problem statement. Consider the final result:

1. All asteroids flying left go left, and all asteroids flying right go right.
2. For an asteroid flying left, if there is no asteroid flying right during its flight, then it will pass through safely.
3. Track all asteroids moving right on the right side; the rightmost one will be the first to face a collision with an asteroid flying left.
4. If it survives, continue moving forward; otherwise, any previous right-moving asteroids will be exposed one by one to collide.

So handle this case first: use an inner loop to finish all possible collisions with right-flying asteroids. After collisions are finished, if the asteroid at the top of the stack is flying left and the incoming asteroid is flying right, append it directly. Otherwise, if the asteroid at the top of the stack is flying right and has the same size as the asteroid flying left, both are destroyed, so pop the top element from the stack.

Code #

package leetcode

func asteroidCollision(asteroids []int) []int {
	res := []int{}
	for _, v := range asteroids {
		for len(res) != 0 && res[len(res)-1] > 0 && res[len(res)-1] < -v {
			res = res[:len(res)-1]
		}
		if len(res) == 0 || v > 0 || res[len(res)-1] < 0 {
			res = append(res, v)
		} else if v < 0 && res[len(res)-1] == -v {
			res = res[:len(res)-1]
		}
	}
	return res
}