{x}
blog image

Sum of Total Strength of Wizards

As the ruler of a kingdom, you have an army of wizards at your command.

You are given a 0-indexed integer array strength, where strength[i] denotes the strength of the ith wizard. For a contiguous group of wizards (i.e. the wizards' strengths form a subarray of strength), the total strength is defined as the product of the following two values:

  • The strength of the weakest wizard in the group.
  • The total of all the individual strengths of the wizards in the group.

Return the sum of the total strengths of all contiguous groups of wizards. Since the answer may be very large, return it modulo 109 + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

 

Example 1:

Input: strength = [1,3,1,2]
Output: 44
Explanation: 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
Explanation: 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 Explanation

This problem asks to calculate the sum of total strengths of all contiguous groups of wizards. The total strength of a group is the product of the minimum strength in the group and the sum of all strengths in the group. A brute-force approach would have O(n^3) time complexity, which is inefficient for large inputs. The optimal solution utilizes a monotonic stack and prefix sums to achieve O(n) time complexity.

Approach

  1. Monotonic Stack for Range Queries: We use two monotonic stacks to efficiently find the leftmost and rightmost indices of the subarray where a given wizard is the weakest wizard. The first stack maintains increasing strengths, and when we encounter a smaller strength, it means that all the elements previously pushed into the stack are larger and thus have their right boundaries set at the current index. The second stack performs the same operation in reverse to find the left boundaries.

  2. Prefix Sums: To calculate the sum of strengths within a given range quickly, we use prefix sums. The s array stores the prefix sum of the strength array and the ss array stores the prefix sum of the prefix sums. This allows us to compute the sum of strengths in a subarray in O(1) time.

  3. Calculate Total Strength: We iterate through the strength array. For each wizard, we know the left and right bounds of the subarray where the wizard is the minimum. Using the prefix sum arrays, we efficiently compute the sum of strengths in this subarray. The formula to calculate the sum using prefix sums for a subarray [l, r] is ss[r+1] - ss[l].

  4. Modulo Operation: We use the modulo operator % mod throughout the calculation to prevent integer overflow.

Time and Space Complexity

  • Time Complexity: O(n), where n is the length of the strength array. We iterate through the array three times: once for each monotonic stack and once for the final calculation. Each operation within these iterations takes constant time.
  • Space Complexity: O(n) to store the left and right boundaries, prefix sums, and stacks.

Code Explanation (Python)

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        n = len(strength)
        left = [-1] * n  # Stores the index of the leftmost wizard weaker than the current wizard
        right = [n] * n  # Stores the index of the rightmost wizard weaker than the current wizard
        stk = [] #Monotonic stack 
        for i, v in enumerate(strength):
            while stk and strength[stk[-1]] >= v:  #Maintain increasing order
                stk.pop()
            if stk:
                left[i] = stk[-1]  #Set left boundary
            stk.append(i)  #Push index into stack
 
        stk = [] #Clear stack for the reverse operation
        for i in range(n - 1, -1, -1):
            while stk and strength[stk[-1]] > strength[i]: #Maintain increasing order
                stk.pop()
            if stk:
                right[i] = stk[-1]  #Set right boundary
            stk.append(i)
 
        ss = list(accumulate(list(accumulate(strength, initial=0)), initial=0)) #Double prefix sum
        mod = int(1e9) + 7
        ans = 0
        for i, v in enumerate(strength): #Iterate and calculate the total strength
            l, r = left[i] + 1, right[i] - 1
            a = (ss[r + 2] - ss[i + 1]) * (i - l + 1) #Sum of strengths for the subarray where current wizard is minimum * length of the subarray to the right
            b = (ss[i + 1] - ss[l]) * (r - i + 1) #Sum of strengths for the subarray where current wizard is minimum * length of the subarray to the left
            ans = (ans + (a - b) * v) % mod #Add the total strength to the final result
        return ans

The code in other languages (Java, C++, Go) follows the same logic and utilizes the same data structures and algorithms. The only differences are in syntax and standard library functions.