LeetCode #735: Asteroid Collision, Stack of Survivors

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: asteroids move in a line. Positive ones move right and negative ones move left. When two collide, the smaller one explodes, and if they are the same size, both explode. Return the asteroids that are left. Brute force: run the collisions pass by pass until nothing changes, which can take O(N²). The key insight: a collision only happens when a right-moving asteroid is followed by a left-moving one, which is exactly the shape a stack handles. For each left-moving asteroid, pop smaller right-movers off the top of the stack. If the top has the same size, both explode. If the top is bigger, the new asteroid explodes. Dry run: in 5, 10, -5, the 10 destroys the -5, so the answer is 5, 10. Complexity: O(N) time and O(N) space. Problem: https://leetcode.com/problems/asteroi... Related: Daily Temperatures (739), Valid Parentheses (20), Remove All Adjacent Duplicates in String II (1209) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode735 #asteroidcollision #stack #simulation #array #medium #coding #codinginterview #dsa #python #amazon #google #faang #brutetobest