Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each maximal run of equal-colored balloons can keep at most one balloon. Keeping the one with the greatest removal cost minimizes the cost of deleting the rest. Keeping one from every original run preserves the differing colors between neighboring runs, so these choices combine safely.

Approach

Scan one same-color run at a time. Accumulate its total removal time and its maximum individual removal time, then add total - maximum to the answer. Advance directly to the next run and return the total after the scan. A one-balloon run contributes zero, and ties for the most expensive balloon can be resolved arbitrarily.

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        n = len(colors)
        res = 0
        i = 0

        while i < n:
            j = i
            total = 0
            mx = 0
            while j < n and colors[i] == colors[j]:
                total += neededTime[j]
                mx = max(mx, neededTime[j])
                j += 1
            res += total - mx
            i = j

        return res

Complexity analysis

The two indices partition n balloons into disjoint same-color runs, and every balloon is processed once. Time is O(n) and auxiliary space is O(1).