2281. Sum of Total Strength of Wizards LeetCode Solution
In this guide, you will get 2281. Sum of Total Strength of Wizards LeetCode Solution with the best time and space complexity. The solution to Sum of Total Strength of Wizards problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Sum of Total Strength of Wizards solution in C++
- Sum of Total Strength of Wizards solution in Java
- Sum of Total Strength of Wizards solution in Python
- Additional Resources
Problem Statement of 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
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(n)
2281. Sum of Total Strength of Wizards LeetCode Solution in C++
class Solution {
public:
int totalStrength(vector<int>& strength) {
constexpr int kMod = 1'000'000'007;
const int n = strength.size();
vector<long> prefix(n);
vector<long> prefixOfPrefix(n + 1);
// left[i] := the next index on the left (if any) s.t.
// nums[left[i]] <= nums[i]
vector<int> left(n, -1);
// right[i] := the next index on the right (if any) s.t.
// nums[right[i]] < nums[i]
vector<int> right(n, n);
stack<int> stack;
for (int i = 0; i < n; ++i)
prefix[i] = i == 0 ? strength[0] : (strength[i] + prefix[i - 1]) % kMod;
for (int i = 0; i < n; ++i)
prefixOfPrefix[i + 1] = (prefixOfPrefix[i] + prefix[i]) % kMod;
for (int i = n - 1; i >= 0; --i) {
while (!stack.empty() && strength[stack.top()] >= strength[i])
left[stack.top()] = i, stack.pop();
stack.push(i);
}
stack = std::stack<int>();
for (int i = 0; i < n; ++i) {
while (!stack.empty() && strength[stack.top()] > strength[i])
right[stack.top()] = i, stack.pop();
stack.push(i);
}
long ans = 0;
// For each strength[i] as minimum, calculate sum.
for (int i = 0; i < n; ++i) {
const int l = left[i];
const int r = right[i];
const long leftSum = prefixOfPrefix[i] - prefixOfPrefix[max(0, l)];
const long rightSum = prefixOfPrefix[r] - prefixOfPrefix[i];
const int leftLen = i - l;
const int rightLen = r - i;
ans += strength[i] *
(rightSum * leftLen % kMod - leftSum * rightLen % kMod + kMod) %
kMod;
ans %= kMod;
}
return ans;
}
};
/* code provided by PROGIEZ */2281. Sum of Total Strength of Wizards LeetCode Solution in Java
class Solution {
public int totalStrength(int[] strength) {
final int kMod = 1_000_000_007;
final int n = strength.length;
long[] prefix = new long[n];
long[] prefixOfPrefix = new long[n + 1];
// left[i] := the next index on the left (if any)
// s.t. nums[left[i]] <= nums[i]
int[] left = new int[n];
Arrays.fill(left, -1);
// right[i] := the next index on the right (if any)
// s.t. nums[right[i]] < nums[i]
int[] right = new int[n];
Arrays.fill(right, n);
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; ++i)
prefix[i] = i == 0 ? strength[0] : (strength[i] + prefix[i - 1]) % kMod;
for (int i = 0; i < n; ++i)
prefixOfPrefix[i + 1] = (prefixOfPrefix[i] + prefix[i]) % kMod;
for (int i = n - 1; i >= 0; --i) {
while (!stack.isEmpty() && strength[stack.peek()] >= strength[i])
left[stack.pop()] = i;
stack.push(i);
}
stack.clear();
for (int i = 0; i < n; ++i) {
while (!stack.isEmpty() && strength[stack.peek()] > strength[i])
right[stack.pop()] = i;
stack.push(i);
}
long ans = 0;
// For each strength[i] as minimum, calculate sum.
for (int i = 0; i < n; ++i) {
final int l = left[i];
final int r = right[i];
final long leftSum = prefixOfPrefix[i] - prefixOfPrefix[Math.max(0, l)];
final long rightSum = prefixOfPrefix[r] - prefixOfPrefix[i];
final int leftLen = i - l;
final int rightLen = r - i;
ans += strength[i] * (rightSum * leftLen % kMod - leftSum * rightLen % kMod + kMod) % kMod;
ans %= kMod;
}
return (int) ans;
}
}
// code provided by PROGIEZ2281. Sum of Total Strength of Wizards LeetCode Solution in Python
class Solution:
def totalStrength(self, strength: list[int]) -> int:
kMod = 1_000_000_007
n = len(strength)
# left[i] := the next index on the left (if any)
# s.t. nums[left[i]] <= nums[i]
left = [-1] * n
# right[i] := the next index on the right (if any)
# s.t. nums[right[i]] < nums[i]
right = [n] * n
stack = []
for i in reversed(range(n)):
while stack and strength[stack[-1]] >= strength[i]:
left[stack.pop()] = i
stack.append(i)
stack = []
for i in range(n):
while stack and strength[stack[-1]] > strength[i]:
right[stack.pop()] = i
stack.append(i)
ans = 0
prefixOfPrefix = list(itertools.accumulate(
itertools.accumulate(strength), initial=0))
# For each strength[i] as the minimum, calculate sum.
for i, (l, r) in enumerate(zip(left, right)):
leftSum = prefixOfPrefix[i] - prefixOfPrefix[max(0, l)]
rightSum = prefixOfPrefix[r] - prefixOfPrefix[i]
leftLen = i - l
rightLen = r - i
ans += strength[i] * (rightSum * leftLen - leftSum * rightLen) % kMod
return ans % kMod
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.