Maximum Total Damage With Spell Casting

Medium
1658.

Maximum Total Damage With Spell Casting

Maximum Total Damage With Spell Casting is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon interviews.

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^5
  • 1 <= power[i] <= 10^4 (reduced from 10^9 so the total fits a 32-bit integer)
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} power
 * @return {number}
 */
var maximumTotalDamage = function(power) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= power[i] <= 10^4 (reduced from 10^9 so the total fits a 32-bit integer)

Hints for Maximum Total Damage With Spell Casting

  1. Hint 1

    Spells with the same damage never block each other, so if you cast one with value v you should cast all of them: the value is worth v · count(v).

  2. Hint 2

    Sort the distinct values. Choosing a value forbids its neighbours within distance 2 — a house-robber-style DP over sorted values.

  3. Hint 3

    dp[i] = max(dp[i - 1], value_i · count_i + dp[j]), where j counts the distinct values smaller than value_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

  1. Count each damage value and sort the distinct values v_0 < v_1 < … < v_{m-1}.
  2. Let dp[i] be the best total using only v_0..v_{i-1}; dp[0] = 0.
  3. For each i, advance a pointer j while v_j < v_i - 2, so j is the number of values compatible with v_i. Then dp[i + 1] = max(dp[i], dp[j] + v_i · count(v_i)).
  4. 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