#2681

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Power of Heroes

Calculate the total power of all non-empty hero groups using state transition dynamic programming efficiently with sorting.

array math dynamic programming sorting prefix sum

Problem Statement

You are given a 0-indexed integer array nums where each element represents the strength of a hero. The power of a group of heroes is defined as the square of the maximum strength in the group multiplied by the minimum strength in the group. Your task is to compute the sum of the power of every possible non-empty group of heroes.

Since the sum of powers can be very large, return it modulo 10^9 + 7. Constraints are 1 <= nums.length <= 10^5 and 1 <= nums[i] <= 10^9. Sorting the array and using dynamic programming on state transitions helps manage computations efficiently.

Examples

Example 1

Input: nums = [2,1,4]

Output: 141

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

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 <= 105
1 <= nums[i] <= 109

Solution Approach

Sort and Initialize

Sort nums in ascending order to simplify the calculation of maximum values in each group. Initialize a dp array to store cumulative contributions and a total variable to accumulate the sum of all powers.

Dynamic Programming State Transition

Iterate over the sorted array. For each nums[i], compute its contribution to all subsets ending at i using the previous dp state. The formula combines dp[i-1], nums[i], and nums[i] squared to reflect maximum and minimum calculations in the group.

Accumulate and Modulo

After updating dp for each element, add dp[i] to the total sum. Apply modulo 10^9 + 7 at each step to prevent overflow and return the final total as the sum of powers of all non-empty hero groups.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) for sorting plus O(n) for DP iteration, giving O(n log n) overall. Space complexity is O(n) for storing DP states, though it can be optimized to O(1) with rolling variables.

What Interviewers Usually Probe

Sorting the array hints at a state transition dynamic programming solution.
Watch for integer overflow in calculations; modulo is essential.
Consider how each element contributes to all subsets including it.

Common Pitfalls or Variants

Common pitfalls

Failing to account for modulo during each addition can cause overflow.
Incorrectly calculating maximum or minimum in DP updates leads to wrong sums.
Assuming subsets are independent without considering cumulative state leads to inefficiency.

Follow-up variants

Compute sum of hero group powers without modulo constraints, observing integer overflow.
Find the maximum single group power instead of sum of all groups using the same DP pattern.
Restrict groups to size k and sum powers using state transition DP optimized for fixed lengths.

FAQ

What is the main pattern used in Power of Heroes?

The problem uses state transition dynamic programming, updating cumulative sums as you iterate through sorted hero strengths.

How does sorting help in this problem?

Sorting ensures that the maximum of each subset is easily tracked, simplifying the DP calculation of each group's power.

Can we optimize space usage in this DP approach?

Yes, instead of storing a full DP array, a rolling variable can hold the previous cumulative contribution, reducing space to O(1).

Why do we need modulo 10^9 + 7?

The sum of powers can be extremely large, so modulo prevents integer overflow and keeps results within limits.

How does GhostInterview assist with subset DP problems?

It guides through computing each element's contribution to all subsets using DP, showing efficient state transitions and accumulation.

terminal

Solution

Solution 1: Sorting + Mathematics

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.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        nums.sort()
        ans = 0
        p = 0
        for x in nums[::-1]:
            ans = (ans + (x * x % mod) * x) % mod
            ans = (ans + x * p) % mod
            p = (p * 2 + x * x) % mod
        return ans

Continue Practicing

#2597 the number of beautiful subsets #3250 find the count of monotonic pairs i #3251 find the count of monotonic pairs ii