Problem Description

You are given a 0-indexed integer array nums representing the strength of some heroes. Your task is to find the sum of the power of all possible non-empty groups of heroes.

The power of a group of heroes is calculated using a specific formula:

• For a group with heroes at indices i₀, i₁, ..., iₖ, the power is defined as: max(nums[i₀], nums[i₁], ..., nums[iₖ])² × min(nums[i₀], nums[i₁], ..., nums[iₖ])
• In other words, you take the maximum strength value in the group, square it, and multiply by the minimum strength value in the group

You need to:

1. Consider all possible non-empty subsets of the array (not necessarily contiguous)
2. Calculate the power for each subset using the formula above
3. Sum up all these power values
4. Return the sum modulo 10⁹ + 7 (since the result can be very large)

For example, if you have a group with strengths [2, 3, 5], the power would be: 5² × 2 = 25 × 2 = 50 (where 5 is the maximum and 2 is the minimum).

The challenge involves efficiently computing this sum across all possible subsets, as the naive approach of generating all subsets would be too slow for large arrays.

Intuition

The key insight is that since we're dealing with maximum and minimum values of subsets, the order of elements in the original array doesn't matter - we can sort it first to make our calculations easier.

Once sorted, let's think about how to count contributions efficiently. For any subset, the power formula is max² × min. If we fix the minimum element, we need to consider all possible subsets that include this minimum and potentially larger elements.

Consider a sorted array [a₁, a₂, a₃, ..., aₙ]. If we fix aᵢ as the minimum element of a subset, then:

• The subset can include aᵢ itself (power = aᵢ² × aᵢ = aᵢ³)
• The subset can include aᵢ and aᵢ₊₁ (power = aᵢ₊₁² × aᵢ)
• The subset can include aᵢ and aᵢ₊₂ (power = aᵢ₊₂² × aᵢ)
• And so on...

But wait - we can also have subsets like {aᵢ, aᵢ₊₁, aᵢ₊₂} where the maximum is aᵢ₊₂. How many such subsets are there? For each element aⱼ where j > i, it can be the maximum element in 2^(j-i-1) different subsets (we can choose to include or exclude each element between i and j).

This means when aᵢ is the minimum, the total contribution is: aᵢ × (aᵢ² + aᵢ₊₁² + 2×aᵢ₊₂² + 4×aᵢ₊₃² + ... + 2^(n-i-1)×aₙ²)

The coefficient doubles each time because each subsequent element can be the maximum in twice as many subsets as the previous one.

To compute this efficiently, we can process the array from right to left, maintaining a running sum p that represents the weighted sum of squares. For each element, we:

1. Add its contribution when it's the minimum (aᵢ × p)
2. Add its contribution when it's both min and max (aᵢ³)
3. Update p for the next iteration: p = 2×p + aᵢ²

This way, we avoid recalculating the weighted sums repeatedly and achieve a linear time solution after sorting.

Learn more about Math, Dynamic Programming, Prefix Sum and Sorting patterns.

Solution Approach

Based on our intuition, let's implement the solution step by step:

Step 1: Sort the array Since the order doesn't affect the result and we need to work with minimum and maximum values, we first sort the array in ascending order.

Step 2: Initialize variables

• mod = 10^9 + 7 for the modulo operation
• ans = 0 to accumulate the total power sum
• p = 0 to maintain the weighted sum of squares for efficient calculation

Step 3: Process elements from right to left We iterate through the sorted array in reverse order (from largest to smallest). For each element x:

1. Add the contribution when x is the minimum element:

   • When x is both min and max (single element subset): x³
   • This is computed as: ans = (ans + x² × x) % mod

2. Add the contribution from larger elements:

   • When x is minimum and there are larger elements as maximum: x × p
   • This is computed as: ans = (ans + x × p) % mod

3. Update p for the next iteration:

   • The formula p = 2×p + x² maintains the weighted sum
   • Each existing term in p gets doubled (representing the doubling of subset counts)
   • We add x² for the current element

Why this works: When we process element aᵢ as the minimum:

• The value p already contains the weighted sum: aᵢ₊₁² + 2×aᵢ₊₂² + 4×aᵢ₊₃² + ...
• Multiplying aᵢ × p gives us all contributions where aᵢ is minimum and some larger element is maximum
• Adding aᵢ³ accounts for the subset containing only aᵢ
• Updating p = 2×p + aᵢ² prepares it for the next element:
  • The 2×p part doubles all existing coefficients
  • Adding aᵢ² includes the current element for future calculations

Time Complexity: O(n log n) due to sorting, where n is the length of the array Space Complexity: O(1) excluding the space used for sorting

The modulo operation is applied at each step to prevent integer overflow, ensuring the result stays within bounds.

Example Walkthrough

Let's walk through the solution with a small example: nums = [1, 2, 3]

Step 1: Sort the array Array is already sorted: [1, 2, 3]

Step 2: Initialize variables

• mod = 10^9 + 7
• ans = 0 (total power sum)
• p = 0 (weighted sum of squares)

Step 3: Process from right to left

Iteration 1: Process element 3 (index 2)

• Current element x = 3
• Add contribution when 3 is minimum (only subset {3}):
  • ans = ans + 3² × 3 = 0 + 27 = 27
• Add contribution from larger elements (none exist):
  • ans = ans + 3 × p = 27 + 3 × 0 = 27
• Update p for next iteration:
  • p = 2 × p + 3² = 2 × 0 + 9 = 9

Iteration 2: Process element 2 (index 1)

• Current element x = 2
• Add contribution when 2 is minimum:
  • Single element subset {2}: 2³ = 8
  • ans = ans + 2² × 2 = 27 + 8 = 35
• Add contribution from larger elements:
  • Subset {2, 3} has power 3² × 2 = 18
  • This is captured by: ans = ans + 2 × p = 35 + 2 × 9 = 53
• Update p for next iteration:
  • p = 2 × p + 2² = 2 × 9 + 4 = 22

Iteration 3: Process element 1 (index 0)

• Current element x = 1
• Add contribution when 1 is minimum:
  • Single element subset {1}: 1³ = 1
  • ans = ans + 1² × 1 = 53 + 1 = 54
• Add contribution from larger elements:
  • Subset {1, 2}: power = 2² × 1 = 4
  • Subset {1, 3}: power = 3² × 1 = 9
  • Subset {1, 2, 3}: power = 3² × 1 = 9
  • Total from p: 4 + 9 + 9 = 22
  • ans = ans + 1 × p = 54 + 1 × 22 = 76

Final answer: 76

Let's verify by listing all subsets and their powers:

• {1}: 1² × 1 = 1
• {2}: 2² × 2 = 8
• {3}: 3² × 3 = 27
• {1, 2}: 2² × 1 = 4
• {1, 3}: 3² × 1 = 9
• {2, 3}: 3² × 2 = 18
• {1, 2, 3}: 3² × 1 = 9

Total: 1 + 8 + 27 + 4 + 9 + 18 + 9 = 76 ✓

The key insight is how p accumulates the weighted sum of squares. When processing element 2, p = 9 represents that element 3 can be the maximum in exactly one subset where 2 is minimum. When processing element 1, p = 22 represents:

• Element 2 can be max in 1 subset: 2² × 1 = 4
• Element 3 can be max in 2 subsets ({1,3} and {1,2,3}): 2 × 3² × 1 = 18
• Total: 4 + 18 = 22

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array. This is dominated by the sorting operation nums.sort(), which takes O(n × log n) time. The subsequent loop iterates through the array once in O(n) time, performing constant-time operations within each iteration.

The space complexity is O(log n). While the code doesn't explicitly create additional data structures proportional to the input size, the sorting algorithm (typically Timsort in Python) requires O(log n) space for its recursive call stack. The variables ans, p, and mod use only O(1) additional space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow in Intermediate Calculations

The most critical pitfall in this problem is handling integer overflow during intermediate calculations, particularly when computing current_num * current_num * current_num or current_num * prefix_contribution.

The Problem: Even though we're using modulo operations, the intermediate multiplication can overflow before the modulo is applied. For example:

• If current_num = 10^5, then current_num^3 = 10^15, which exceeds the typical integer limit
• The expression (current_num * current_num % MOD) * current_num might still overflow if not handled carefully

Solution: Apply modulo operations more frequently to keep intermediate values small:

# Instead of:
total_sum = (total_sum + (current_num * current_num % MOD) * current_num) % MOD

# Use:
squared = (current_num * current_num) % MOD
cubed = (squared * current_num) % MOD
total_sum = (total_sum + cubed) % MOD

2. Incorrect Order of Operations with Modulo

Another common mistake is applying modulo operations in the wrong order or missing them in certain places.

The Problem: Forgetting to apply modulo to intermediate results can lead to overflow, while applying it incorrectly can produce wrong results.

Solution: Ensure modulo is applied consistently after each arithmetic operation:

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        nums.sort()
      
        total_sum = 0
        prefix_contribution = 0
      
        for current_num in reversed(nums):
            # Break down calculations to avoid overflow
            curr_squared = (current_num * current_num) % MOD
            curr_cubed = (curr_squared * current_num) % MOD
          
            # Add current element's contribution
            total_sum = (total_sum + curr_cubed) % MOD
          
            # Add prefix contribution
            contribution = (current_num * prefix_contribution) % MOD
            total_sum = (total_sum + contribution) % MOD
          
            # Update prefix for next iteration
            prefix_contribution = (2 * prefix_contribution + curr_squared) % MOD
      
        return total_sum

3. Misunderstanding the Prefix Contribution Update

The formula prefix_contribution = (2 * prefix_contribution + current_num^2) is crucial but easy to get wrong.

The Problem:

• Forgetting to multiply by 2 (which represents the doubling of subset counts)
• Adding current_num instead of current_num^2
• Updating prefix_contribution before using it in calculations

Solution: Always update prefix_contribution after using it in the current iteration's calculations, and ensure you're adding the square of the current number.

4. Processing Order Confusion

Processing the array in the wrong direction can lead to incorrect results.

The Problem: The algorithm relies on processing elements from largest to smallest (after sorting) to correctly accumulate the prefix contributions.

Solution: Always sort first, then process in reverse order using reversed(nums) or iterate with reverse indices.