3186. Maximum Total Damage With Spell Casting

MediumArrayHash TableTwo PointersBinary SearchDynamic ProgrammingCountingSorting

Problem Description

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.

Intuition

To tackle this problem, the approach involves sorting the array power and understanding that each element represents a unique damage value a magician can cast. The main challenge is to select which spells to cast such that the sum of their damages is maximized, while also adhering to the restriction that casting a spell prevents nearby spells from being cast.

Sorting and Counting Frequencies:
- First, we sort the power array to facilitate decision-making. This allows for straightforward determination of nearby elements.
- We also count the frequency of each damage value using a dictionary, cnt, as casting spells with the same damage might be beneficial.
Defining the Problem Using Dynamic Programming:
- Define a recursive function dfs with memoization to calculate the maximum total damage starting from the ith index. Memoization ensures we don't recalculate results and speeds up the process.
- At each spell with damage power[i], we face two choices:
  - Skip to the next set of unique damage values (by advancing by cnt[power[i]] in the array).
  - Use the current damage value and jump directly to nxt[i], which represents the first index with a damage value greater than power[i] + 2. Using binary search, we precompute this nxt array to optimize performance.
Maximizing Total Damage:
- For each choice at index i, calculate the possible total damage and take the maximum. This considers both ignoring and casting the current spell, with the aim to maximize the accumulated damage.
Final Calculation:
- By initializing the process from the first spell, dfs(0) provides the desired result for the maximum possible damage.

By addressing the problem with these principles, the solution effectively leverages sorting, frequency counting, and dynamic programming techniques to find the optimal sequence of spells to cast.

Learn more about Two Pointers, Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

The key idea in solving the problem is to use a combination of sorting, frequency counting, binary search, and dynamic programming with memoization. Here’s how the solution is implemented:

Sorting the Damage Values:
- Begin by sorting the power array. This simplifies the task of identifying any spells that we need to skip due to adjacent values.
Counting Frequencies:
- Use Counter from the collections module to determine how many times each damage value appears in the power array. This frequency information is stored in cnt.
Setup for Dynamic Programming:
- Compute an auxiliary array nxt.
  - For each damage value power[i], nxt[i] stores the index of the next damage value that can be used if power[i] is chosen. This index is determined using bisect_right, effectively skipping over inaccessible damages (power[i] + 1 and power[i] + 2).
Memoized Depth-First Search (dfs):
- Define a recursive function dfs(i) which computes the maximum possible damage starting from the ith index.
- Base Case: If i is beyond the length of the array, return 0.
- Recursive Case:
  - Compute two scenarios:
    1. Skip the Current Damage Value: Compute dfs(i + cnt[power[i]]) which skips all occurrences of power[i].
    2. Use the Current Damage Value: Add the total damage power[i] * cnt[power[i]] from using all spells of this damage and move to dfs(nxt[i]).
  - Return the maximum of these two scenarios.
Result Computation:
- Begin the recursive process with dfs(0) to evaluate from the start of the sorted array.

The above logic efficiently computes the maximum damage by balancing decisions at each damage value between choosing or skipping spells, guided by the constraints provided in the problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a simple example to illustrate the solution approach. Consider the power array as [2, 3, 4, 6, 8].

Sorting the Damage Values:
- The input array is already sorted: [2, 3, 4, 6, 8].
Counting Frequencies:
- Use a Counter to determine the frequency of each damage value. Since each value is unique, frequencies are: {2: 1, 3: 1, 4: 1, 6: 1, 8: 1}.
Setup for Dynamic Programming:
- Compute the nxt array:
  - Start with 2. The next eligible damage value should be greater than 2 + 2 = 4, thus nxt[0] = 3 (index of 6).
  - Similarly, for 3 (power[1]): nxt[1] = 3.
  - For 4 (power[2]): nxt[2] = 3.
  - For 6 (power[3]): nxt[3] = 4 (index of 8).
  - For 8 (power[4]): nxt[4] = 5 (out of bounds).
Memoized Depth-First Search (dfs):
- Define and call dfs(i) recursively from index 0.
- Calculations:
  - dfs(0):
    - Skip 2: Compute dfs(1).
    - Use 2: Total damage = 2 * 1 + dfs(3).
  - dfs(1):
    - Skip 3: Compute dfs(2).
    - Use 3: Total damage = 3 * 1 + dfs(3).
  - dfs(2):
    - Skip 4: Compute dfs(3).
    - Use 4: Total damage = 4 * 1 + dfs(3).
  - dfs(3):
    - Skip 6: Compute dfs(4).
    - Use 6: Total damage = 6 * 1 + dfs(4).
  - dfs(4):
    - Skip 8: Compute dfs(5) (returns 0).
    - Use 8: Total damage = 8 * 1 + dfs(5) (returns 8).
Result Computation:
- The recursive evaluation yields the maximum damage that can be achieved, with dfs(0) returning the final result.

By choosing either to skip or use damage values strategically while respecting constraints, the maximum possible damage for the given example can be accurately determined.

Solution Implementation

1from typing import List
2from collections import Counter
3from functools import cache
4from bisect import bisect_right
5
6class Solution:
7    def maximumTotalDamage(self, power: List[int]) -> int:
8        @cache
9        def dfs(i: int) -> int:
10            # Base case: if the index exceeds the list length, return 0
11            if i >= n:
12                return 0
13            # Calculate total damage when skipping the current element group
14            skip_current = dfs(i + cnt[power[i]])
15            # Calculate total damage when taking the current element group
16            # and jumping to the next valid position
17            take_current = power[i] * cnt[power[i]] + dfs(nxt[i])
18            # Return the maximum of the two strategies
19            return max(skip_current, take_current)
20
21        n = len(power)  # Length of the power list
22      
23        # Count occurrences of each element in power
24        cnt = Counter(power)
25      
26        # Sort the power list to manage damage and occurrences effectively
27        power.sort()
28      
29        # Create a list to hold the next valid jump positions
30        # If the element x is chosen, jump to the first element > x + 2
31        nxt = [bisect_right(power, x + 2, lo=i + 1) for i, x in enumerate(power)]
32      
33        # Start the DFS from the first element
34        return dfs(0)
35

1import java.util.Arrays;
2import java.util.HashMap;
3import java.util.Map;
4
5class Solution {
6    // Array to store the maximum damage starting from each index 
7    private Long[] maxDamageMemo;
8
9    // Array to store the power values
10    private int[] powerArray;
11
12    // Map to count occurrences of each power value
13    private Map<Integer, Integer> powerCount;
14
15    // Array to store the next available index for damage calculation
16    private int[] nextIndex;
17
18    // Total number of elements in the power array
19    private int totalPowers;
20
21    public long maximumTotalDamage(int[] power) {
22        // Sort the power array to facilitate processing in order
23        Arrays.sort(power);
24        this.powerArray = power;
25        totalPowers = power.length;
26      
27        // Initialize the memoization array
28        maxDamageMemo = new Long[totalPowers];
29      
30        // Initialize the map to count occurrences of each power value
31        powerCount = new HashMap<>(totalPowers);
32      
33        // Initialize the next index array
34        nextIndex = new int[totalPowers];
35      
36        // Fill out the power count map and next index array
37        for (int i = 0; i < totalPowers; ++i) {
38            powerCount.merge(power[i], 1, Integer::sum);
39            int nextPos = Arrays.binarySearch(power, power[i] + 3);
40            nextPos = nextPos < 0 ? -nextPos - 1 : nextPos;
41            nextIndex[i] = nextPos;
42        }
43      
44        // Start the recursive calculation from index 0
45        return dfs(0);
46    }
47
48    // Recursive function to calculate maximum damage starting from index i
49    private long dfs(int i) {
50        // Base case: if the index is out of bounds, return 0 damage
51        if (i >= totalPowers) {
52            return 0;
53        }
54      
55        // If we have previously calculated the maximum damage from index i, return it
56        if (maxDamageMemo[i] != null) {
57            return maxDamageMemo[i];
58        }
59      
60        // Skip the current power[i] and calculate damage from the next different power
61        long skipCurrent = dfs(i + powerCount.get(powerArray[i]));
62      
63        // Include the current power[i] and calculate damage from the next available index
64        long includeCurrent = 1L * powerArray[i] * powerCount.get(powerArray[i]) + dfs(nextIndex[i]);
65      
66        // Record the maximum damage possible starting from index i
67        return maxDamageMemo[i] = Math.max(skipCurrent, includeCurrent);
68    }
69}
70

1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    long long maximumTotalDamage(std::vector<int>& power) {
8        // Sort the array to handle elements in non-decreasing order
9        std::sort(power.begin(), power.end());
10
11        // Store the sorted power array
12        this->power = power;
13        numElements = power.size();
14
15        // Resize vectors to store intermediate results 
16        dp.resize(numElements);
17        nextIndex.resize(numElements);
18
19        // Count occurrences and compute next index for each element
20        for (int i = 0; i < numElements; ++i) {
21            powerCount[power[i]]++;
22            nextIndex[i] = std::upper_bound(power.begin() + i + 1,
23                                             power.end(),
24                                             power[i] + 2) - power.begin();
25        }
26
27        // Begin the depth-first search from the first element
28        return dfs(0);
29    }
30
31private:
32    std::unordered_map<int, int> powerCount;  // Map to count occurrences of each power level
33    std::vector<long long> dp;                // Memoization array for storing maximum damage
34    std::vector<int> power;                   // To store the power levels array
35    std::vector<int> nextIndex;               // To store the next index to process
36    int numElements;                          // Number of elements in power array
37
38    // Depth-first search function to calculate maximum damage starting from index i
39    long long dfs(int i) {
40        // Base case: If index is out of bounds, return 0 as damage
41        if (i >= numElements) {
42            return 0;
43        }
44
45        // If already computed, return the memoized result
46        if (dp[i] != 0) {
47            return dp[i];
48        }
49
50        // Option 1: Skip the current power level and move forward
51        long long optionSkip = dfs(i + powerCount[power[i]]);
52
53        // Option 2: Use current power level damage and calculate from the next viable index
54        long long optionUse = 1LL * power[i] * powerCount[power[i]] + dfs(nextIndex[i]);
55
56        // Store the maximum of both options in dp[i]
57        return dp[i] = std::max(optionSkip, optionUse);
58    }
59};
60

1function maximumTotalDamage(power: number[]): number {
2    const n = power.length;
3  
4    // Sort the array to easily find subsequences
5    power.sort((a, b) => a - b);
6  
7    // Array to store the maximum damage for each starting point
8    const f: number[] = Array(n).fill(0);
9
10    // Record to count the frequency of each power value
11    const cnt: Record<number, number> = {};
12
13    // Array to find the next starting point that has a power greater than the current power + 2
14    const nxt: number[] = Array(n).fill(0);
15
16    // Calculate frequencies and next indices for each power[i]
17    for (let i = 0; i < n; ++i) {
18        cnt[power[i]] = (cnt[power[i]] || 0) + 1;
19
20        // Perform binary search for next index with power greater than power[i] + 2
21        let [l, r] = [i + 1, n];
22        while (l < r) {
23            const mid = (l + r) >> 1;
24            if (power[mid] > power[i] + 2) {
25                r = mid;
26            } else {
27                l = mid + 1;
28            }
29        }
30        nxt[i] = l;
31    }
32
33    // Recursive function with memoization to calculate maximum total damage
34    const dfs = (i: number): number => {
35        // Base case: if index exceeds the power array
36        if (i >= n) {
37            return 0;
38        }
39        // Return cached result if already computed
40        if (f[i]) {
41            return f[i];
42        }
43
44        // Either skip the current element or take the subsequence starting at current element
45        const skipCurrent = dfs(i + cnt[power[i]]);
46        const takeCurrent = power[i] * cnt[power[i]] + dfs(nxt[i]);
47
48        // Memoize the maximum damage for the current index and return
49        return (f[i] = Math.max(skipCurrent, takeCurrent));
50    };
51
52    // Calculate maximum total damage starting from the first index
53    return dfs(0);
54}
55

Time and Space Complexity

The time complexity is O(n log n), primarily due to sorting the power list which takes O(n log n), and the use of bisect_right, which also contributes O(n log n) across all iterations combined. The recursive DFS with memoization (@cache) ensures that each unique state is only computed once, effectively making the DFS part of the code take O(n).

The space complexity is O(n). This is because the memoization (@cache) requires space to store results for each of the n unique states, and additional linear space is used for auxiliary arrays like cnt and nxt.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

The three-steps of Depth First Search are:

Identify states;
Draw the state-space tree;
DFS on the state-space tree.

True

False

I don’t know