Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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 <= 10^5
  • 1 <= power[i] <= 10^9

Solution

Method 1 – Dynamic Programming with Frequency Counting

Intuition

This problem is similar to the “House Robber” or “Delete and Earn” pattern, but with a wider forbidden range. For each unique damage value, if we cast spells of this damage, we must skip all spells with damage within 2 of it. We use dynamic programming to track the best total damage at each value.

Approach

  1. Count the frequency of each damage value in power.
  2. Sort the unique damage values.
  3. Use a DP array where dp[i] is the max damage using up to the ith unique value:
    • For each value, either:
      • Skip it: take dp[i-1].
      • Take it: add its total damage to dp[j], where j is the last index with value at least 3 less than current.
  4. Return the last value in the DP array.

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting and DP over unique values.
  • 🧺 Space complexity: O(n) — For frequency and DP arrays.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int maximumDamage(vector<int>& power) {
        map<int, int> freq;
        for (int x : power) freq[x]++;
        vector<int> vals;
        for (auto& [v, _] : freq) vals.push_back(v);
        int n = vals.size();
        vector<int> dp(n);
        for (int i = 0; i < n; ++i) {
            int dmg = vals[i] * freq[vals[i]];
            int j = i - 1;
            while (j >= 0 && vals[j] >= vals[i] - 2) --j;
            dp[i] = max((i ? dp[i-1] : 0), dmg + (j >= 0 ? dp[j] : 0));
        }
        return dp.back();
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func maximumDamage(power []int) int {
    freq := map[int]int{}
    for _, x := range power { freq[x]++ }
    vals := []int{}
    for v := range freq { vals = append(vals, v) }
    sort.Ints(vals)
    n := len(vals)
    dp := make([]int, n)
    for i, v := range vals {
        dmg := v * freq[v]
        j := i - 1
        for j >= 0 && vals[j] >= v-2 { j-- }
        skip := 0
        if i > 0 { skip = dp[i-1] }
        take := dmg
        if j >= 0 { take += dp[j] }
        dp[i] = max(skip, take)
    }
    return dp[n-1]
}
func max(a, b int) int { if a > b { return a } else { return b } }
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int maximumDamage(int[] power) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : power) freq.put(x, freq.getOrDefault(x, 0) + 1);
        List<Integer> vals = new ArrayList<>(freq.keySet());
        Collections.sort(vals);
        int n = vals.size();
        int[] dp = new int[n];
        for (int i = 0; i < n; ++i) {
            int dmg = vals.get(i) * freq.get(vals.get(i));
            int j = i - 1;
            while (j >= 0 && vals.get(j) >= vals.get(i) - 2) j--;
            dp[i] = Math.max(i > 0 ? dp[i-1] : 0, dmg + (j >= 0 ? dp[j] : 0));
        }
        return dp[n-1];
    }
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maximumDamage(power: IntArray): Int {
        val freq = mutableMapOf<Int, Int>()
        for (x in power) freq[x] = freq.getOrDefault(x, 0) + 1
        val vals = freq.keys.sorted()
        val n = vals.size
        val dp = IntArray(n)
        for (i in vals.indices) {
            val dmg = vals[i] * freq[vals[i]]!!
            var j = i - 1
            while (j >= 0 && vals[j] >= vals[i] - 2) j--
            dp[i] = maxOf(if (i > 0) dp[i-1] else 0, dmg + if (j >= 0) dp[j] else 0)
        }
        return dp.last()
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def maximum_damage(power: list[int]) -> int:
    from collections import Counter
    freq = Counter(power)
    vals = sorted(freq)
    n = len(vals)
    dp = [0] * n
    for i, v in enumerate(vals):
        dmg = v * freq[v]
        j = i - 1
        while j >= 0 and vals[j] >= v - 2:
            j -= 1
        skip = dp[i-1] if i > 0 else 0
        take = dmg + (dp[j] if j >= 0 else 0)
        dp[i] = max(skip, take)
    return dp[-1]
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn maximum_damage(power: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for &x in &power { *freq.entry(x).or_insert(0) += 1; }
        let mut vals: Vec<_> = freq.keys().cloned().collect();
        vals.sort();
        let n = vals.len();
        let mut dp = vec![0; n];
        for i in 0..n {
            let dmg = vals[i] * freq[&vals[i]];
            let mut j = i as i32 - 1;
            while j >= 0 && vals[j as usize] >= vals[i] - 2 { j -= 1; }
            let skip = if i > 0 { dp[i-1] } else { 0 };
            let take = dmg + if j >= 0 { dp[j as usize] } else { 0 };
            dp[i] = skip.max(take);
        }
        dp[n-1]
    }
}
TypeScript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    maximumDamage(power: number[]): number {
        const freq = new Map<number, number>();
        for (const x of power) freq.set(x, (freq.get(x) ?? 0) + 1);
        const vals = Array.from(freq.keys()).sort((a, b) => a - b);
        const n = vals.length;
        const dp = Array(n).fill(0);
        for (let i = 0; i < n; ++i) {
            const dmg = vals[i] * freq.get(vals[i])!;
            let j = i - 1;
            while (j >= 0 && vals[j] >= vals[i] - 2) --j;
            const skip = i > 0 ? dp[i-1] : 0;
            const take = dmg + (j >= 0 ? dp[j] : 0);
            dp[i] = Math.max(skip, take);
        }
        return dp[n-1];
    }
}