Sum of Total Strength of Wizards - Video Solutions
Sum of Total Strength of Wizards | Leetcode 2281 | Monotonic Stacks Prefix Sum | Contest 294 🔥🔥
Sum of Total Strength of Wizards - Video Solution
Watch 9 video solutions for Sum of Total Strength of Wizards, a hard level problem involving Array, Stack, Monotonic Stack. This walkthrough by Coding Decoded has 13,137 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 1051 <= strength[i] <= 109
Approach Overview
Problem Overview: You are given an array where strength[i] represents the strength of the i-th wizard. For every subarray, the total strength equals the minimum value in the subarray multiplied by the sum of that subarray. The task is to compute the sum of this value across all possible subarrays efficiently.
Approach 1: Direct Calculation with Prefix Sum Optimization (O(n²) time, O(n) space)
The straightforward idea is to enumerate every subarray and compute two values: the minimum element and the sum of the subarray. A running prefix sum allows you to compute subarray sums in O(1) instead of recalculating them each time. While iterating with two pointers (i as start and j as end), maintain the current minimum value and multiply it by the subarray sum obtained from the prefix array. This reduces repeated work but still requires examining all O(n²) subarrays.
This approach is useful for understanding the formula and validating smaller inputs. However, it does not scale to the largest constraints because the nested iteration quickly becomes too slow.
Approach 2: Monotonic Stack with Prefix Sums (O(n) time, O(n) space)
The optimal solution reframes the problem: instead of enumerating subarrays, determine how many subarrays treat each element as the minimum. A monotonic stack helps find the previous and next smaller elements for every index. These boundaries define the range where the current value remains the minimum.
Once the span is known, the remaining task is to efficiently compute the contribution of all subarray sums within that span. This is where prefix sums and prefix-of-prefix sums come in. They allow fast calculation of cumulative subarray sums on the left and right sides of the current element. By combining these values, you can compute the total contribution of each wizard in constant time.
The algorithm iterates through the array once to maintain the stack and once more to calculate contributions. Each index enters and leaves the stack exactly once, giving linear complexity. The technique combines ideas from array processing, range contribution counting, and prefix sum mathematics.
Recommended for interviews: Interviewers typically expect the monotonic stack approach. Demonstrating the brute-force idea shows you understand the definition of the problem, but the optimized solution proves you can transform a quadratic enumeration into a linear contribution-based calculation.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Calculation with Prefix Sum | O(n²) | O(n) | Good for understanding the problem and validating logic on small inputs |
| Monotonic Stack with Prefix Sums | O(n) | O(n) | Optimal solution for large constraints and typical interview expectations |