FastPrepFastPrep
Problem Brief

Asteroid Collision (IMC Sydney 🐚)

INTERNOA

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 ith asteroid and a second array direction of size n where direction[i] is the direction of the ithasteroid 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.

1Example 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].

    2Example 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].

    3Example 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

    Limits and guarantees your solution can rely on.

    A mysterious secrete for now 😔
    public int[] asteroidCollision(int[] size, int[] direction) {
    
    // write your code here
    // (p.s. I kinda remember there is a similar asteroid collision problem on LC,
    // it might be helpful to check it out ^~^)
}
    Input

    size

    [4, 5, 6, 7, 4]

    direction

    [1, 1, 1, 0, 1, 0]

    Output

    [6, 7]

    Sign in to submit your solution.