Power of Heroes

Problem Description

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:

Let i_0, i_1, ... ,i_k be the indices of the heroes in a group. Then, the power of this group is max(nums[i_0], nums[i_1], ... ,nums[i_k])^2 * min(nums[i_0], nums[i_1], ... ,nums[i_k]).

Return the sum of the power of all non-empty groups of heroes possible. Since the sum could be very large, return it modulo 10^9 + 7.

Key Insights

• Each group can be defined by its maximum and minimum values.
• The contribution of each hero's strength to the total power can be calculated based on how many groups they can be a part of.
• Sorting the array can help in efficiently calculating the number of valid groups for each hero strength.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the array. Each group contribution can be calculated in linear time after sorting. Space Complexity: O(1) if we do not count the space used for the input array, or O(n) if we consider additional storage for intermediate results.

Solution

To solve this problem, we can follow these steps:

1. Sort the nums array to easily identify maximum and minimum values in any group.
2. For each hero strength, calculate its contribution to the power based on how many groups it can form as the maximum and minimum.
3. Use combinatorial counting to find how many groups can include a certain hero based on its position in the sorted array.

Code Solutions