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:
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 <= 1051 <= strength[i] <= 109This approach leverages a monotonic stack to determine the contribution of each element when it is the minimum in its subarrays. Using this, we can efficiently calculate the total subarray strength including this minimum. Along with this, prefix sums help in computing the sum of elements in a range efficiently.
In this solution, we calculate the prefix sums for the strength array to efficiently get subarray sums. The monotonic stack helps track the previous and next smaller element positions for each element. We calculate each element's contribution to the total strength by considering it as the minimal value for contiguous subarrays and using the previously calculated ranges and prefix sums.
JavaScript
Time Complexity: O(n), where n is the length of the strength array. Space Complexity: O(n) due to the prefix sums and stack usage.
This approach directly calculates each subarray's total strength using nested loops with some optimizations to reduce redundant calculations, like avoiding repeated strength sums by leveraging previous computations.
This C++ solution applies a similar logic as the previous approach with the computational optimization related to prefix sums and using indices to denote the boundaries of subarrays. It uses loops to push and pop indices on and off the 'stack' appropriately while checking for conditions on strength values.
C#
Time Complexity: O(n), since each element is pushed and popped from the stack once. Space Complexity: O(n), due to the prefix arrays and auxiliary space used for indices.
| Approach | Complexity |
|---|---|
| Monotonic Stack with Prefix Sum | Time Complexity: O(n), where n is the length of the strength array. Space Complexity: O(n) due to the prefix sums and stack usage. |
| Direct Calculation with Optimizations | Time Complexity: O(n), since each element is pushed and popped from the stack once. Space Complexity: O(n), due to the prefix arrays and auxiliary space used for indices. |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,241 views views
Watch 9 more video solutions →Practice Sum of Total Strength of Wizards with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor