Power of Heroes - Video Solutions

Problem Overview: You are given an array where each value represents a hero's strength. For every non‑empty group of heroes, the group's power is defined as max(hero)^2 * min(hero). The task is to compute the sum of power across all possible groups. A brute force enumeration of all subsets quickly becomes infeasible, so the key is recognizing how each element contributes when it acts as the maximum or minimum in a subset.

Approach 1: Sorting and Combinatorial Contribution (O(n log n) time, O(1) extra space)

Sort the array so that when you iterate from left to right, the current element is the maximum of any subset ending at that position. The trick is computing how much previous elements contribute as the minimum. Maintain a running prefix contribution that represents the sum of minimum values across all subsets formed so far. When processing nums[i], treat it as the maximum and combine it with all previously formed subsets. The total contribution becomes nums[i]^2 * (nums[i] + prefixSum). After processing the element, update the prefix sum to include new subset combinations. Sorting ensures the minimum is always from earlier elements, which keeps the counting correct.

This technique converts exponential subset enumeration into a linear scan after sorting. Modular arithmetic is used because values grow quickly. The approach works well because each hero is processed exactly once while the prefix state captures the contribution of all earlier subset minimums.

Approach 2: Dynamic Programming for Group Contribution (O(n log n) time, O(n) space)

This method also begins with sorting the array. Define a DP state representing the total contribution of subsets whose maximum element is the current hero. Each step builds on previously computed subsets by extending them with the current element. The DP recurrence tracks the accumulated minimum contribution from earlier elements and updates it as new subsets are formed. When a new hero becomes the maximum, its contribution is calculated using previously accumulated subset values plus the single‑element subset.

The dynamic programming perspective makes the subset construction explicit: each element either starts a new group or extends existing groups. Maintaining cumulative sums avoids recomputing subset minimums repeatedly. Although conceptually different, this method produces the same optimized complexity as the combinational approach.

Both strategies rely heavily on sorting and incremental contribution tracking, which makes them good exercises in array processing combined with sorting. The prefix accumulation technique also resembles patterns seen in prefix sum and dynamic programming problems.

Recommended for interviews: The sorting + combinational contribution approach is what interviewers usually expect. It demonstrates that you can transform subset enumeration into per‑element contribution analysis. Mentioning the DP interpretation is useful because it shows deeper understanding of how subset states accumulate, but the concise prefix contribution solution is typically the cleanest implementation.