You are given a 0-indexed integer array nums representing the strength of some heroes. The power of a group of heroes is defined as follows:
i0, i1, ... ,ik be the indices of the heroes in a group. Then, the power of this group is max(nums[i0], nums[i1], ... ,nums[ik])2 * min(nums[i0], nums[i1], ... ,nums[ik]).Return the sum of the power of all non-empty groups of heroes possible. Since the sum could be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,1,4] Output: 141 Explanation: 1st group: [2] has power = 22 * 2 = 8. 2nd group: [1] has power = 12 * 1 = 1. 3rd group: [4] has power = 42 * 4 = 64. 4th group: [2,1] has power = 22 * 1 = 4. 5th group: [2,4] has power = 42 * 2 = 32. 6th group: [1,4] has power = 42 * 1 = 16. 7th group: [2,1,4] has power = 42 * 1 = 16. The sum of powers of all groups is 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141.
Example 2:
Input: nums = [1,1,1] Output: 7 Explanation: A total of 7 groups are possible, and the power of each group will be 1. Therefore, the sum of the powers of all groups is 7.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109Problem 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.
This approach involves sorting the heroes by strength and calculating how often each element is the maximum in some group.
By iterating through the sorted array, for each element, we count how many subarrays it serves as the maximum. We then calculate its contribution to the total power when it is the maximum element, considering every case where it combines with smaller elements. This significantly reduces the computational overhead compared to evaluating each possible group separately.
In Python, the method sorts the array and precomputes the powers of two modulo 109 + 7 for efficiency. For every hero's strength, it is considered as both a maximum and minimum at different positions, and contributions are calculated accordingly.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing powers of 2.
This approach utilizes dynamic programming to handle and store contributions of each element when it is the max or min in any group. By storing these contributions, we can avoid recalculating them from scratch for each possible group configuration.
We leverage precomputed values to avoid redundancy and ensure that each calculation is done efficiently, utilizing previous calculations to mitigate the time complexity.
In Java, similar logic is applied using sorting and dynamic programming logic to ensure that reused computations contribute correctly to the final answer. Modulo operations ensure that intermediate large values are managed efficiently.
Java
JavaScript
Time Complexity: O(n log n) due to sorting, followed by linear dynamic computations.
Space Complexity: O(n) for storing power computations.
We notice that the problem involves the maximum and minimum values of a subsequence, and the order of elements in the array does not affect the final result. Therefore, we can sort the array first.
Next, we enumerate each element as the minimum value of the subsequence. Let's denote each element of the array as a_1, a_2, cdots, a_n. The contribution of the subsequence with a_i as the minimum value is:
$
a_i times (a_{i}^{2} + a_{i+1}^2 + 2 times a_{i+2}^2 + 4 times a_{i+3}^2 + cdots + 2^{n-i-1} times a_n^2)
We notice that each a_i will be multiplied by a_i^2, which we can directly add to the answer. For the remaining part, we can maintain it with a variable p, initially set to 0.
Then, we enumerate a_i from right to left. Each time, we add a_i times p to the answer, and then set p = p times 2 + a_i^2.
After enumerating all a_i, return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n$ is the length of the array.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Combinatorial Contribution | Time Complexity: O(n log n) due to sorting. Space Complexity: O(n) for storing powers of 2. |
| Dynamic Programming for Group Contribution | Time Complexity: O(n log n) due to sorting, followed by linear dynamic computations. Space Complexity: O(n) for storing power computations. |
| Sorting + Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting and Combinatorial Contribution | O(n log n) | O(1) | Best general solution. Efficient for large arrays and commonly expected in interviews. |
| Dynamic Programming for Group Contribution | O(n log n) | O(n) | Useful for understanding subset construction and cumulative contribution patterns. |
Leetcode BiWeekly contest 104 - Hard - Power of Heroes • Prakhar Agrawal • 1,317 views views
Watch 8 more video solutions →Practice Power of Heroes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor