LeetCode Challenge Day 26 — 3186. Maximum Total Damage With Spell Casting

Hey folks

This is Day 26 of my LeetCode streak 🚀.
Today’s problem is 3186. Maximum Total Damage With Spell Casting — a dynamic programming problem where we must pick spells for maximum damage but avoid choosing ones too close in value.

📌 Problem Statement

You are given:

• power[i] → the damage of the i-th spell.

Rules:

• Each spell can be cast only once.
• If you cast a spell with value x, then x-2, x-1, x+1, x+2 are all banned.

Return the maximum total damage possible.

Examples

• Input:
  power = [1,1,3,4]
  Output: 6

• Input:
  power = [7,1,6,6]
  Output: 13

💡 Intuition

This is like the Delete and Earn problem.

• First, group all spells with the same value.
• Choosing a number blocks numbers within 2 distance.
• So we only pick numbers at least 3 apart.

🔑 Approach

1. Count total damage for each unique value.
2. Sort these values.
3. Use DP:
   • Skip current → take best from previous.
   • Take current → add its total + best from last allowed value (value ≤ current-3).
4. Use binary search to find the last valid index quickly.

⏱️ Complexity Analysis

• Time complexity: O(n + m log m) where m = unique values.
• Space complexity: O(m).

🧑‍💻 Code (JavaScript)

/**
 * @param {number[]} power
 * @return {number}
 */
var maximumTotalDamage = function(power) {
  const total = new Map();
  for (const v of power) total.set(v, (total.get(v) || 0) + v);

  const vals = Array.from(total.keys()).sort((a, b) => a - b);
  const sums = vals.map(v => total.get(v));
  const n = vals.length;
  const dp = new Array(n).fill(0);

  function findPrev(i) {
    let lo = 0, hi = i - 1, target = vals[i] - 3, ans = -1;
    while (lo <= hi) {
      const mid = (lo + hi) >> 1;
      if (vals[mid] <= target) { ans = mid; lo = mid + 1; }
      else { hi = mid - 1; }
    }
    return ans;
  }

  for (let i = 0; i < n; i++) {
    const prev = findPrev(i);
    const take = sums[i] + (prev >= 0 ? dp[prev] : 0);
    const skip = i > 0 ? dp[i - 1] : 0;
    dp[i] = Math.max(skip, take);
  }

  return dp[n - 1] || 0;
};

🧪 Edge Cases

• All same values → take them all.

• Values spaced far apart → no conflict, take everything.

• Consecutive values → need to skip wisely.

🎥 Reflections

This problem is fun because it mixes greedy grouping with DP thinking.

• Grouping turns the input into smaller chunks.

• DP with binary search makes it efficient.

That’s it for Day 26 of my LeetCode journey!
On to the next challenge 🔥

Happy Coding 👨‍💻