Power of Heroes — Editorial

Opening the reading…

Intuitionassigning every group to one sorted maximum

Sort the strengths from smallest to largest. Consider a group whose largest selected element is nums[i]. Its power always contains nums[i] squared, so the remaining question is the sum of the possible minimum strengths for groups assigned to this maximum. Assign a group to the rightmost maximum it contains; this makes the assignment unique even when several strengths are equal.

If nums[j] is the minimum and j is at most i, both endpoints must be selected, every index between them may be selected or skipped, and every index after i must be skipped. There are 2^(i - j - 1) choices for the interior. Thus nums[j] is weighted by that power of two, and the total contribution for maximum i is nums[i] squared times the weighted minimum sum.

Approachturning the subset count into one running value

Sort nums so every processed element is at least as large as the elements before it; without this order, an earlier element would not reliably be the minimum and the current element would not reliably be the assigned maximum.

Maintain s as the sum of minimum strengths for all groups formed from already processed elements, with the weighting needed when the next maximum is considered; this avoids recomputing every possible minimum.

For the current value x, add x squared times x for the singleton group; omitting this term loses the group whose minimum and maximum are both x.

Add x squared times s for all groups that already contain an earlier minimum and now use x as their maximum; each such group's power gains the factor x squared.

Update s to x + 2s after using it. The x creates the singleton group for future maxima, while 2s accounts for choosing or skipping the current x in every older group.

Take every multiplication modulo 1e9 + 7 and use long long for intermediate products; int multiplication can overflow before the remainder is taken.

Return ans after the scan, because each group has been assigned to exactly one rightmost selected maximum and has therefore contributed once.

Complexitysorting dominates the scan

MEASURE	BOUND	WHY
Time	O(n log n)	Sorting performs the dominant work on n elements, and the following scan visits each element once. No subset is enumerated: all of the 2^n groups are represented by the one running sum.
Space	O(log n) extra	The array is sorted in place, and the scan uses only a constant number of variables. The standard comparison sort may use O(log n) stack space; unlike a recursive structure, this bound does not degrade for any particular input shape. Output storage is excluded because the required result is one integer.

Here n is the number of heroes. The returned value is a single integer and is excluded from extra-space usage.

Annotated solutionC++ · sorted one-pass prefix recurrence

CPPSort first, then use s to add every group whose assigned maximum is the current value.

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int sumOfPower(vector<int>& nums) {
        const long long MOD = 1000000007LL;
        sort(nums.begin(), nums.end());

        long long ans = 0;
        long long s = 0;

        for (int x : nums) {
            long long value = x;
            ans = (ans + value * value % MOD * (value + s) % MOD) % MOD;
            s = (value + 2 * s) % MOD;
        }

        return static_cast<int>(ans);
    }
};

The order of the two lines inside the loop matters. ans uses the old s, which describes groups made before x was considered. Only after those groups receive x squared as their maximum do you update s so that future maxima can extend them. Updating s first would count x as part of the current maximum's minimum combinations and change the weights.