LeetCode 3186 - Maximum Total Damage With Spell Casting

The problem gives us an array power, where each element represents the damage value of a spell. Every spell can be used at most once, and multiple spells may share the same damage value. The restriction is the important part of the problem.

leetcodemediumarrayhash-tabletwo-pointersbinary-searchdynamic-programmingsortingcounting

LeetCode Problem 3186

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Two Pointers, Binary Search, Dynamic Programming, Sorting, Counting

Solution

Problem Understanding

The problem gives us an array power, where each element represents the damage value of a spell. Every spell can be used at most once, and multiple spells may share the same damage value.

The restriction is the important part of the problem. If we decide to cast a spell with damage x, then we are forbidden from casting any spell whose damage is:

  • x - 2
  • x - 1
  • x + 1
  • x + 2

In other words, any two chosen spell damage values must differ by at least 3.

The goal is to maximize the total damage dealt by selecting a subset of spells that satisfies this restriction.

A key detail is that duplicates are allowed. If we choose damage value x, we are still allowed to cast every spell whose damage is also x, because the restriction only applies to values differing by 1 or 2. This means identical values are compatible with each other.

For example, if the array is:

[7,1,6,6]

we may choose both 6s and also choose 1, because:

  • 6 and 6 are compatible
  • 1 differs from 6 by 5, which is allowed

The total becomes:

1 + 6 + 6 = 13

The constraints are large:

  • power.length can reach 100000
  • power[i] can reach 10^9

This immediately tells us that exponential subset enumeration is impossible. Even quadratic solutions may become too slow. We need something around O(n log n).

Important edge cases include:

  • Arrays where all values are identical
  • Arrays where every value conflicts with every other value
  • Sparse large numbers such as [1, 1000000000]
  • Heavy duplication counts
  • Situations where taking a smaller value multiple times is better than taking a larger single value

These cases make greedy selection unreliable, so dynamic programming becomes necessary.

Approaches

Brute Force Approach

A brute force solution would try every possible subset of spells.

For each subset, we would verify whether every pair of chosen spell values satisfies the rule that their difference is at least 3. If valid, we compute the total damage and keep the maximum.

This approach is correct because it explores all possibilities, guaranteeing that the optimal subset is considered.

However, the complexity is catastrophic. With n spells, there are 2^n subsets. Even for n = 30, this becomes impractical. The problem allows 100000 elements, so brute force is completely infeasible.

Key Insight

The critical observation is that spells with the same damage value are always compatible with each other.

Suppose value 5 appears four times. If we decide to use damage 5, there is never a reason to take only some of them. Since equal values do not conflict, taking all of them always increases the total damage.

This means we can compress the array into:

damage value -> total contribution

For example:

[1,1,3,4]

becomes:

1 -> 2
3 -> 3
4 -> 4

Now the problem transforms into:

Choose distinct damage values so that chosen values differ by at least 3, maximizing the sum of their grouped contributions.

This becomes very similar to the classic "House Robber" style dynamic programming problem, except the conflict distance is not fixed by index, but by numeric value difference.

After sorting unique values, we can use dynamic programming with binary search or two pointers to find the last compatible value for each position.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Tries every subset and validates it
Optimal O(n log n) O(n) Uses counting, sorting, and DP

Algorithm Walkthrough

Optimal Dynamic Programming Algorithm

  1. Count the total contribution of each damage value.

We use a hash map where:

total[value] += value

If 5 appears three times, its contribution becomes 15.

This compression is important because duplicates are always either all taken or all skipped. 2. Extract and sort all unique damage values.

Suppose the unique values are:

values = [1, 3, 4, 7]

Sorting allows us to process values from small to large while maintaining compatibility relationships. 3. Define the DP state.

Let:

dp[i]

represent the maximum total damage achievable using unique values up to index i. 4. For each value, determine the last compatible value.

If current value is:

values[i]

then we need the largest index j < i such that:

values[j] <= values[i] - 3

because differences of 1 and 2 are forbidden. 5. Use binary search to find that compatible index efficiently.

Since the values array is sorted, we can binary search for:

values[i] - 3
  1. Compute the transition.

We have two choices:

  • Skip current value:
dp[i - 1]
  • Take current value:
total[values[i]] + dp[j]

where j is the last compatible index.

Therefore:

dp[i] = max(skip, take)
  1. Return the final DP value.

The answer is:

dp[last index]

Why it works

The algorithm works because the decision for each unique value is independent once we know the last compatible value. Sorting guarantees that all conflicts occur locally in the ordered sequence. Dynamic programming ensures that every optimal prefix solution is reused instead of recomputed. Since each state considers both taking and skipping the current value, all valid combinations are implicitly explored.

Python Solution

from typing import List
from collections import Counter
import bisect

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        total_damage = Counter()

        for value in power:
            total_damage[value] += value

        values = sorted(total_damage.keys())
        n = len(values)

        dp = [0] * n

        for i in range(n):
            current_value = values[i]
            current_total = total_damage[current_value]

            # Find last index with value <= current_value - 3
            j = bisect.bisect_right(values, current_value - 3) - 1

            take = current_total
            if j >= 0:
                take += dp[j]

            skip = dp[i - 1] if i > 0 else 0

            dp[i] = max(take, skip)

        return dp[-1]

The implementation begins by grouping identical spell values together using a Counter. Instead of treating every spell independently, we aggregate their total contribution. This significantly reduces the effective problem size.

Next, we sort the unique values. Sorting is necessary because compatibility depends on numeric distance.

The dynamic programming array stores the best achievable total up to each unique value index.

For every value, we use bisect_right to locate the last value that differs by at least 3. This gives the latest compatible state that can safely combine with the current value.

The transition compares two possibilities:

  • Taking the current grouped value
  • Skipping it

The larger result becomes the optimal solution for that prefix.

Finally, the last DP entry contains the global optimum.

Go Solution

package main

import (
	"sort"
)

func maximumTotalDamage(power []int) int64 {
	totalDamage := make(map[int]int64)

	for _, value := range power {
		totalDamage[value] += int64(value)
	}

	values := make([]int, 0, len(totalDamage))
	for value := range totalDamage {
		values = append(values, value)
	}

	sort.Ints(values)

	n := len(values)
	dp := make([]int64, n)

	for i := 0; i < n; i++ {
		currentValue := values[i]
		currentTotal := totalDamage[currentValue]

		// Find last index with value <= currentValue - 3
		j := sort.Search(len(values), func(k int) bool {
			return values[k] > currentValue-3
		}) - 1

		take := currentTotal
		if j >= 0 {
			take += dp[j]
		}

		var skip int64
		if i > 0 {
			skip = dp[i-1]
		}

		if take > skip {
			dp[i] = take
		} else {
			dp[i] = skip
		}
	}

	return dp[n-1]
}

The Go implementation follows the same logic as the Python version, but there are a few language specific considerations.

The total damage values are stored as int64 because the answer can exceed 32 bit integer limits. If all 100000 spells have value 10^9, the result can become extremely large.

Go does not provide a direct equivalent of Python's bisect_right, so we use sort.Search with a custom predicate to locate the first value greater than currentValue - 3.

Slices are dynamically sized and work naturally for the DP array and sorted unique values.

Worked Examples

Example 1

Input:

power = [1,1,3,4]

Step 1: Group identical values

Value Total Contribution
1 2
3 3
4 4

Sorted unique values:

[1, 3, 4]

Step 2: DP Processing

i Current Value Compatible Index j Take Skip dp[i]
0 1 -1 2 0 2
1 3 -1 3 2 3
2 4 0 4 + 2 = 6 3 6

Final answer:

6

Chosen values are:

1, 1, 4

Example 2

Input:

power = [7,1,6,6]

Step 1: Group identical values

Value Total Contribution
1 1
6 12
7 7

Sorted unique values:

[1, 6, 7]

Step 2: DP Processing

i Current Value Compatible Index j Take Skip dp[i]
0 1 -1 1 0 1
1 6 0 12 + 1 = 13 1 13
2 7 0 7 + 1 = 8 13 13

Final answer:

13

Chosen values are:

1, 6, 6

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting unique values and binary searches dominate
Space O(n) Hash map and DP array store up to n unique values

The counting phase is linear. Sorting the unique values costs O(k log k), where k is the number of distinct values and k <= n.

For each unique value, we perform one binary search, costing O(log k). Therefore the total complexity remains O(n log n).

The space complexity is linear because we store grouped totals, sorted unique values, and the DP array.

Test Cases

from typing import List

class Solution:
    def maximumTotalDamage(self, power: List[int]) -> int:
        from collections import Counter
        import bisect

        total_damage = Counter()

        for value in power:
            total_damage[value] += value

        values = sorted(total_damage.keys())
        n = len(values)

        dp = [0] * n

        for i in range(n):
            current_value = values[i]
            current_total = total_damage[current_value]

            j = bisect.bisect_right(values, current_value - 3) - 1

            take = current_total
            if j >= 0:
                take += dp[j]

            skip = dp[i - 1] if i > 0 else 0

            dp[i] = max(take, skip)

        return dp[-1]

solution = Solution()

assert solution.maximumTotalDamage([1,1,3,4]) == 6  # Provided example 1
assert solution.maximumTotalDamage([7,1,6,6]) == 13  # Provided example 2

assert solution.maximumTotalDamage([5]) == 5  # Single element
assert solution.maximumTotalDamage([2,2,2]) == 6  # All identical values
assert solution.maximumTotalDamage([1,2,3]) == 3  # Every value conflicts
assert solution.maximumTotalDamage([1,4,7]) == 12  # All values compatible
assert solution.maximumTotalDamage([1,1,1,4,4,4]) == 15  # Multiple compatible duplicates
assert solution.maximumTotalDamage([1,2,4,5,7,8]) == 12  # Alternating compatible values
assert solution.maximumTotalDamage([10,12,13,15]) == 25  # Optimal skipping
assert solution.maximumTotalDamage([1000000000]) == 1000000000  # Maximum value boundary
assert solution.maximumTotalDamage([1,1000000000]) == 1000000001  # Large sparse gap
assert solution.maximumTotalDamage([3,3,3,5,5,8]) == 17  # Mixed duplicates and conflicts
Test Why
[1,1,3,4] Validates provided example
[7,1,6,6] Validates duplicate handling
[5] Smallest possible input
[2,2,2] Ensures all duplicates are accumulated
[1,2,3] Every value conflicts with others
[1,4,7] All values are compatible
[1,1,1,4,4,4] Large grouped contributions
[1,2,4,5,7,8] Multiple competing choices
[10,12,13,15] Verifies DP transition correctness
[1000000000] Large numeric boundary
[1,1000000000] Sparse values with no conflicts
[3,3,3,5,5,8] Combination of duplicates and spacing

Edge Cases

One important edge case occurs when all spell values are identical. For example:

[5,5,5,5]

A buggy implementation might incorrectly think duplicate values conflict with each other. In reality, only values differing by 1 or 2 are forbidden. The grouping strategy handles this correctly by summing all identical values together.

Another important case occurs when every value conflicts with every other value. Consider:

[1,2,3]

Here, every pair differs by at most 2, so only one distinct value may be selected. The DP correctly evaluates all possibilities and chooses the maximum contribution.

A third critical case involves sparse large numbers:

[1,1000000000]

The values are extremely far apart, so both can be selected together. Since the algorithm relies only on sorted ordering and binary search, large numeric gaps cause no issues.

Another subtle edge case is when taking many smaller duplicates is better than taking a single larger value. For example:

[4,4,4,6]

The grouped contribution for 4 becomes 12, which is better than choosing 6. A greedy algorithm focused only on larger individual values would fail here, but the DP correctly compares total grouped contributions.