# Maximum Total Damage With Spell Casting
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-total-damage-with-spell-casting)
Canonical: https://scaleengineer.com/dsa/problems/maximum-total-damage-with-spell-casting
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## 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 <= 105`
* `1 <= power[i] <= 109`

# Approaches
## Brute-Force Recursion
This approach explores all possible valid combinations of spells by making a decision for each unique spell power: either cast it or skip it. It uses a recursive function to traverse the decision tree. While simple to understand, its exponential nature makes it impractical for the given constraints.
**Time:** O(N + 2^M), where N is the length of the `power` array and M is the number of unique powers. O(N) is for preprocessing. The recursive part can have up to 2^M calls in the worst case, making it exponential. · **Space:** O(M), where M is the number of unique powers. This is for storing the unique powers and for the recursion stack depth.
**Pros:** Conceptually simple and a direct translation of the problem statement.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for moderately large inputs.
### Explanation
The core idea is to simplify the problem first. Since the constraint depends on the damage value, not the spell's index, we can group spells by their power. If we decide to cast a spell with power `p`, it's always optimal to cast all spells with power `p` to maximize damage without adding new restrictions. 

1.  **Preprocessing:** We first count the frequencies of each power value using a HashMap. Then, we extract the unique power values and sort them. This gives us a sorted array of unique powers, say `uniquePowers`.

2.  **Recursion:** We define a recursive function `solve(index)` that calculates the maximum damage possible from the spells in `uniquePowers` from `index` to the end. At each `index`, we face a choice:
    *   **Skip `uniquePowers[index]`:** We move to the next unique power, so the damage is `solve(index + 1)`.
    *   **Cast `uniquePowers[index]`:** We gain `uniquePowers[index] * count` damage. Due to the constraint, we cannot cast spells with power `p+1` or `p+2`. We must find the next available spell, which is the first one with power greater than `uniquePowers[index] + 2`. Let its index be `nextIndex`. We then add the result of `solve(nextIndex)`.

The function returns the maximum of these two outcomes. This method explores the entire search space, leading to a correct but very slow solution.

```java
import java.util.*;

class Solution {
    private Map<Integer, Integer> counts;
    private int[] uniquePowers;

    public long maximumTotalDamage(int[] power) {
        counts = new HashMap<>();
        for (int p : power) {
            counts.put(p, counts.getOrDefault(p, 0) + 1);
        }

        uniquePowers = new int[counts.size()];
        int i = 0;
        for (int p : counts.keySet()) {
            uniquePowers[i++] = p;
        }
        Arrays.sort(uniquePowers);

        return solve(0);
    }

    private long solve(int index) {
        if (index >= uniquePowers.length) {
            return 0;
        }

        // Option 1: Skip current power
        long damageSkip = solve(index + 1);

        // Option 2: Take current power
        long currentPower = uniquePowers[index];
        long currentDamage = currentPower * counts.get((int)currentPower);

        // Find the next index to jump to
        int nextIndex = index + 1;
        while (nextIndex < uniquePowers.length && uniquePowers[nextIndex] <= currentPower + 2) {
            nextIndex++;
        }
        long damageTake = currentDamage + solve(nextIndex);

        return Math.max(damageSkip, damageTake);
    }
}
```
### Algorithm
- Create a frequency map of the `power` array to count occurrences of each spell damage.
- Extract the unique damage values into a list and sort them in ascending order. Let this be `uniquePowers`.
- Define a recursive function, `solve(index)`, which computes the maximum damage from `uniquePowers` starting from `index`.
- **Base Case:** If `index` is out of bounds (`>= uniquePowers.length`), return 0.
- **Recursive Step:** For the spell at `uniquePowers[index]`, there are two choices:
    1. **Skip:** Don't cast this spell. The damage is `solve(index + 1)`.
    2. **Cast:** Cast this spell. The damage is `(uniquePowers[index] * frequency)`. We then find the next non-conflicting spell. This is the first spell `uniquePowers[nextIndex]` such that `uniquePowers[nextIndex] > uniquePowers[index] + 2`. The total damage for this choice is `(current spell's damage) + solve(nextIndex)`.
- The function returns the maximum of the 'Skip' and 'Cast' options.
- The initial call is `solve(0)`.

## Top-Down Dynamic Programming (Memoization)
This approach optimizes the brute-force recursion by using memoization, a top-down dynamic programming technique. It recognizes that the recursive solution computes the same subproblems multiple times. By storing the results of these subproblems in a cache (e.g., an array or map), we can avoid redundant calculations, drastically improving performance.
**Time:** O(N + M log M). O(N) for frequency counting, O(M log M) for sorting. Each of the M DP states is computed once, and each computation involves a binary search taking O(log M), leading to O(M log M) for the DP part. · **Space:** O(M), for the frequency map, unique powers array, memoization table, and the recursion stack.
**Pros:** Efficient enough to pass the given constraints.; The recursive structure is often intuitive and closely follows the problem's logic.
**Cons:** Slight overhead due to recursion function calls.; Can lead to a StackOverflowError if the number of unique powers is very large (though unlikely with given constraints).
### Explanation
The problem exhibits optimal substructure and overlapping subproblems, making it a perfect candidate for dynamic programming. The recursive brute-force approach is inefficient because it re-calculates `solve(k)` for the same `k` multiple times through different recursive paths.

We can eliminate this redundant work by storing the result of `solve(index)` the first time it's computed. A `memo` array (or a HashMap) can be used for this. `memo[index]` will store the result of `solve(index)`.

The logic is as follows:
1.  Inside `solve(index)`, first check if `memo[index]` contains a valid result. If yes, return it.
2.  If not, proceed with the regular recursive calculation: find the max damage by either skipping or casting the spell at `uniquePowers[index]`.
3.  To make the 'Cast' option efficient, we need to quickly find the next non-conflicting spell. Instead of a linear scan, we can use binary search on the sorted `uniquePowers` array to find the first power greater than `currentPower + 2`. This reduces the time for this step from O(M) to O(log M).
4.  Once the result is computed, store it in `memo[index]` before returning.

This ensures that each subproblem `solve(index)` is computed only once.

```java
import java.util.*;

class Solution {
    private Map<Integer, Integer> counts;
    private int[] uniquePowers;
    private long[] memo;

    public long maximumTotalDamage(int[] power) {
        counts = new HashMap<>();
        for (int p : power) {
            counts.put(p, counts.getOrDefault(p, 0) + 1);
        }

        uniquePowers = new int[counts.size()];
        int i = 0;
        for (int p : counts.keySet()) {
            uniquePowers[i++] = p;
        }
        Arrays.sort(uniquePowers);
        
        memo = new long[uniquePowers.length];
        Arrays.fill(memo, -1);
        return solve(0);
    }

    private long solve(int index) {
        if (index >= uniquePowers.length) {
            return 0;
        }
        if (memo[index] != -1) {
            return memo[index];
        }

        // Option 1: Skip current power
        long damageSkip = solve(index + 1);

        // Option 2: Take current power
        long currentPower = uniquePowers[index];
        long currentDamage = currentPower * counts.get((int)currentPower);

        // Find the next non-conflicting index using binary search
        int low = index + 1, high = uniquePowers.length - 1;
        int nextIndex = uniquePowers.length;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (uniquePowers[mid] > currentPower + 2) {
                nextIndex = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        long damageTake = currentDamage + solve(nextIndex);

        memo[index] = Math.max(damageSkip, damageTake);
        return memo[index];
    }
}
```
### Algorithm
- Preprocess the `power` array to get a frequency map and a sorted array of `uniquePowers`.
- Create a memoization table, `memo`, of the same size as `uniquePowers`, initialized to a sentinel value (e.g., -1).
- Use the same recursive function `solve(index)` as in the brute-force approach.
- Before any computation in `solve(index)`, check if `memo[index]` already has a computed value. If so, return it immediately.
- If not, compute the result for the 'Skip' and 'Cast' options.
- To find the `nextIndex` for the 'Cast' option efficiently, use binary search on the `uniquePowers` array. This finds the next non-conflicting spell in O(log M) time.
- Store the computed result in `memo[index]` before returning it.

## Bottom-Up Dynamic Programming
This approach uses bottom-up dynamic programming, an iterative method that builds the solution from the smallest subproblems. It avoids recursion, which can offer a slight performance benefit and prevents stack overflow issues. The logic is similar to the House Robber problem on a non-uniform set of values.
**Time:** O(N + M log M). O(N) for frequency counting, O(M log M) for sorting. The DP calculation with the two-pointer optimization takes O(M) time. The sorting step dominates the complexity. · **Space:** O(M), for the frequency map, unique powers array, and the DP table. This can be optimized to O(1) extra space (besides storing unique powers) since `dp[i]` only depends on `dp[i-1]` and `dp[j]`, but it complicates the code.
**Pros:** Most efficient approach in practice due to iterative nature (no recursion overhead).; Avoids potential stack overflow errors.
**Cons:** Can be slightly less intuitive to formulate than the recursive top-down approach.; Requires careful handling of indices and base cases.
### Explanation
An iterative DP approach is often preferred for its performance and avoidance of recursion limits. We build a `dp` array where `dp[i]` represents the maximum total damage achievable by considering the first `i+1` unique spell powers (i.e., from `uniquePowers[0]` to `uniquePowers[i]`).

1.  **Preprocessing:** As before, we get the sorted `uniquePowers` array and their frequencies.

2.  **DP State:** `dp[i]` = Maximum damage using a subset of `{uniquePowers[0], ..., uniquePowers[i]}`.

3.  **DP Transition:** We iterate `i` from `0` to `M-1` and compute `dp[i]`:
    *   **Choice 1 (Skip `uniquePowers[i]`):** If we don't cast this spell, the maximum damage is whatever we could achieve with the previous spells. This is simply `dp[i-1]` (if `i > 0`).
    *   **Choice 2 (Cast `uniquePowers[i]`):** We gain `uniquePowers[i] * count` damage. We must add the maximum damage from spells that don't conflict. We need to find the maximum damage from the subproblem ending just before the conflicting range, i.e., from spells with power `< uniquePowers[i] - 2`. This corresponds to `dp[j]` where `uniquePowers[j]` is the largest power satisfying this condition.

    The recurrence is `dp[i] = max(damage_if_skip, damage_if_cast)`. Finding the index `j` for each `i` can be done with a binary search (`O(M log M)`) or, even better, a two-pointer technique (`O(M)`), as the required `j` is non-decreasing as `i` increases.

```java
import java.util.*;

class Solution {
    public long maximumTotalDamage(int[] power) {
        if (power == null || power.length == 0) {
            return 0;
        }

        Map<Integer, Integer> counts = new HashMap<>();
        for (int p : power) {
            counts.put(p, counts.getOrDefault(p, 0) + 1);
        }

        int[] uniquePowers = new int[counts.size()];
        int i = 0;
        for (int p : counts.keySet()) {
            uniquePowers[i++] = p;
        }
        Arrays.sort(uniquePowers);

        int m = uniquePowers.length;
        long[] dp = new long[m];
        
        int j = 0; // Two-pointer for finding previous non-conflicting state
        for (i = 0; i < m; i++) {
            long currentPower = uniquePowers[i];
            long currentTotalDamage = currentPower * counts.get((int)currentPower);

            // Move pointer j forward. It will point to the first power that is >= currentPower - 2.
            while (uniquePowers[j] < currentPower - 2) {
                j++;
            }
            
            // The last valid subproblem result is at dp[j-1]
            long prevDamage = (j > 0) ? dp[j - 1] : 0;
            long damageTake = currentTotalDamage + prevDamage;

            // Option to skip the current power
            long damageSkip = (i > 0) ? dp[i - 1] : 0;

            dp[i] = Math.max(damageTake, damageSkip);
        }

        return m > 0 ? dp[m - 1] : 0;
    }
}
```
### Algorithm
- Perform the same preprocessing: create a frequency map and a sorted array `uniquePowers` of size `M`.
- Create a DP array, `dp`, of size `M`. `dp[i]` will store the maximum damage considering spells up to `uniquePowers[i]`.
- Iterate from `i = 0` to `M-1` to fill the `dp` array.
- For each `i`, calculate the max damage by considering two choices for `uniquePowers[i]`:
    1. **Skip:** The max damage is the result from the previous state, `dp[i-1]` (or 0 if `i=0`).
    2. **Cast:** The damage is `(uniquePowers[i] * frequency)`. To this, we add the max damage from non-conflicting previous spells. This requires finding the result for the largest power `uniquePowers[j]` such that `uniquePowers[j] < uniquePowers[i] - 2`. This corresponds to `dp[j]`.
- The value `dp[i]` is the maximum of these two choices.
- The index `j` can be found efficiently using a two-pointer approach. Maintain a pointer `j` that tracks the last non-conflicting state. As `i` increases, `j` only moves forward, leading to an O(M) DP calculation.
- The final answer is `dp[M-1]`.

# Solutions
### Java

```java
class Solution {
private
  Long[] f;
private
  int[] power;
private
  Map<Integer, Integer> cnt;
private
  int[] nxt;
private
  int n;
public
  long maximumTotalDamage(int[] power) {
    Arrays.sort(power);
    this.power = power;
    n = power.length;
    f = new Long[n];
    cnt = new HashMap<>(n);
    nxt = new int[n];
    for (int i = 0; i < n; ++i) {
      cnt.merge(power[i], 1, Integer : : sum);
      int l = Arrays.binarySearch(power, power[i] + 3);
      l = l < 0 ? -l - 1 : l;
      nxt[i] = l;
    }
    return dfs(0);
  }
private
  long dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    long a = dfs(i + cnt.get(power[i]));
    long b = 1L * power[i] * cnt.get(power[i]) + dfs(nxt[i]);
    return f[i] = Math.max(a, b);
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumTotalDamage(vector<int> &power) {
    sort(power.begin(), power.end());
    this->power = power;
    n = power.size();
    f.resize(n);
    nxt.resize(n);
    for (int i = 0; i < n; ++i) {
      cnt[power[i]]++;
      nxt[i] = upper_bound(power.begin() + i + 1, power.end(), power[i] + 2) -
               power.begin();
    }
    return dfs(0);
  }

private:
  unordered_map<int, int> cnt;
  vector<long long> f;
  vector<int> power;
  vector<int> nxt;
  int n;
  long long dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i]) {
      return f[i];
    }
    long long a = dfs(i + cnt[power[i]]);
    long long b = 1LL * power[i] * cnt[power[i]] + dfs(nxt[i]);
    return f[i] = max(a, b);
  }
};

```

### Python

```python
class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int: @ cache def dfs(i: int) -> int: if i >= n: return 0 a = dfs(i + cnt[power[i]]) b = power[i] * cnt[power[i]] + dfs(nxt[i]) return max(a, b) n = len(power) cnt = Counter(power) power . sort() nxt = [bisect_right(power, x + 2, lo=i + 1) for i, x in enumerate(power)] return dfs(0)

```