Sum of Total Strength of Wizards - Practice Coding Problems

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: 42

💡 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+2 = 42

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: 44

💡 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

Understanding the Visualization

Input Array

Wizard strengths: [1,3,1,2]

Calculate Each Subarray

For each subarray: total_strength = min × sum

Sum All Results

Add all total_strength values together

Key Takeaway

🎯 Key Insight: Each element contributes as minimum to specific subarrays - find these ranges efficiently using monotonic stack

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

Approach	Time	Space	Notes
✓ Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all possible subarrays and calculate total strength for each
Monotonic Stack with Prefix Sums	O(n)	O(n)	Use monotonic stack to find contribution ranges and prefix sums for efficient calculation

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;
}

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

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subarrays — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler