LeetCode 2681 - Power of Heroes

The problem asks us to compute the total "power" across every possible non-empty subset of heroes. For any selected group of heroes, its power is defined as: We are given an array nums, where each value represents the strength of one hero.

leetcodehardarraymathdynamic-programmingsortingprefix-sum

LeetCode Problem 2681

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Sorting, Prefix Sum

Solution

Problem Understanding

The problem asks us to compute the total "power" across every possible non-empty subset of heroes.

For any selected group of heroes, its power is defined as:

$$(\text{maximum strength in the group})^2 \times (\text{minimum strength in the group})$$

We are given an array nums, where each value represents the strength of one hero. We must consider every non-empty subset of this array, compute the power of that subset, and sum all such powers together.

The final answer can become extremely large because there are up to:

$$2^n - 1$$

possible non-empty subsets. Since n can be as large as 10^5, brute force enumeration is impossible. Therefore, the answer must be returned modulo:

$$10^9 + 7$$

The constraints are the key indicator that an optimized combinational or dynamic programming approach is required:

  • nums.length <= 10^5 means any exponential or quadratic subset processing is infeasible.
  • nums[i] <= 10^9 means integer overflow must be handled carefully.
  • We need something close to O(n log n) or O(n).

Several edge cases are important:

  • Arrays with all identical values, because many subsets produce the same minimum and maximum.
  • Arrays with only one element, where the subset consists solely of that hero.
  • Strictly increasing arrays, where every newly added value changes the maximum.
  • Large values close to 10^9, which require modular arithmetic throughout the computation.

The biggest challenge is avoiding explicit subset enumeration while still correctly accounting for every subset contribution.

Approaches

Brute Force Approach

The most direct solution is to generate every non-empty subset of nums.

For each subset:

  1. Find the minimum value.
  2. Find the maximum value.
  3. Compute:

$$\text{max}^2 \times \text{min}$$

  1. Add it to the answer.

This approach is correct because it literally follows the problem definition.

However, the number of subsets is exponential:

$$2^n - 1$$

Even for n = 30, this becomes impractical. With n = 10^5, brute force is completely impossible.

Additionally, computing minimum and maximum for every subset adds further overhead.

Key Insight for the Optimal Solution

The crucial observation is that we can sort the array and count contributions systematically instead of generating subsets explicitly.

Suppose the array is sorted:

$$a_0 \le a_1 \le a_2 \le \dots \le a_{n-1}$$

Now consider some value a[i] acting as the maximum element of a subset.

If a[i] is the maximum, then every chosen element must come from indices < i.

The subset power becomes:

$$a[i]^2 \times (\text{minimum chosen element})$$

So the real challenge becomes:

For every a[i], efficiently compute the sum of all possible minimum values among subsets ending at i.

This leads to a dynamic accumulation pattern.

When processing values from left to right:

  • Each previous value can either appear or not appear in a subset.
  • Every time we add a new number, previous contributions double because every existing subset can either include or exclude the new intermediate elements.

This creates a prefix recurrence:

$$\text{prefix} = 2 \times \text{prefix} + a[i]$$

The prefix variable efficiently tracks the sum of minimum contributions across all subsets where the current number is the maximum.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n \cdot n) O(n) Enumerates all subsets and computes min/max directly
Optimal O(n log n) O(1) excluding sorting Uses sorting and contribution counting

Algorithm Walkthrough

  1. Sort the array in non-decreasing order.

Sorting allows us to process elements from smallest to largest. Once sorted, when we process nums[i], we know it is the maximum element of every subset considered at that step. 2. Initialize three variables:

  • MOD = 10^9 + 7
  • answer = 0
  • prefix = 0

The prefix variable stores the cumulative contribution of all possible subset minimums formed from previously processed elements. 3. Iterate through the sorted array.

Let the current value be x. 4. Compute the contribution where x is the maximum.

Every subset ending at x contributes:

$$x^2 \times (\text{sum of all possible minimums})$$

The total minimum contribution equals:

$$x + \text{prefix}$$

The standalone x corresponds to the subset containing only x.

So the contribution becomes:

$$x^2 \times (x + \text{prefix})$$

Add this to the answer.

  1. Update the prefix contribution.

After processing x, future elements may use it as a minimum.

Every previous subset can either include or exclude x, so previous contributions double.

Additionally, x itself forms a new singleton subset.

Therefore:

$$\text{prefix} = 2 \times \text{prefix} + x$$

  1. Apply modulo operations after every arithmetic update.

This prevents overflow and satisfies the problem requirement. 2. Return the final answer.

Why it works

After sorting, every subset has a uniquely determined maximum element, namely the largest selected value.

When processing nums[i], all valid subsets where nums[i] is maximum are formed by combining it with arbitrary subsets of previous elements.

The prefix variable compactly represents the total contribution of all possible minimum values from those subsets. Because each new element doubles the number of ways previous minimums can appear, the recurrence naturally emerges.

Thus, every subset is counted exactly once, under its maximum element.

Python Solution

from typing import List

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        MOD = 10**9 + 7

        nums.sort()

        answer = 0
        prefix = 0

        for x in nums:
            contribution = (x * x) % MOD
            contribution = (contribution * (x + prefix)) % MOD

            answer = (answer + contribution) % MOD

            prefix = (2 * prefix + x) % MOD

        return answer

The implementation begins by sorting the array so that each element can be treated as the maximum of all subsets processed at that iteration.

The variable prefix stores the cumulative minimum contribution from all subsets formed using previously processed elements.

For each value x:

  • x * x computes the square of the maximum.
  • (x + prefix) represents the total minimum contribution across all subsets where x is maximum.
  • Their product gives the total contribution of all such subsets.

After adding the contribution into the final answer, the prefix recurrence:

prefix = 2 * prefix + x

updates the running subset minimum total for future iterations.

Modulo arithmetic is applied throughout to avoid overflow and comply with the problem constraints.

Go Solution

package main

import (
	"sort"
)

func sumOfPower(nums []int) int {
	const MOD int64 = 1_000_000_007

	sort.Ints(nums)

	var answer int64 = 0
	var prefix int64 = 0

	for _, value := range nums {
		x := int64(value)

		contribution := (x * x) % MOD
		contribution = (contribution * ((x + prefix) % MOD)) % MOD

		answer = (answer + contribution) % MOD

		prefix = (2*prefix + x) % MOD
	}

	return int(answer)
}

The Go implementation follows the exact same mathematical logic as the Python version.

A few Go-specific details are important:

  • int64 is used for all arithmetic because intermediate values can exceed 32-bit integer limits.
  • sort.Ints(nums) sorts the slice in-place.
  • Constants are explicitly typed to avoid overflow issues during multiplication.
  • The final result is converted back to int because the LeetCode signature requires it.

Worked Examples

Example 1

Input:

nums = [2,1,4]

After sorting:

[1,2,4]
Step x prefix before x² x + prefix Contribution answer prefix after
1 1 0 1 1 1 1 1
2 2 1 4 3 12 13 4
3 4 4 16 8 128 141 12

Final answer:

141

Example 2

Input:

nums = [1,1,1]

After sorting:

[1,1,1]
Step x prefix before x² x + prefix Contribution answer prefix after
1 1 0 1 1 1 1 1
2 1 1 1 2 2 3 3
3 1 3 1 4 4 7 7

Final answer:

7

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates the runtime
Space O(1) excluding sorting Only a few variables are used

The loop itself is linear, processing each element exactly once.

The sorting step costs:

$$O(n \log n)$$

which becomes the dominant complexity.

No auxiliary data structures proportional to input size are needed, so the extra space usage is constant aside from the sorting implementation.

Test Cases

from typing import List

class Solution:
    def sumOfPower(self, nums: List[int]) -> int:
        MOD = 10**9 + 7

        nums.sort()

        answer = 0
        prefix = 0

        for x in nums:
            contribution = (x * x) % MOD
            contribution = (contribution * (x + prefix)) % MOD

            answer = (answer + contribution) % MOD

            prefix = (2 * prefix + x) % MOD

        return answer

sol = Solution()

assert sol.sumOfPower([2, 1, 4]) == 141  # provided example
assert sol.sumOfPower([1, 1, 1]) == 7  # all identical values
assert sol.sumOfPower([5]) == 125  # single element
assert sol.sumOfPower([1, 2]) == 13  # small increasing array
assert sol.sumOfPower([2, 2]) == 24  # duplicate values
assert sol.sumOfPower([1, 2, 3]) == 76  # multiple subset combinations
assert sol.sumOfPower([10**9]) == 999999664  # large value modulo handling
assert sol.sumOfPower([3, 1, 2]) == 76  # unsorted input
assert sol.sumOfPower([1, 3, 5, 7]) == 4212  # larger increasing sequence
assert sol.sumOfPower([100000, 100000]) == 999300987  # large duplicates

Test Summary

Test Why
[2,1,4] Validates the official example
[1,1,1] Tests repeated identical values
[5] Tests single-element input
[1,2] Smallest non-trivial subset generation
[2,2] Ensures duplicates are counted correctly
[1,2,3] Verifies multiple subset interactions
[10^9] Confirms modulo arithmetic correctness
[3,1,2] Ensures sorting is handled properly
[1,3,5,7] Tests larger accumulation patterns
[100000,100000] Stress test for large duplicate values

Edge Cases

One important edge case is a single-element array. In this situation, there is only one subset, the element itself. The minimum and maximum are equal, so the power becomes:

$$x^2 \times x = x^3$$

The implementation handles this naturally because prefix starts at zero, making the contribution:

$$x^2 \times (x + 0)$$

Another important edge case involves duplicate values. When many elements are equal, multiple subsets share the same minimum and maximum. A naive counting strategy can accidentally overcount or undercount these combinations. Because the algorithm processes subsets through contribution accumulation rather than explicit uniqueness logic, duplicates are handled correctly without any special cases.

A third critical edge case is very large values near 10^9. Squaring these numbers exceeds 32-bit integer limits. Both implementations use modular arithmetic throughout computation, and the Go version explicitly uses int64 to avoid overflow before taking modulo reductions.

Finally, unsorted input is another common source of bugs. The entire contribution logic depends on processing values in non-decreasing order so that the current element is guaranteed to be the subset maximum. The algorithm sorts the array immediately, ensuring correctness regardless of input order.