Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Stack Parsing

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Queue & Deque →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumstack-parsing

Asteroid Collision

Problem (restated)

Asteroids on a line: positive = right, negative = left, magnitude = size. Opposite neighbors collide; smaller explodes, equal both explode. Same direction never collide. Return survivors.

Intuition

Stack of surviving asteroids left-to-right. Only a left-moving rock can hit a right-moving top.

Approaches

Collision stack simulation

Tested only
Time O(n)Space O(n)

Idea. While new a < 0 and stack top > 0, resolve by size; push a if it survives.

Walkthrough. [5,10,-5] → [5,10]; [8,-8] → []; [10,2,-5] → [10].

Trade-offs. Each asteroid enters/leaves stack once → O(n).

Solution
export function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];
  for (const a of asteroids) {
    let alive = true;
    while (
      alive &&
      a < 0 &&
      stack.length > 0 &&
      stack[stack.length - 1]! > 0
    ) {
      const top = stack[stack.length - 1]!;
      if (top < -a) {
        stack.pop();
        continue;
      } else if (top === -a) {
        stack.pop();
      }
      alive = false;
    }
    if (alive) stack.push(a);
  }
  return stack;
}

export function asteroidCollision(asteroids: number[]): number[] {
  const stack: number[] = [];
  for (const a of asteroids) {
    let alive = true;
    while (
      alive &&
      a < 0 &&
      stack.length > 0 &&
      stack[stack.length - 1]! > 0
    ) {
      const top = stack[stack.length - 1]!;
      if (top < -a) {
        stack.pop();
        continue;
      } else if (top === -a) {
        stack.pop();
      }
      alive = false;
    }
    if (alive) stack.push(a);
  }
  return stack;
}

Template connection

Stack simulation of collisions / nested resolution.

Reflection