Maximum Total Damage With Spell Casting solution and explanation
Google
9 more videos on this problem
Maximum Total Damage With Spell Casting | 2 Approaches | Detailed | Leetcode 3186 | codestorywithMIKcodestorywithMIK · 40:41 · 9K views
3186. Maximum Total Damage With Spell Casting | DP + Binary Search | Same as LISAryan Mittal · 20:39 · 7K views
3186. Maximum Total Damage With Spell Casting (Leetcode Medium)Programming Live with Larry · 17:26 · 1K views
Daily Leetcode #2020: Oct 11, 2025 - 3186. Maximum Total Damage With Spell CastingProgramming Live with Larry · 12:25 · 898 views
3186. Maximum Total Damage With Spell Casting | Leetcode Daily - PythonLeetcode Daily · 7:24 · 815 views
Maximum Total Damage With Spell Casting | Leetcode 3186 | Hindi Explaination | Leetcode | DSACode with Deepak · 24:09 · 679 views
Maximum Total Damage With Spell Casting | LeetCode 3186 - Pythonimpoldev · 14:47 · 519 views
Leetcode 3186 | Maximum Total Damage With Spell Casting | Leetcode Weekly Contest 402Road To FAANG · 14:07 · 399 views
LeetCode Daily 3186 | Maximum Total Damage With Spell Casting | Medium | Solution WalkthroughDaily Dose Of LeetCode · 29:38 · 208 views
Maximum Total Damage With Spell Casting | LeetCode 3186 | Dynamic Programming | Google MetaCode Harmony · 17:28 · 167 views
The 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.
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.
def max_total_damage(power):
if len(power) == 1:
return power[0]
power.sort()
prev1 = prev2 = current = 0
for i in range(len(power)):
temp = current
include_current = power[i] + (prev2 if i > 1 else 0)
current = max(prev1, include_current)
prev2 = prev1
prev1 = temp
return current
power = [7, 1, 6, 6]
print(max_total_damage(power))import java.util.Arrays;
public class SpellCasting {
public static int maxTotalDamage(int[] power) {
if (power.length == 1) return power[0];
Arrays.sort(power);
int prev1 = 0, prev2 = 0, current = 0;
for (int i = 0; i < power.length; ++i) {
int temp = current;
int includeCurrent = power[i] + (i > 1 ? prev2 : 0);
current = Math.max(prev1, includeCurrent);
prev2 = prev1;
prev1 = temp;
}
return current;
}
public static void main(String[] args) {
int[] power = {7, 1, 6, 6};
System.out.println(maxTotalDamage(power));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int maxTotalDamage(std::vector<int>& power) {
if (power.size() == 1) return power[0];
std::sort(power.begin(), power.end());
int prev1 = 0, prev2 = 0, current = 0;
for (size_t i = 0; i < power.size(); ++i) {
int temp = current;
int includeCurrent = power[i] + (i > 1 ? prev2 : 0);
current = std::max(prev1, includeCurrent);
prev2 = prev1;
prev1 = temp;
}
return current;
}
int main() {
std::vector<int> power = {7, 1, 6, 6};
std::cout << maxTotalDamage(power) << std::endl;
return 0;
}function maxTotalDamage(power) {
if (power.length === 1) return power[0];
power.sort((a, b) => a - b);
let prev1 = 0, prev2 = 0, current = 0;
for (let i = 0; i < power.length; i++) {
let temp = current;
let includeCurrent = power[i] + (i > 1 ? prev2 : 0);
current = Math.max(prev1, includeCurrent);
prev2 = prev1;
prev1 = temp;
}
return current;
}
const power = [7, 1, 6, 6];
console.log(maxTotalDamage(power));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int maxTotalDamage(int* power, int powerSize) {
if (powerSize == 1) return power[0];
qsort(power, powerSize, sizeof(int), compare);
int prev1 = 0, prev2 = 0, current = 0;
for (int i = 0; i < powerSize; ++i) {
int temp = current;
int includeCurrent = power[i] + (i > 1 ? prev2 : 0);
current = (prev1 > includeCurrent) ? prev1 : includeCurrent;
prev2 = prev1;
prev1 = temp;
}
return current;
}
int main() {
int power[] = {7, 1, 6, 6};
int powerSize = sizeof(power) / sizeof(power[0]);
printf("%d\n", maxTotalDamage(power, powerSize));
return 0;
}using System;
public class SpellCasting {
public static int MaxTotalDamage(int[] power) {
if (power.Length == 1) return power[0];
Array.Sort(power);
int prev1 = 0, prev2 = 0, current = 0;
for (int i = 0; i < power.Length; i++) {
int temp = current;
int includeCurrent = power[i] + (i > 1 ? prev2 : 0);
current = Math.Max(prev1, includeCurrent);
prev2 = prev1;
prev1 = temp;
}
return current;
}
public static void Main() {
int[] power = {7, 1, 6, 6};
Console.WriteLine(MaxTotalDamage(power));
}
}This Python implementation involves sorting the power array and iterating through it. A temporary variable keeps track of potential inclusion, while the decision to include or exclude each element is made by comparing with previous results.
Time Complexity: O(n log n) due to sorting followed by O(n) in the loop.
Space Complexity: O(1) because only a few integer variables are used.
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.
def max_total_damage_greedy(power):
if len(power) == 1:
return power[0]
power.sort()
max_damage = 0
last_included = -5
for dmg in power:
if dmg > last_included + 2:
max_damage += dmg
last_included = dmg
return max_damage
power = [7, 1, 6, 6]
print(max_total_damage_greedy(power))import java.util.Arrays;
public class SpellCasting {
public static int maxTotalDamageGreedy(int[] power) {
if (power.length == 1) return power[0];
Arrays.sort(power);
int maxDamage = 0;
int lastIncluded = -5;
for (int i = 0; i < power.length; i++) {
if (power[i] > lastIncluded + 2) {
maxDamage += power[i];
lastIncluded = power[i];
}
}
return maxDamage;
}
public static void main(String[] args) {
int[] power = {7, 1, 6, 6};
System.out.println(maxTotalDamageGreedy(power));
}
}#include <vector>
#include <algorithm>
#include <iostream>
int maxTotalDamageGreedy(std::vector<int>& power) {
if (power.size() == 1) return power[0];
std::sort(power.begin(), power.end());
int maxDamage = 0;
int lastIncluded = -5;
for (size_t i = 0; i < power.size(); ++i) {
if (power[i] > lastIncluded + 2) {
maxDamage += power[i];
lastIncluded = power[i];
}
}
return maxDamage;
}
int main() {
std::vector<int> power = {7, 1, 6, 6};
std::cout << maxTotalDamageGreedy(power) << std::endl;
return 0;
}function maxTotalDamageGreedy(power) {
if (power.length === 1) return power[0];
power.sort((a, b) => a - b);
let maxDamage = 0;
let lastIncluded = -5;
for (let i = 0; i < power.length; i++) {
if (power[i] > lastIncluded + 2) {
maxDamage += power[i];
lastIncluded = power[i];
}
}
return maxDamage;
}
const power = [7, 1, 6, 6];
console.log(maxTotalDamageGreedy(power));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int maxTotalDamageGreedy(int* power, int powerSize) {
if (powerSize == 1) return power[0];
qsort(power, powerSize, sizeof(int), compare);
int maxDamage = 0;
int lastIncluded = -5;
for (int i = 0; i < powerSize; ++i) {
if (power[i] > lastIncluded + 2) {
maxDamage += power[i];
lastIncluded = power[i];
}
}
return maxDamage;
}
int main() {
int power[] = {7, 1, 6, 6};
int powerSize = sizeof(power) / sizeof(power[0]);
printf("%d\n", maxTotalDamageGreedy(power, powerSize));
return 0;
}using System;
public class SpellCasting {
public static int MaxTotalDamageGreedy(int[] power) {
if (power.Length == 1) return power[0];
Array.Sort(power);
int maxDamage = 0;
int lastIncluded = -5;
for (int i = 0; i < power.Length; i++) {
if (power[i] > lastIncluded + 2) {
maxDamage += power[i];
lastIncluded = power[i];
}
}
return maxDamage;
}
public static void Main() {
int[] power = {7, 1, 6, 6};
Console.WriteLine(MaxTotalDamageGreedy(power));
}
}This Python solution sorts the power list and accumulates maximum damage by choosing each non-consecutive spell invocantly compared to the last taken one.
Time Complexity: O(n log n) for initial sort followed by O(n) for the greedy selection.
Space Complexity: O(1) for only a few additional variables.
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.
function maximumTotalDamage(power: number[]): number {
const n = power.length;
power.sort((a, b) => a - b);
const f: number[] = Array(n).fill(0);
const cnt: Record<number, number> = {};
const nxt: number[] = Array(n).fill(0);
for (let i = 0; i < n; ++i) {
cnt[power[i]] = (cnt[power[i]] || 0) + 1;
let [l, r] = [i + 1, n];
while (l < r) {
const mid = (l + r) >> 1;
if (power[mid] > power[i] + 2) {
r = mid;
} else {
l = mid + 1;
}
}
nxt[i] = l;
}
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i]) {
return f[i];
}
const a = dfs(i + cnt[power[i]]);
const b = power[i] * cnt[power[i]] + dfs(nxt[i]);
return (f[i] = Math.max(a, b));
};
return dfs(0);
}func maximumTotalDamage(power []int) int64 {
n := len(power)
sort.Ints(power)
cnt := map[int]int{}
nxt := make([]int, n)
f := make([]int64, n)
for i, x := range power {
cnt[x]++
nxt[i] = sort.SearchInts(power, x+3)
}
var dfs func(int) int64
dfs = func(i int) int64 {
if i >= n {
return 0
}
if f[i] != 0 {
return f[i]
}
a := dfs(i + cnt[power[i]])
b := int64(power[i]*cnt[power[i]]) + dfs(nxt[i])
f[i] = max(a, b)
return f[i]
}
return dfs(0)
}use std::collections::HashMap;
impl Solution {
pub fn maximum_total_damage(mut power: Vec<i32>) -> i64 {
power.sort();
let n = power.len();
let mut cnt = HashMap::new();
let mut nxt = vec![0; n];
let mut f = vec![-1_i64; n];
for i in 0..n {
*cnt.entry(power[i]).or_insert(0) += 1;
let j = match power[i + 1..].binary_search_by(|&x| x.cmp(&(power[i] + 2 + 1))) {
Ok(pos) | Err(pos) => i + 1 + pos,
};
nxt[i] = j;
}
fn dfs(
i: usize,
n: usize,
power: &Vec<i32>,
nxt: &Vec<usize>,
f: &mut Vec<i64>,
cnt: &HashMap<i32, i32>,
) -> i64 {
if i >= n {
return 0;
}
if f[i] != -1 {
return f[i];
}
let c = *cnt.get(&power[i]).unwrap();
let a = dfs(i + c as usize, n, power, nxt, f, cnt);
let b = power[i] as i64 * c as i64 + dfs(nxt[i], n, power, nxt, f, cnt);
f[i] = a.max(b);
f[i]
}
dfs(0, n, &power, &nxt, &mut f, &cnt)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n log n) due to sorting followed by O(n) in the loop. |
| Greedy Approach with Sorting | Time Complexity: O(n log n) for initial sort followed by O(n) for the greedy selection. |
| Binary Search + Memoization | – |
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 |
Frequently asked questions
Is Maximum Total Damage With Spell Casting easy or hard?
Maximum Total Damage With Spell Casting is generally classified as a Medium difficulty problem. The challenge comes from recognizing that selecting a spell blocks nearby power values and transforming the problem into a dynamic programming pattern similar to House Robber or Delete and Earn.
Maximum Total Damage With Spell Casting Python/Java solution
Python and Java solutions typically follow the same structure: count frequencies with a dictionary or map, sort the unique powers, compute the total damage for each power, and apply dynamic programming with binary search to combine compatible values. Both languages achieve O(n log n) time complexity.
How to solve Maximum Total Damage With Spell Casting in O(n)?
A near-linear solution is possible after preprocessing if spell powers are already sorted or compressed into a small range. By grouping identical values and scanning them with a rolling DP (similar to House Robber), each value is processed once. Without pre-sorted input, sorting typically makes the practical complexity O(n log n).
What is the best approach for Maximum Total Damage With Spell Casting?
The most reliable approach uses dynamic programming with counting and sorting. First group identical spell powers and compute their total contribution. Then process the sorted unique powers with a DP transition that either skips the current power or combines it with the last compatible power (difference greater than 2). This runs in O(n log n) time due to sorting and binary search.
Is Maximum Total Damage With Spell Casting asked at Google/Amazon/Meta?
Problems based on weighted selection and dynamic programming patterns appear frequently in interviews at companies like Amazon, Google, and Meta. This problem closely resembles the classic Delete and Earn or weighted interval scheduling pattern, which interviewers often use to test DP reasoning.
What data structure is used in Maximum Total Damage With Spell Casting?
Common implementations use a hash table to count spell power frequencies, an array or list to store sorted unique powers, and a DP array for optimal damage values. Binary search or two pointers help locate the last compatible power when enforcing the distance constraint.
What is the time complexity of Maximum Total Damage With Spell Casting?
The optimal solution runs in O(n log n) time and O(n) space. Sorting the unique spell powers dominates the runtime, while dynamic programming processes each value once. If the values are already sorted or constrained to a small range, the complexity can approach linear time.