<AI/>
All posts

Asteroid Collision

LeetCode 735: Predict the outcome when asteroids of different sizes and directions collide in a row.

Difficulty
Medium
Published
Topics
#array#stack
Open on LeetCode

Problem Description

Write a function that calculates the outcome of asteroid collisions.

Input

An array of non-zero integers. Each number represents the mass of an asteroid, and its sign indicates the direction of movement.

Output

An array of non-zero integers. The array describes the set of asteroids, their mass and direction, after all asteroids that can collide have collided.

All asteroids move at the same speed. Therefore, asteroids moving in the same direction will never collide with each other.

Unlike real life, the mass and direction of an asteroid do not change after a collision. The smaller of the two is completely destroyed, and the larger one continues moving in the same direction without changing mass.

Constraints

  • The number of asteroids (length of the input array) is in the range from 2 to 10000
  • The mass of an asteroid is in the range from 1 to 1000 (the sign only affects the direction of movement)
  • Asteroids with zero mass do not exist

Examples

Input: [5,10,-5]

Answer: [5,10]

Explanation: The first two asteroids move to the right, the last one moves to the left. As a result, the second and third asteroids collide. The second asteroid has a greater mass, so it completely destroys the third.

Two Pointers approach

One possible solution is to use two pointers. We choose the first two asteroids as the initial points. We follow these rules:

  • If the left asteroid has a negative sign (i.e., it moves to the left), we move both pointers one position forward.
  • If both asteroids have a positive sign (i.e., both move to the right), we move both pointers one position forward, since they move in the same direction and will never collide.
  • If the left asteroid has a positive sign and the right one has a negative sign:
    • If the left asteroid is greater in absolute value than the right one, we remove the element at the right index. We do not shift the indices, since after removal the right index now points to the asteroid that was behind the removed element.
    • If the right asteroid is greater in absolute value, we remove the element at the left index and decrement both indices by one, since the right element shifted one position to the left, and the left one was removed.
    • If the asteroids are equal in absolute value, we remove both elements. We decrement both indices by one, since we need to move the left one back by one and the right one forward by one, but due to the shift by two elements to the left, the right index also needs to be decremented by two.
  • Don't forget to check edge cases: as a result of our operations, the indices may go outside the range [0, len(asteroids)].

Solution

typescript
export const asteroidCollisionTwoIdx = (asteroids: number[]): number[] => {
  let i = 0;
  let j = 1;
 
  while (i >= 0 && j < asteroids.length) {
    const first = asteroids[i];
    const second = asteroids[j];
 
    if (first * second > 0 || first < 0) {
      i++;
      j++;
      continue;
    }
 
    if (first > -1 * second) {
      asteroids = [...asteroids.slice(0, i + 1), ...asteroids.slice(j + 1)];
      continue;
    }
 
    if (first < -1 * second) {
      asteroids = [...asteroids.slice(0, i), ...asteroids.slice(j)];
      j--;
      i--;
 
      if (i < 0) {
        i = 0;
        j = 1;
      }
 
      continue;
    }
 
    if (first == -1 * second) {
      asteroids = [...asteroids.slice(0, i), ...asteroids.slice(j + 1)];
      j--;
      i--;
 
      if (i < 0) {
        i = 0;
        j = 1;
      }
    }
  }
 
  return asteroids;
};

Complexity Analysis

Time Complexity

The complexity is O(n²), where n is the length of the array.

Even though we used two pointers and did not run any inner loops, it is worth remembering that removing an element from the middle of an array is an O(n) operation (since the entire "tail" of the array needs to be shifted one element to the left).

Space Complexity

The complexity is O(1), since all modifications were done in-place, without allocating additional memory.

Stack approach

To solve the problem, we need to create a stack (which can be implemented using an array) and iterate through the elements of the input array:

  • If the stack is empty, push the element onto the stack.
  • If the stack is not empty, peek at the top element. If it has a negative sign (i.e., the asteroid moves to the left), keep it in the stack and also push the current element onto the stack.
  • If the stack is not empty, peek at the top element. If it is positive and the current element is negative, then:
    • If the current element has a smaller mass, keep the top element in the stack and move on to the next element.
    • If the elements have equal mass, move on to the next element without returning the top element to the stack.
    • If the current element has a greater mass, pop the next element from the stack without returning the top element, and repeat the checks with the new pair.
  • After we have fully iterated through all elements of the input array, the stack will contain the expected set of asteroids. If the stack is implemented using an array, the function can return it as the answer.

For simplicity, we implemented this approach using a recursive function appendAsteroidToStack, but it can be done without recursion as well.

Solution

typescript
export function asteroidCollision(asteroids: number[]): number[] {
  let stack: number[] = [];
 
  const appendAsteroidToStack = (asteroid: number): void => {
    if (stack.length == 0) {
      stack.push(asteroid);
      return;
    }
 
    const current = stack[stack.length - 1];
 
    if (current * asteroid > 0 || current < 0) {
      stack.push(asteroid);
      return;
    }
 
    if (current > -1 * asteroid) {
      return;
    }
 
    if (current < -1 * asteroid) {
      stack.pop();
      appendAsteroidToStack(asteroid);
      return;
    }
 
    stack.pop();
  };
 
  asteroids.forEach((asteroid) => {
    appendAsteroidToStack(asteroid);
  });
 
  return stack;
}

Complexity Analysis

Time Complexity

The complexity is O(n), where n is the length of the array.

In the worst case, we will have to push n-1 elements onto the stack and then pop all of them. That is, the maximum complexity is 2n, which in terms of algorithm analysis is equivalent to O(n).

Space Complexity

The complexity is O(n), since we had to create a stack to store the data.