Destroying Asteroids - Practice Coding Problems

Destroying Asteroids - Problem

You are given an integer mass, which represents the original mass of a planet. You are further given an integer array asteroids, where asteroids[i] is the mass of the ith asteroid.

You can arrange for the planet to collide with the asteroids in any arbitrary order. If the mass of the planet is greater than or equal to the mass of the asteroid, the asteroid is destroyed and the planet gains the mass of the asteroid. Otherwise, the planet is destroyed.

Return true if all asteroids can be destroyed. Otherwise, return false.

Input & Output

Example 1 — Basic Success

$ Input: mass = 10, asteroids = [3,9,19,5,21]

› Output: true

💡 Note: Sort to [3,5,9,19,21]. Planet: 10→13→18→27→46→67. All asteroids destroyed successfully.

Example 2 — Impossible Case

$ Input: mass = 5, asteroids = [4,9,23,4]

› Output: false

💡 Note: Sort to [4,4,9,23]. Planet: 5→9→13→22. Cannot destroy asteroid 23 (mass 22 < 23).

Example 3 — Edge Case

$ Input: mass = 10, asteroids = []

› Output: true

💡 Note: No asteroids to destroy, so automatically return true.

Constraints

1 ≤ mass ≤ 10⁵
1 ≤ asteroids.length ≤ 10⁵
1 ≤ asteroids[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Planet with initial mass and array of asteroid masses

Strategy

Sort asteroids and attack smallest first to maximize growth

Result

Return whether all asteroids can be destroyed

Key Takeaway

🎯 Key Insight: Always attack the smallest asteroid you can handle to maximize mass growth and future opportunities

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we should always destroy the smallest asteroid we can handle first. This greedy approach maximizes our mass growth, giving us the best chance to handle larger asteroids later. Best approach is greedy sorting. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Try All Permutations	O(n! × n)	O(n)	Generate all possible orders and check if any works
Greedy - Sort Ascending	O(n log n)	O(1)	Always destroy the smallest asteroid first to grow mass efficiently

Try All Permutations — Algorithm Steps

Generate all permutations of asteroids
For each permutation, simulate collisions in that order
Return true if any permutation succeeds

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible orders of asteroids

Test Each Order

Simulate collision sequence for each permutation

Find Success

Return true if any order works

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool simulate(long long mass, int* asteroids, int n) {
    long long currentMass = mass;
    for (int i = 0; i < n; i++) {
        if (currentMass >= asteroids[i]) {
            currentMass += asteroids[i];
        } else {
            return false;
        }
    }
    return true;
}

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool nextPermutation(int* arr, int n) {
    int i = n - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i < 0) return false;
    
    int j = n - 1;
    while (arr[j] <= arr[i]) j--;
    swap(&arr[i], &arr[j]);
    
    int left = i + 1, right = n - 1;
    while (left < right) {
        swap(&arr[left], &arr[right]);
        left++;
        right--;
    }
    return true;
}

void quickSort(int* arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int partition(int* arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

bool solution(int mass, int* asteroids, int n) {
    if (n == 0) return true;
    
    quickSort(asteroids, 0, n - 1);
    
    do {
        if (simulate(mass, asteroids, n)) {
            return true;
        }
    } while (nextPermutation(asteroids, n));
    
    return false;
}

int main() {
    int mass;
    scanf("%d", &mass);
    
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int asteroids[1000];
    int n = 0;
    
    if (strlen(line) > 3) {
        char* token = strtok(line + 1, ",]");
        while (token != NULL) {
            asteroids[n++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    bool result = solution(mass, asteroids, n);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

n! permutations, each taking O(n) time to simulate

⚠ Quadratic Growth

Space Complexity

O(n)

Space for recursion stack and current permutation

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Try All Permutations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler