Sum of Total Strength of Wizards - Problem

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 i^th 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 sum 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 10⁹ + 7.

A subarray is a contiguous non-empty sequence of elements within an array.

Input & Output

Example 1 — Basic Case

$ Input: strength = [1,3,1,2]

› Output: 44

💡 Note: All subarrays: [1]=1×1=1, [1,3]=1×4=4, [1,3,1]=1×5=5, [1,3,1,2]=1×7=7, [3]=3×3=9, [3,1]=1×4=4, [3,1,2]=1×6=6, [1]=1×1=1, [1,2]=1×3=3, [2]=2×2=4. Total = 1+4+5+7+9+4+6+1+3+4 = 44

Example 2 — Single Element

$ Input: strength = [5]

› Output: 25

💡 Note: Only one subarray [5]: minimum=5, sum=5, total strength = 5×5 = 25

Example 3 — Ascending Order

$ Input: strength = [1,2,3]

› Output: 33

💡 Note: [1]=1×1=1, [1,2]=1×3=3, [1,2,3]=1×6=6, [2]=2×2=4, [2,3]=2×5=10, [3]=3×3=9. Total = 1+3+6+4+10+9 = 33

Constraints

1 ≤ strength.length ≤ 10⁵
1 ≤ strength[i] ≤ 10⁹

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to find the contribution of each element when it serves as the minimum in subarrays. The optimal approach uses monotonic stack to efficiently find the range where each element is minimum, combined with prefix sums for fast sum calculations. Time: O(n), Space: O(n)

Common Approaches

✓ Brute Force - Check All Subarrays

⏱️ Time: O(n³) Space: O(1)

For each possible subarray, find the minimum element and sum of all elements, multiply them together, and add to the final result.

Monotonic Stack with Prefix Sums

⏱️ Time: O(n) Space: O(n)

For each element, find the range where it's the minimum using monotonic stack. Then calculate its contribution to the final sum using prefix sum techniques.

Brute Force - Check All Subarrays — Algorithm Steps

Iterate through all possible starting positions
For each start, iterate through all ending positions
Find minimum and sum for each subarray
Multiply min × sum and add to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Create all possible contiguous subarrays

Calculate Strength

For each: find min × sum

Sum Results

Add all total strengths together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int* strength, int n) {
    const int MOD = 1000000007;
    long long total = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int minVal = INT_MAX;
            long long sumVal = 0;
            for (int k = i; k <= j; k++) {
                if (strength[k] < minVal) {
                    minVal = strength[k];
                }
                sumVal += strength[k];
            }
            total = (total + (long long)minVal * sumVal) % MOD;
        }
    }
    
    return total;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int strength[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            strength[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(strength, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Triple nested loops: n starting positions × n ending positions × n to find min/sum

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Sum of Total Strength of Wizards - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler