Maximum Total Damage With Spell Casting | Leetcode 3186 | Two Approaches | Java | Hindi Explanation скачать в хорошем качестве

Maximum Total Damage With Spell Casting | Leetcode 3186 | Two Approaches | Java | Hindi Explanation

🔗 Problem Link: https://leetcode.com/problems/maximum... 💻 Solution Link: https://github.com/kernelqueen/Leetco... 🧩 Problem Understanding We are given an array power[] where each number represents a spell’s damage power. When you choose a spell with power x, you cannot choose spells with power x-2, x-1, x+1, or x+2 (i.e., adjacent powers). The goal is to maximize the total damage you can achieve following this restriction. ⚙️ Approach 1 — Recursive (TLE) Idea: Build a frequency map of all power values. Sort unique powers and recursively explore two choices for each index: Take current power → add its total damage and skip conflicting powers. Skip current power → move to the next one. The maximum of both gives the answer. Time complexity grows exponentially since overlapping subproblems are recalculated. ⏱️ Time Complexity: O(2ⁿ) (TLE) 💾 Space Complexity: O(n) (recursion stack) ⚙️ Approach 2 — Recursive + Memoization (Optimized DP) Idea: Same logic as the recursive version, but we cache results in a memoization array dp[]. Each index stores the best damage achievable up to that point. Avoids recomputation, making it efficient enough to pass large inputs. Steps: Build frequency map → count Sort unique powers → List of keys Use recursive helper with memoization to compute dp[i] = max(skip, take). ⏱️ Time Complexity: O(nlogn) 💾 Space Complexity: O(n) ⚙️ Approach 3 — Iterative Dynamic Programming (Bottom-Up) Idea: Convert recursion to an iterative DP approach. For each power: Skip it → inherit previous maximum. Take it → add its damage + best value from a non-conflicting previous index. Store the best result in dp[i]. ⏱️ Time Complexity: O(nlogn) 💾 Space Complexity: O(n) 🧠 Concepts Used Frequency Map Sorting Dynamic Programming (Memoization + Iteration) Non-Adjacent Element Selection Pattern #LeetCode #DynamicProgramming #Java #CodingInterview #Memoization #DP #HashMap #MaximumTotalDamage #Leetcode3186 #IterativeDP #CodingSolution #ProgrammingExplained 0:00 Problem Description 2:18 Example to understand the Approach 6:52 Recursive gives TLE 8:41 Recursive with Memoization 9:39 Code for recursive DP 12:29 Time & Space Complexity 13:24 Code for Iterative DP 15:56 Time & Space Complexity