Destroying Asteroids - Video Solutions

Problem Overview: You start with a planet of mass mass and a list of asteroid masses. If your planet's mass is greater than or equal to an asteroid, you destroy it and your mass increases by that asteroid’s mass. If you encounter an asteroid larger than your current mass, the process stops. The goal is to determine whether you can destroy every asteroid.

Approach 1: Sorting and Sequential Processing (Greedy) (Time: O(n log n), Space: O(1) or O(n) depending on sort)

This approach relies on a greedy observation: always destroy the smallest asteroid first so your mass grows as quickly as possible. Start by sorting the asteroid array in ascending order using a standard sorting algorithm. Then iterate through the sorted list and check whether the current asteroid mass is less than or equal to your planet’s mass. If it is, add the asteroid’s mass to your total and continue; otherwise return false immediately. Sorting ensures you never face a large asteroid before accumulating enough mass, which makes the greedy choice optimal. The runtime is dominated by sorting at O(n log n), while the scan itself is O(n). This approach works well because the problem reduces to processing values in increasing order using simple arithmetic on an array.

Approach 2: Priority Queue for Dynamic Ordering (Time: O(n log n), Space: O(n))

Instead of sorting the array up front, you can push all asteroid masses into a min-heap (priority queue). Each step extracts the smallest asteroid currently available. If your mass is large enough, absorb it and increase your mass; otherwise stop and return false. The heap always gives the smallest remaining asteroid, which preserves the same greedy property as the sorting solution. Each insertion and extraction costs O(log n), so processing all asteroids results in O(n log n) time with O(n) additional memory. This method is useful when values may be streamed or dynamically inserted, since the heap maintains order without a full re-sort. It demonstrates how greedy strategies can be combined with a priority queue for incremental ordering.

Recommended for interviews: The sorting-based greedy approach is what interviewers typically expect. It shows you recognize the key insight: destroying smaller asteroids first maximizes growth and avoids early failure. Implementing the sorted iteration is straightforward and communicates strong problem-solving instincts. The priority queue variation is a good follow-up discussion that shows you understand alternative data structures and dynamic ordering tradeoffs.