Sum of Total Strength of Wizards — Problem & Solution
Sum of Total Strength of Wizards solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Sum of Total Strength of Wizards is a hard coding problem on arrays, prefix sum and stack, asked in Amazon, Google and Uber interviews.
- Difficulty: Hard
- Topics: Arrays, Prefix Sum, Stack, Monotonic Stack
- Asked at: Amazon, Google, Uber
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A row of wizards stands in line; strength[i] is the strength of the i-th wizard. For any contiguous group of wizards (a non-empty subarray), its total strength is the strength of its weakest wizard multiplied by the sum of all strengths in the group.
Return the sum of the total strengths of all contiguous groups. The value can be huge, so return it modulo 10^9 + 7.
Example 1
Input: strength = [2,1,3]
Output: 27
Explanation: The six groups give 2·2 + 1·1 + 3·3 + 1·3 + 1·4 + 1·6 = 4 + 1 + 9 + 3 + 4 + 6 = 27.
Example 2
Input: strength = [4,4]
Output: 64
Explanation: 4·4 + 4·4 + 4·8 = 64.
Example 3
Input: strength = [1000000000]
Output: 49
Explanation: 10^18 modulo 10^9 + 7 is 49.
Constraints
1 <= strength.length <= 10^51 <= strength[i] <= 10^9
Hints for Sum of Total Strength of Wizards
Hint 1
Flip the sum around: for each wizard, which groups is it the weakest member of?
Hint 2
With a monotonic stack find, for every
i, the span of groups in whichstrength[i]is the minimum. Break ties so each group is counted for exactly one index (strictly smaller on one side, smaller-or-equal on the other).Hint 3
You then need the sum of
sum(l..r)over everylin a range andrin another range. With prefix sumsPand prefix sums of prefix sumsPP, that total is a difference of two products — O(1) per index.
How to solve Sum of Total Strength of Wizards
Count each group once, at the index of its minimum. For index i the groups where it is the minimum have their left end in (L, i] and right end in [i, R), and the sum of all their sums collapses to a closed form over prefix sums of prefix sums.
Approach
- With a monotonic stack compute
L[i], the nearest index to the left with a strictly smaller strength (or -1), andR[i], the nearest index to the right with a smaller-or-equal strength (orn). - Build
P[t] = strength[0] + … + strength[t - 1]andPP[t] = P[0] + … + P[t - 1], all modulo10^9 + 7. - The groups
[x, y]withL < x <= i <= y < Rhave sums totalling(i - L) · (PP[R + 1] - PP[i + 1]) - (R - i) · (PP[i + 1] - PP[L + 1]). - Add
strength[i]times that total to the answer for everyi, keeping everything reduced modulo10^9 + 7.
Why it works
The sum of a group [x, y] is P[y + 1] - P[x]. Summing over all y in [i, R) and x in (L, i] gives (i - L) · ΣP[y + 1] - (R - i) · ΣP[x], and each of those Σ terms is a difference of two PP values. The asymmetric tie rule (strict on the left, non-strict on the right) assigns a group with a repeated minimum to the rightmost copy of that minimum only, so every group is counted exactly once.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Using strict comparisons on both sides counts groups with equal minima twice; non-strict on both sides misses them.
- Products of two residues reach 10^18 — use 64-bit integers, and in JavaScript split one factor so no product passes 2^53.
- Subtractions under a modulus can go negative: add the modulus before reducing.
Reference solution
Python
from typing import List
def totalStrength(strength: List[int]) -> int:
MOD = 10**9 + 7
n = len(strength)
left = [-1] * n
right = [n] * n
st = []
for i in range(n):
while st and strength[st[-1]] >= strength[i]:
right[st.pop()] = i
left[i] = st[-1] if st else -1
st.append(i)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = (prefix[i] + strength[i]) % MOD
pp = [0] * (n + 2)
for i in range(n + 1):
pp[i + 1] = (pp[i] + prefix[i]) % MOD
total = 0
for i in range(n):
l, r = left[i], right[i]
plus = (i - l) * (pp[r + 1] - pp[i + 1])
minus = (r - i) * (pp[i + 1] - pp[l + 1])
total = (total + strength[i] * ((plus - minus) % MOD)) % MOD
return totalJava
public static int totalStrength(int[] strength) {
final long MOD = 1000000007L;
int n = strength.length;
int[] left = new int[n], right = new int[n], st = new int[n];
int top = 0;
for (int i = 0; i < n; i++) {
right[i] = n;
while (top > 0 && strength[st[top - 1]] >= strength[i]) right[st[--top]] = i;
left[i] = top > 0 ? st[top - 1] : -1;
st[top++] = i;
}
long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) prefix[i + 1] = (prefix[i] + strength[i]) % MOD;
long[] pp = new long[n + 2];
for (int i = 0; i <= n; i++) pp[i + 1] = (pp[i] + prefix[i]) % MOD;
long total = 0;
for (int i = 0; i < n; i++) {
int l = left[i], r = right[i];
long plus = (long) (i - l) * ((pp[r + 1] - pp[i + 1] + MOD) % MOD) % MOD;
long minus = (long) (r - i) * ((pp[i + 1] - pp[l + 1] + MOD) % MOD) % MOD;
long diff = (plus - minus + MOD) % MOD;
total = (total + strength[i] * diff) % MOD;
}
return (int) total;
}C++
int totalStrength(vector<int>& strength) {
const long long MOD = 1000000007LL;
int n = strength.size();
vector<int> left(n, -1), right(n, n), st;
for (int i = 0; i < n; i++) {
while (!st.empty() && strength[st.back()] >= strength[i]) {
right[st.back()] = i;
st.pop_back();
}
left[i] = st.empty() ? -1 : st.back();
st.push_back(i);
}
vector<long long> prefix(n + 1, 0), pp(n + 2, 0);
for (int i = 0; i < n; i++) prefix[i + 1] = (prefix[i] + strength[i]) % MOD;
for (int i = 0; i <= n; i++) pp[i + 1] = (pp[i] + prefix[i]) % MOD;
long long total = 0;
for (int i = 0; i < n; i++) {
int l = left[i], r = right[i];
long long plus = (long long)(i - l) * ((pp[r + 1] - pp[i + 1] + MOD) % MOD) % MOD;
long long minus = (long long)(r - i) * ((pp[i + 1] - pp[l + 1] + MOD) % MOD) % MOD;
long long diff = (plus - minus + MOD) % MOD;
total = (total + (long long)strength[i] * diff) % MOD;
}
return (int)total;
}JavaScript
var totalStrength = function(strength) {
var MOD = 1000000007;
var n = strength.length;
var mulmod = function(a, b) {
return ((a * (b >>> 16)) % MOD * 65536 + a * (b & 65535)) % MOD;
};
var left = new Array(n), right = new Array(n).fill(n), st = [];
for (var i = 0; i < n; i++) {
while (st.length > 0 && strength[st[st.length - 1]] >= strength[i]) right[st.pop()] = i;
left[i] = st.length > 0 ? st[st.length - 1] : -1;
st.push(i);
}
var prefix = new Array(n + 1).fill(0);
for (var a = 0; a < n; a++) prefix[a + 1] = (prefix[a] + strength[a]) % MOD;
var pp = new Array(n + 2).fill(0);
for (var b = 0; b <= n; b++) pp[b + 1] = (pp[b] + prefix[b]) % MOD;
var total = 0;
for (var j = 0; j < n; j++) {
var l = left[j], r = right[j];
var plus = (j - l) * ((pp[r + 1] - pp[j + 1] + MOD) % MOD) % MOD;
var minus = (r - j) * ((pp[j + 1] - pp[l + 1] + MOD) % MOD) % MOD;
var diff = (plus - minus + MOD) % MOD;
total = (total + mulmod(strength[j], diff)) % MOD;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Prefix Sum