Maximum Total Damage With Spell Casting - Practice Coding Problems

Maximum Total Damage With Spell Casting - Problem

Array Hash Table Two Pointers Binary Search Dynamic Programming Sorting Counting Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: power = [1,1,3,4]

› Output: 4

💡 Note: We can cast the spell with damage 4. If we cast spells with damage 1, we get total 2 but cannot cast damage 3 or 4. Casting damage 3 gives us 3. Casting damage 4 gives us 4, which is maximum.

Example 2 — Multiple Same Values

$ Input: power = [7,1,6,6]

› Output: 13

💡 Note: We can cast both spells with damage 6 and the spell with damage 1. Total = 6 + 6 + 1 = 13. We cannot include damage 7 because it conflicts with damage 6.

Example 3 — All Consecutive

$ Input: power = [1,2,3,4,5]

› Output: 5

💡 Note: All damages are consecutive and conflict with each other. The best strategy is to pick the single highest damage spell: 5.

Constraints

1 ≤ power.length ≤ 10⁵
1 ≤ power[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of spell damage values with constraint rules

Constraint

Casting spell with damage X blocks X±1 and X±2

Output

Maximum total damage possible

Key Takeaway

🎯 Key Insight: Group identical spells and use dynamic programming with house robber pattern, considering constraint distance of 2

Asked in

G Google 15 M Meta 12 a Amazon 10

The key insight is to group spells by damage value and treat this as a house robber problem with constraint distance of 2. After counting frequencies and sorting, use dynamic programming where each damage value is either fully taken or skipped. Best approach uses binary search for optimal transitions. Time: O(n log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Backtracking)	O(2ⁿ)	O(n)	Try every possible combination of spells and check constraints
Frequency Count + Sorting	O(n log n)	O(n)	Group identical spells, sort by damage, and use dynamic programming
Optimized Dynamic Programming	O(n log k)	O(k)	Most efficient solution using house robber pattern with constraint window

Brute Force (Backtracking) — Algorithm Steps

Try casting each spell
Mark conflicting spells as unusable
Recursively solve remaining subproblem
Return maximum of casting vs skipping

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with all spells available

Branch

For each spell: cast it or skip it

Constrain

Mark conflicting spells as unusable

Result

Return maximum damage found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int backtrack(int index, bool* used, int* power, int n) {
    if (index == n) return 0;
    
    // Skip current spell
    int maxDamage = backtrack(index + 1, used, power, n);
    
    // Try casting current spell if not conflicted
    if (!used[index]) {
        // Mark conflicting spells
        bool* newUsed = (bool*)malloc(n * sizeof(bool));
        memcpy(newUsed, used, n * sizeof(bool));
        int currentPower = power[index];
        for (int i = 0; i < n; i++) {
            if (abs(power[i] - currentPower) <= 2) {
                newUsed[i] = true;
            }
        }
        
        int castDamage = currentPower + backtrack(index + 1, newUsed, power, n);
        if (castDamage > maxDamage) maxDamage = castDamage;
        free(newUsed);
    }
    
    return maxDamage;
}

int solution(int* power, int n) {
    bool* used = (bool*)calloc(n, sizeof(bool));
    int result = backtrack(0, used, power, n);
    free(used);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int power[1000];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        power[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(power, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ)

Each spell has 2 choices (cast or skip), leading to 2^n combinations

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth up to n levels

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Backtracking) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler