#2281

Hard

auto_awesomeStack-based state management

LeetCode Problem Workspace

Sum of Total Strength of Wizards

The Sum of Total Strength of Wizards problem asks for the sum of the total strengths of all contiguous subarrays of wizard strengths.

array stack monotonic stack prefix sum

Problem Statement

You are given an array of wizard strengths, where each element represents the strength of a specific wizard. A contiguous group of wizards is a subarray of the original array. For each subarray, its total strength is determined by multiplying the minimum strength within the subarray with the sum of all elements in that subarray.

The goal is to calculate the sum of total strengths for all contiguous subarrays. Since the result may be large, return it modulo 10^9 + 7. Your approach must account for all possible subarrays and avoid inefficient brute-force methods, especially as the input size can be large.

Examples

Example 1

Input: strength = [1,3,1,2]

Output: 44

The following are all the contiguous groups of wizards:

[1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
[3] from [1,3,1,2] has a total strength of min([3]) * sum([3]) = 3 * 3 = 9
[1] from [1,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
[2] from [1,3,1,2] has a total strength of min([2]) * sum([2]) = 2 * 2 = 4
[1,3] from [1,3,1,2] has a total strength of min([1,3]) * sum([1,3]) = 1 * 4 = 4
[3,1] from [1,3,1,2] has a total strength of min([3,1]) * sum([3,1]) = 1 * 4 = 4
[1,2] from [1,3,1,2] has a total strength of min([1,2]) * sum([1,2]) = 1 * 3 = 3
[1,3,1] from [1,3,1,2] has a total strength of min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
[3,1,2] from [1,3,1,2] has a total strength of min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
[1,3,1,2] from [1,3,1,2] has a total strength of min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7 The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.

Example 2

Input: strength = [5,4,6]

Output: 213

The following are all the contiguous groups of wizards:

[5] from [5,4,6] has a total strength of min([5]) * sum([5]) = 5 * 5 = 25
[4] from [5,4,6] has a total strength of min([4]) * sum([4]) = 4 * 4 = 16
[6] from [5,4,6] has a total strength of min([6]) * sum([6]) = 6 * 6 = 36
[5,4] from [5,4,6] has a total strength of min([5,4]) * sum([5,4]) = 4 * 9 = 36
[4,6] from [5,4,6] has a total strength of min([4,6]) * sum([4,6]) = 4 * 10 = 40
[5,4,6] from [5,4,6] has a total strength of min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60 The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.

Constraints

1 <= strength.length <= 105
1 <= strength[i] <= 109

Solution Approach

Efficient Calculation with Monotonic Stack

To optimize the solution, use a monotonic stack to track the minimum strength in each subarray. This allows you to efficiently calculate the contribution of each wizard to the total sum without iterating over all possible subarrays directly.

Prefix Sum for Fast Summation

Using a prefix sum array, precompute the cumulative sum of strengths up to each index. This helps in quickly calculating the sum of any subarray, making the algorithm more efficient when combined with the monotonic stack approach.

Modulo Arithmetic for Large Numbers

Since the result can be very large, always apply modulo 10^9 + 7 during the summation process to prevent overflow and ensure the answer fits within the required limits.

Complexity Analysis

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

The time complexity depends on the final approach, typically O(n) for stack-based methods when combined with prefix sums, and the space complexity is O(n) due to the need for the stack and prefix sum array.

What Interviewers Usually Probe

Ability to manage large inputs efficiently without brute force methods.
Understanding of monotonic stacks and their application in reducing time complexity.
Skill in handling large numbers and applying modulo operations to ensure correctness.

Common Pitfalls or Variants

Common pitfalls

Not using a monotonic stack to reduce redundant calculations for subarrays.
Forgetting to apply modulo 10^9 + 7 during the summation process, causing overflow or incorrect results.
Relying on brute-force methods to calculate all subarrays, which can be too slow for large inputs.

Follow-up variants

Optimizing for larger inputs by reducing time complexity with better state management.
Adjusting the solution to handle varying constraints, such as different ranges for wizard strengths.
Exploring variations of the problem where other properties, like sum or product, need to be calculated instead of total strength.

FAQ

How do I optimize my solution for the Sum of Total Strength of Wizards problem?

The optimal solution involves using a monotonic stack to manage subarray minimums and prefix sums to quickly calculate subarray sums.

What are the key trade-offs when solving this problem?

The main trade-off is between time complexity and space usage, where more efficient state management with a monotonic stack reduces time complexity but requires extra space.

What does the modulo 10^9 + 7 mean in this problem?

Modulo 10^9 + 7 is used to ensure that the sum of the strengths does not exceed the integer limits and stays within the problem's constraints.

How does the monotonic stack help in this problem?

The monotonic stack helps track the minimum strength in each subarray, allowing for efficient calculation of total strengths without checking each subarray individually.

What is the significance of prefix sums in this problem?

Prefix sums allow you to quickly calculate the sum of any subarray, improving the time complexity by eliminating the need to sum elements repeatedly.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        n = len(strength)
        left = [-1] * n
        right = [n] * n
        stk = []
        for i, v in enumerate(strength):
            while stk and strength[stk[-1]] >= v:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and strength[stk[-1]] > strength[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)

        ss = list(accumulate(list(accumulate(strength, initial=0)), initial=0))
        mod = int(1e9) + 7
        ans = 0
        for i, v in enumerate(strength):
            l, r = left[i] + 1, right[i] - 1
            a = (ss[r + 2] - ss[i + 1]) * (i - l + 1)
            b = (ss[i + 1] - ss[l]) * (r - i + 1)
            ans = (ans + (a - b) * v) % mod
        return ans

Continue Practicing

#1856 maximum subarray min product #2289 steps to make array non decreasing #2334 subarray with elements greater than varying threshold