Maximum Total Damage With Spell Casting — Problem & Solution
Maximum Total Damage With Spell Casting solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Total Damage With Spell Casting is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Dynamic Programming, Sorting, Binary Search, Two Pointers, Counting
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A magician knows several spells; power[i] is the damage of the i-th spell. Several spells may share the same damage value.
If the magician casts a spell with damage power[i], they can no longer cast any spell with damage power[i] - 2, power[i] - 1, power[i] + 1 or power[i] + 2. Each spell can be cast at most once.
Return the maximum total damage the magician can deal.
Example 1
Input: power = [1,1,3,4]
Output: 6
Explanation: Cast both 1s and the 4: 1 + 1 + 4 = 6.
Example 2
Input: power = [7,1,6,6]
Output: 13
Explanation: Cast 1, 6 and 6: 13.
Example 3
Input: power = [5]
Output: 5
Constraints
1 <= power.length <= 10^51 <= power[i] <= 10^4 (reduced from 10^9 so the total fits a 32-bit integer)
Hints for Maximum Total Damage With Spell Casting
Hint 1
Spells with the same damage never block each other, so if you cast one with value
vyou should cast all of them: the value is worthv · count(v).Hint 2
Sort the distinct values. Choosing a value forbids its neighbours within distance 2 — a house-robber-style DP over sorted values.
Hint 3
dp[i] = max(dp[i - 1], value_i · count_i + dp[j]), wherejcounts the distinct values smaller thanvalue_i - 2— a pointer that only moves forward finds it.
How to solve Maximum Total Damage With Spell Casting
Group spells by damage. Within a group there is no conflict, so a group is all-or-nothing, worth v · count(v). Across groups the rule is: chosen values must differ by more than 2. On the sorted distinct values that is a house-robber DP with a variable look-back.
Approach
- Count each damage value and sort the distinct values
v_0 < v_1 < … < v_{m-1}. - Let
dp[i]be the best total using onlyv_0..v_{i-1};dp[0] = 0. - For each
i, advance a pointerjwhilev_j < v_i - 2, sojis the number of values compatible withv_i. Thendp[i + 1] = max(dp[i], dp[j] + v_i · count(v_i)). - Return
dp[m].
Why it works
The best set either skips v_i (giving dp[i]) or takes it, in which case it cannot contain v_i - 1 or v_i - 2 and every other smaller value is unaffected — exactly the first j values. Because the values are sorted, j never moves backwards.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Looking back exactly two positions is wrong — the values are not consecutive integers; use the pointer.
- Taking only one copy of a value wastes damage; copies never conflict.
- Totals can be large; use 64-bit accumulators where the language needs them.
Reference solution
Python
from typing import List
def maximumTotalDamage(power: List[int]) -> int:
cnt = {}
for p in power:
cnt[p] = cnt.get(p, 0) + 1
vals = sorted(cnt)
m = len(vals)
dp = [0] * (m + 1)
j = 0
for i in range(m):
while vals[j] < vals[i] - 2:
j += 1
dp[i + 1] = max(dp[i], dp[j] + vals[i] * cnt[vals[i]])
return dp[m]Java
public static int maximumTotalDamage(int[] power) {
int[] a = power.clone();
Arrays.sort(a);
int n = a.length, m = 0;
int[] vals = new int[n];
long[] tot = new long[n];
for (int i = 0; i < n; i++) {
if (m > 0 && vals[m - 1] == a[i]) tot[m - 1] += a[i];
else { vals[m] = a[i]; tot[m] = a[i]; m++; }
}
long[] dp = new long[m + 1];
int j = 0;
for (int i = 0; i < m; i++) {
while (vals[j] < vals[i] - 2) j++;
dp[i + 1] = Math.max(dp[i], dp[j] + tot[i]);
}
return (int) dp[m];
}C++
int maximumTotalDamage(vector<int>& power) {
vector<int> a = power;
sort(a.begin(), a.end());
vector<int> vals;
vector<long long> tot;
for (int x : a) {
if (!vals.empty() && vals.back() == x) tot.back() += x;
else { vals.push_back(x); tot.push_back(x); }
}
int m = vals.size();
vector<long long> dp(m + 1, 0);
int j = 0;
for (int i = 0; i < m; i++) {
while (vals[j] < vals[i] - 2) j++;
dp[i + 1] = max(dp[i], dp[j] + tot[i]);
}
return (int) dp[m];
}JavaScript
var maximumTotalDamage = function(power) {
var a = power.slice().sort(function(p, q) { return p - q; });
var vals = [], tot = [];
for (var i = 0; i < a.length; i++) {
if (vals.length > 0 && vals[vals.length - 1] === a[i]) tot[tot.length - 1] += a[i];
else { vals.push(a[i]); tot.push(a[i]); }
}
var m = vals.length;
var dp = new Array(m + 1).fill(0), j = 0;
for (var i = 0; i < m; i++) {
while (vals[j] < vals[i] - 2) j++;
dp[i + 1] = Math.max(dp[i], dp[j] + tot[i]);
}
return dp[m];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets