Watch 10 video solutions for Maximum Total Damage With Spell Casting, a medium level problem involving Array, Hash Table, Two Pointers. This walkthrough by codestorywithMIK has 9,335 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A magician has various spells.
You are given an array power, where each element represents the damage of a spell. Multiple spells can have the same damage value.
It is a known fact that if a magician decides to cast a spell with a damage of power[i], they cannot cast any spell with a damage of power[i] - 2, power[i] - 1, power[i] + 1, or power[i] + 2.
Each spell can be cast only once.
Return the maximum possible total damage that a magician can cast.
Example 1:
Input: power = [1,1,3,4]
Output: 6
Explanation:
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
Explanation:
The maximum possible damage of 13 is produced by casting spells 1, 2, 3 with damage 1, 6, 6.
Constraints:
1 <= power.length <= 1051 <= power[i] <= 109Problem Overview: You are given an array where each value represents the power of a spell. Casting spells with certain powers prevents casting spells with nearby powers. The goal is to select a subset of spells that maximizes total damage while respecting these constraints.
Approach 1: Dynamic Programming with Sorting and Counting (O(n log n) time, O(n) space)
The key observation is that multiple spells can share the same power, and choosing a power effectively contributes power * frequency damage. First count occurrences using a hash table, then sort the unique power values. This converts the problem into a weighted selection problem similar to House Robber. For each power x, compute the best damage either by skipping it or taking it and combining it with the last power whose value is less than x - 2. A binary search finds that previous compatible index efficiently. The DP relation becomes dp[i] = max(dp[i-1], damage[i] + dp[j]). This handles overlapping constraints cleanly and guarantees the optimal total damage.
Approach 2: Greedy + Sorting with Two Pointers (O(n log n) time, O(1) extra space)
Another perspective is to sort the spell powers and process them in increasing order. After grouping identical values, compute their total contribution. Maintain a pointer to track the latest power that does not violate the distance constraint. When evaluating the current group, decide whether including it increases the cumulative damage compared with skipping it. This technique behaves like a rolling dynamic decision while scanning the sorted list. The approach relies on ordered traversal and compatibility checks between powers, which is why sorting is required.
Recommended for interviews: The dynamic programming solution with counting and binary search is the most reliable approach. It clearly models the constraint between spell powers and scales well for large inputs. Interviewers typically expect candidates to recognize the similarity to weighted scheduling or the Delete-and-Earn pattern. Starting from a brute-force subset idea and then optimizing with DP demonstrates strong problem-solving progression.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Sorting + Binary Search | O(n log n) | O(n) | General case with many duplicate spell powers and large input sizes |
| Greedy Scan with Sorting | O(n log n) | O(1) | When memory usage should stay minimal and powers can be processed sequentially |