Introduction

In this blog post, we will explore how to solve the LeetCode problem "2126" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. Example 1: Input: mass = 10, asteroids = [3,9,19,5,21] Output: true Explanation: One way to order the asteroids is [9,19,5,3,21]: - The planet collides with the asteroid with a mass of 9. New planet mass: 10 + 9 = 19 - The planet collides with the asteroid with a mass of 19. New planet mass: 19 + 19 = 38 - The planet collides with the asteroid with a mass of 5. New planet mass: 38 + 5 = 43 - The planet collides with the asteroid with a mass of 3. New planet mass: 43 + 3 = 46 - The planet collides with the asteroid with a mass of 21. New planet mass: 46 + 21 = 67 All asteroids are destroyed. Example 2: Input: mass = 5, asteroids = [4,9,23,4] Output: false Explanation: The planet cannot ever gain enough mass to destroy the asteroid with a mass of 23. After the planet destroys the other asteroids, it will have a mass of 5 + 4 + 9 + 4 = 22. This is less than 23, so a collision would not destroy the last asteroid. Constraints: 1 <= mass <= 105 1 <= asteroids.length <= 105 1 <= asteroids[i] <= 105

Explanation

Here's the solution to the problem:

• Sorting for Optimality: The key idea is to sort the asteroids in ascending order. This allows the planet to destroy smaller asteroids first, accumulating mass gradually to handle larger asteroids later.

• Greedy Approach: Iterate through the sorted asteroids. If the planet's mass is greater than or equal to the asteroid's mass, destroy the asteroid and increase the planet's mass. Otherwise, the planet cannot destroy all asteroids, so return false.

• Runtime Complexity: O(n log n), due to sorting the asteroids. Storage Complexity: O(1), excluding the input array (or O(n) if sorting creates a copy).

Code

    def can_destroy_all_asteroids(mass: int, asteroids: list[int]) -> bool:
    """
    Determines if a planet can destroy all asteroids in a given order.

    Args:
        mass: The initial mass of the planet.
        asteroids: A list of integers representing the mass of each asteroid.

    Returns:
        True if the planet can destroy all asteroids, False otherwise.
    """

    asteroids.sort()  # Sort asteroids in ascending order

    for asteroid_mass in asteroids:
        if mass >= asteroid_mass:
            mass += asteroid_mass  # Destroy the asteroid and gain mass
        else:
            return False  # Planet destroyed

    return True  # All asteroids destroyed