#3186

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Maximum Total Damage With Spell Casting

Calculate the maximum total damage by selectively casting spells while avoiding adjacent power conflicts using array scanning and hash lookup.

array hash table two pointers binary search dynamic programming

Problem Statement

You are given an array power where each element represents the damage of a spell a magician can cast. Multiple spells can have the same damage value, and the magician wants to maximize total damage through careful selection.

The magician cannot cast any spell whose damage is within 2 of another chosen spell. That is, if a spell with power[i] is cast, spells with power[i]-2, power[i]-1, power[i]+1, and power[i]+2 cannot be used. Compute the maximum total damage achievable under these constraints.

Examples

Example 1

Input: power = [1,1,3,4]

Output: 6

The maximum possible damage of 6 is produced by casting spells 0, 1, 3 with damage 1, 1, 4.

Example 2

Input: power = [7,1,6,6]

Output: 13

The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.

Constraints

1 <= power.length <= 105
1 <= power[i] <= 109

Solution Approach

Map Power to Total Damage

Create a hash table to sum all occurrences of each unique power. This allows quick lookup of total damage contribution for any chosen power and sets up for dynamic programming decisions.

Dynamic Programming Over Sorted Powers

Sort the unique powers and iterate through them. For each power, calculate two options: include the total damage from this power plus the best damage from non-conflicting previous powers, or skip this power and carry forward the previous maximum. Select the higher of the two.

Final Damage Selection

After processing all powers, the maximum stored in the dynamic programming array represents the optimal total damage. Return this value as the answer, ensuring the adjacency rules are maintained throughout.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m log m), where n is the length of power and m is the number of unique powers, due to counting and sorting. Space complexity is O(m) for the hash table and dynamic programming array.

What Interviewers Usually Probe

They may emphasize using all spells of the same power when choosing to cast it.
Expect hints toward array scanning combined with hash lookup for efficiency.
Watch for discussions about handling large power values within the adjacency constraints.

Common Pitfalls or Variants

Common pitfalls

Failing to sum all duplicates of a power before dynamic programming.
Not properly skipping conflicting powers within the +-2 range.
Assuming sequential indices matter instead of actual power values.

Follow-up variants

Allowing conflicts within a range k instead of 2.
Casting each spell at most once instead of summing duplicates.
Maximizing damage under additional cooldown constraints between casts.

FAQ

What is the best way to handle duplicate spell powers in Maximum Total Damage With Spell Casting?

Sum all duplicates of each power first in a hash table to consider their total contribution before applying dynamic programming.

Why do we sort unique powers instead of the original array?

Sorting unique powers ensures adjacency checks are based on power values, not indices, enabling correct dynamic programming decisions.

Can this method handle very large power values efficiently?

Yes, using a hash table avoids iterating through unused power values and keeps computation limited to actual unique powers.

How does the +-2 conflict rule affect dynamic programming?

It defines which previous powers are safe to combine with the current power, guiding the choice between including or skipping each power.

Is array scanning plus hash lookup essential for this problem?

Yes, this pattern efficiently aggregates spell damage and enables conflict-aware selection for maximum total damage.

terminal

Solution

Solution 1: Binary Search + Memoization

We can first sort the array $\textit{power}$, use a hash table $\textit{cnt}$ to record the occurrence count of each damage value, and then iterate through the array $\textit{power}$. For each damage value $x$, we can determine the index of the next damage value that can be used when using a spell with damage value $x$, which is the index of the first damage value greater than $x + 2$. We can use binary search to find this index and record it in the array $\textit{nxt}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        @cache
        def dfs(i: int) -> int:
            if i >= n:
                return 0
            a = dfs(i + cnt[power[i]])
            b = power[i] * cnt[power[i]] + dfs(nxt[i])
            return max(a, b)

        n = len(power)
        cnt = Counter(power)
        power.sort()
        nxt = [bisect_right(power, x + 2, lo=i + 1) for i, x in enumerate(power)]
        return dfs(0)

Continue Practicing

#2856 minimum array length after pair removals #2830 maximize the profit as the salesman #1782 count pairs of nodes