Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Spells with equal damage do not conflict, and damage is positive, so selecting a value means taking all its occurrences. After grouping equal values, choosing a power excludes only distinct powers within distance two. Sorted values make the compatible earlier groups a growing prefix.

Approach

Count the frequency of each power and sort the distinct powers. Let dp[i] be the best total damage of a selection whose largest chosen power is unique[i]. Its own contribution is unique[i] * frequency[unique[i]].

Maintain a pointer through earlier powers and a running maximum of their DP values. Before computing dp[i], add every earlier power strictly less than unique[i] - 2 to that eligible prefix. Combine its best total, or zero if empty, with the current contribution.

Return the largest DP value. Every selection has a largest power, and removing that group leaves either nothing or an eligible earlier selection, so the recurrence covers all possibilities without examining every pair.

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        fm = defaultdict(int)

        for x in power:
            fm[x] += 1

        unique = sorted(list(fm.keys()))
        n = len(unique)
        dp = [0] * n
        mx = 0
        j = 0

        for i in range(n):
            while j < i and unique[j] < unique[i] - 2:
                mx = max(mx, dp[j])
                j += 1
            dp[i] = mx + unique[i] * fm[unique[i]]

        return max(dp)

Complexity analysis

Let n = power.length and u be the number of distinct powers. Time: O(n + u log u). Auxiliary space: O(u).