We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Total Damage With Spell Casting

Number: 3437

Difficulty: Medium

Paid? No

Companies: Citadel, Meta

Problem Description

Given an array power, where each element represents the damage of a spell, determine the maximum total damage that can be achieved by casting a subset of these spells under the restriction that if you cast a spell with damage d, you cannot cast any spell with damage d-2, d-1, d+1, or d+2. Each spell can only be cast once.

Key Insights

  • The problem is similar to "Delete and Earn" but with an extended conflict range (neighbors are d-2, d-1, d+1, and d+2).
  • Aggregate spells with the same damage value; for each unique damage, calculate totalDamage = damage * frequency.
  • Sort the unique damage values to consider conflicts in a sequential order.
  • Use dynamic programming: for each unique damage value, decide whether to take it (and add the accumulated damage from non-conflicting previous spells) or skip it.
  • When the current damage and the previous damage differ by at most 2, they conflict; otherwise, the current damage can be safely added without conflicts.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the unique damage values, where n is the length of the power array. Space Complexity: O(n) for storing the frequency dictionary and the dp array.

Solution

We start by counting the frequency of each damage value and multiply it by the damage itself to get the total damage contribution for that damage value. Sorting the keys allows us to process damage values in order and detect conflicts by checking if the difference between consecutive keys is less than or equal to 2. Using dynamic programming, for each unique damage d:

  • If d conflicts with the previous damage value (i.e., current damage - previous damage <= 2), update the dp state by taking the maximum of skipping the current damage or adding it to dp[i-2] (if available).
  • If there is no conflict (the gap is at least 3), safely add the current total damage to the previous dp state. The final dp state gives the maximum total damage.

Code Solutions

# Python solution with line-by-line comments
def max_total_damage(power):
    # Create a dictionary to store total damage per unique damage value.
    damage_map = {}
    for d in power:
        damage_map[d] = damage_map.get(d, 0) + d

    # Sort the unique damage values.
    sorted_damages = sorted(damage_map.keys())
    
    # Initialize dp list for dynamic programming.
    n = len(sorted_damages)
    dp = [0] * n
    dp[0] = damage_map[sorted_damages[0]]
    
    for i in range(1, n):
        # Check if current damage conflicts with the previous one.
        if sorted_damages[i] - sorted_damages[i - 1] <= 2:
            # If there's a conflict, decide to either skip current or take current and add best from two steps before.
            prev = dp[i - 2] if i > 1 else 0
            dp[i] = max(dp[i - 1], prev + damage_map[sorted_damages[i]])
        else:
            # No conflict; add current damage contribution.
            dp[i] = dp[i - 1] + damage_map[sorted_damages[i]]
    
    return dp[-1]

# Example usage:
#print(max_total_damage([1,1,3,4]))  # Expected output: 6
#print(max_total_damage([7,1,6,6]))  # Expected output: 13
← Back to All Questions