Sum of Total Strength of Wizards

Hard
1404.

Sum of Total Strength of Wizards

Sum of Total Strength of Wizards is a hard coding problem on arrays, prefix sum and stack, asked in Amazon, Google and Uber interviews.

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^5
  • 1 <= strength[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} strength
 * @return {number}
 */
var totalStrength = function(strength) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 1 <= strength[i] <= 10^9

Hints for Sum of Total Strength of Wizards

  1. Hint 1

    Flip the sum around: for each wizard, which groups is it the weakest member of?

  2. Hint 2

    With a monotonic stack find, for every i, the span of groups in which strength[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).

  3. Hint 3

    You then need the sum of sum(l..r) over every l in a range and r in another range. With prefix sums P and prefix sums of prefix sums PP, 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

  1. With a monotonic stack compute L[i], the nearest index to the left with a strictly smaller strength (or -1), and R[i], the nearest index to the right with a smaller-or-equal strength (or n).
  2. Build P[t] = strength[0] + … + strength[t - 1] and PP[t] = P[0] + … + P[t - 1], all modulo 10^9 + 7.
  3. The groups [x, y] with L < x <= i <= y < R have sums totalling (i - L) · (PP[R + 1] - PP[i + 1]) - (R - i) · (PP[i + 1] - PP[L + 1]).
  4. Add strength[i] times that total to the answer for every i, keeping everything reduced modulo 10^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 total

Java

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