Maximum Total Damage With Spell Casting - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem 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 1: Dynamic Programming Approach
This approach is inspired by the house robber problem where you cannot rob two consecutive houses for maximum profit.
Sort the array to ensure sequential consideration of spells and use a dynamic programming array to keep track of the maximum damage possible after considering each spell.
The state transition will involve checking if taking the current spell is beneficial over not taking it, given the constraint that certain nearby spells cannot be taken if the current one is taken.
The approach involves sorting the power array, then using a dynamic programming approach to decide whether to include the current spell damage or not. It relies on previous results and skips adjacent spells that violate constraints. The final result is stored in the 'current' variable.
Complexity
Time Complexity: O(n log n) due to sorting followed by O(n) dynamic programming iteration.
Space Complexity: O(1) since we only use a constant amount of extra space for variables.
Approach 2: Greedy Approach with Sorting
The greedy approach first sorts the spells to manage constraints easily.
Loop over sorted array to select spells ensuring the constraint condition by skipping spells adjacent to any selected spell's damage value.
Directly keep a set of selected spells to avoid overlapping selections.
Sort the array of spell damages, then iterate through selecting any spell that doesn't violate constraints determined by the previously included spell damage. The loop accumulates allowable spells' damage directly into the result.
Complexity
Time Complexity: O(n log n) due to sorting plus O(n) for the iteration.
Space Complexity: O(1) with constant variables used for computations.
Approach 3: Binary Search + Memoization
We can first sort the array power, use a hash table cnt to record the occurrence count of each damage value, and then iterate through the array 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 nxt.
Next, we define a function dfs to calculate the maximum damage value that can be obtained starting from the i-th damage value.
In the dfs function, we can choose to skip the current damage value, so we can skip all the same damage values of the current one and directly jump to i + cnt[x], obtaining a damage value of dfs(i + cnt[x]); or we can choose to use the current damage value, so we can use all the same damage values of the current one and then jump to the index of the next damage value, obtaining a damage value of x times cnt[x] + dfs(nxt[i]), where nxt[i] represents the index of the first damage value greater than x + 2. We take the maximum of these two cases as the return value of the function.
To avoid repeated calculations, we can use memoization, storing the results that have already been calculated in an array f. Thus, when calculating dfs(i), if f[i] is not 0, we directly return f[i].
The answer is dfs(0).
The time complexity is O(n log n), and the space complexity is O(n). Here, n is the length of the array power.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n log n) due to sorting followed by O(n) dynamic programming iteration. |
| Greedy Approach with Sorting | Time Complexity: O(n log n) due to sorting plus O(n) for the iteration. |
| Binary Search + Memoization | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Maximum Total Damage With Spell Casting | 2 Approaches | Detailed | Leetcode 3186 | codestorywithMIK • codestorywithMIK • 9,672 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Total Damage With Spell Casting easy or hard?
Maximum Total Damage With Spell Casting Python/Java solution
How to solve Maximum Total Damage With Spell Casting in O(n)?
What is the best approach for Maximum Total Damage With Spell Casting?
Is Maximum Total Damage With Spell Casting asked at Google/Amazon/Meta?
What data structure is used in Maximum Total Damage With Spell Casting?
What is the time complexity of Maximum Total Damage With Spell Casting?
Ready to solve this problem?
Practice Maximum Total Damage With Spell Casting with our built-in code editor and test cases.
Practice on FleetCode