LeetCode Entry

735. Asteroid Collision

20.07.2023 medium 2023 kotlin

Result after asteroids collide left-right exploding by size: 15 5 -15 -5 5 -> -15 -5 5

735. Asteroid Collision medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/281

Problem TLDR

Result after asteroids collide left-right exploding by size: 15 5 -15 -5 5 -> -15 -5 5

Intuition

Let’s add positive asteroids to the Stack. When negative met, it can fly over all smaller positive added, and can explode if larger met.

Approach

Kotlin’s API helping reduce some LOC

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun asteroidCollision(asteroids: IntArray): IntArray = with(Stack<Int>()) {
        asteroids.forEach { sz ->
          if (!generateSequence { if (sz > 0 || isEmpty() || peek() < 0) null else peek() }
            .any {
              if (it <= -sz) pop()
              it >= -sz
            }) add(sz)
        }
        toIntArray()
    }