FastPrep

Description

Solutions

Submission

Asteroid Collision (IMC Sydney 🐚)

🤘 INTERN

In this game, there are a number asteroids arranged in line. These asteroids can all move either left or right on the line and all asteroids move at the same speed. Each asteroid also has a size associated with it. If two asteroids that are next to each other move towards each other, they will collide. In this case, the larger asteroid will destroy the smaller one. If both asteroids have the same size, then both asteroids are destroyed. The purpose of this game is to determine which asteroids remain after all possible collisions occur.

Thus, given an array size of length n, where size[i] is the size of the i^th asteroid and a second array direction of size n where direction[i] is the direction of the i^thasteroid where 0 indicates moving left and 1 indicates moving right.

Given these inputs, find which asteroids remain after all collisions have taken place. Return an array containing the sizes of the remaining asteroids (in order). If no asteroids remain, then return an empty array.

Example 1:

Input:  size = [4, 5, 6, 7, 4], direction = [1, 1, 1, 0, 1, 0]
Output: [6, 7] 
Explanation:
A direction value if 1 indicates moving to the right and a direction value of 0 indicates moving to the left.

Collisions:
    
 size[1], size[2]: 5 < 6 so size[1] vanishes
 
 size[0], size[2]: 4 < 6 so size[0] vanishes and there are no more asteroids to the left of size[2]
 
 size[3], size[4]: 7 > 4 so size[4] vanishes and there are no more asteroids to the right of size[4]

Only size[2] and size[3] remain. Return them in the order they appear in size [6, 7].

Example 2:

Input:  size = [3, 4, 2, 1, 6, 4, 5], direction = [1, 0, 1, 0, 1, 1, 0]
Output: [4, 2, 6] 
Explanation:
The initial size array = [3, 4, 2, 1, 6, 4, 5] with direction = [1, 0, 1, 0, 1, 1, 0]

The collisions are between asteroids with sizes:

        (3, 4) 4 remains
        (2, 1) 2 remains
        (4, 5) 5 remains (no more collision to go)
        (6, 5) 6 remains

The remaining asteroids are [4, 2, 6].

Example 3:

Input:  size = [5, 5], direction = [1, 0]
Output: [] 
Explanation:
The initial size array = [5, -5] with direction = [1, 0]

The first and second asteroids collide. Since they are of the same size, both of them disappear 😭.

Constraints:

A mysterious secrete for now 😔