2281. Sum of Total Strength of Wizards

HardStackArrayPrefix SumMonotonic Stack
Leetcode Link

Problem Description

In this problem, we are given an array strength representing the strength of wizards in a kingdom, indexed starting from 0. We need to compute the sum of the total strengths for all possible contiguous subarrays of wizards. The total strength of a specific group of contiguous wizards is the product of two factors:

  1. The strength of the weakest wizard in the group.
  2. The sum of strengths of all wizards in the group.

The task is to return the sum of total strengths of all such groups. However, since the sum may be huge, we must return the sum modulo (10^9 + 7).

A subarray is defined as a contiguous non-empty sequence from the array.

Intuition behind the Solution

The brute force approach to solving this problem would involve finding all possible subarrays and calculating their total strengths, but this would be inefficient for large arrays. To optimize, we can use a stack-based approach to find the bounds within which each wizard is the weakest.

We iterate through the strength array to find, for each wizard, the index of the next weaker wizard to the left and to the right. This helps us determine the range of subarrays where the current wizard would be the weakest and affect the total strength calculation.

Once we have these left and right bounds for each wizard, the next step is to calculate the sum of strengths for all subarrays ending at each position. To do this efficiently, we use prefix sums, which allow us to calculate sums over ranges in constant time.

Finally, we combine the above information to calculate the answer using the formula derived from the definition of total strength and our understanding of the provided bounds. Specifically, we find the sum of products of the strength of the current wizard (the weakest), the sum of strengths for subarrays ending at this wizard's position, and the count of such subarrays.

Let's break down the important steps of our solution:

  1. We use stacks to find the left and right indices (bounds) where the strength[i] is the weakest in a contiguous group.
  2. We calculate prefix sums twice over the array. First, to get the sum of elements up to each index, and then to get the sum of those sums. This helps to find the total sum of strengths in different ranges quickly.
  3. We then calculate the answer using the derived indices and prefix sums, taking care to apply the modulo operation to handle large numbers.
  4. With all these steps, we ensure efficient computation by avoiding repeated sum calculations and by determining bounds for each wizard efficiently.

These optimization techniques allow the solution to run significantly faster than the brute force method and are suitable for arrays of any size.

Learn more about Stack, Prefix Sum and Monotonic Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Solution Approach

The solution provided leverages a stack to efficiently determine the bounds of subarrays for which each wizard's strength is the limiting strength. Here is a step-by-step explanation of the implementation details:

  1. Initialization of Auxiliary Arrays:

    • left: An array to store the index of the previous weaker wizard for each wizard.
    • right: An array to store the index of the next weaker wizard for each wizard.
    • stk: A stack that will help in finding the indices for the left and right bounds.

  2. Finding Left Bounds:

    • Iterate through the strength array from left to right (increasing index).
    • For each wizard, pop elements from the stack while the top of the stack represents a wizard with strength greater than or equal to the current wizard, and then store the index of the last popped element as the previous weaker wizard.
    • If the stack is not empty after popping stronger wizards, the top element will be the index of the previous weaker wizard.
    • Add the current index to the stack for future comparisons.

  3. Finding Right Bounds:

    • Iterate through the strength array from right to left (decreasing index).
    • The process is similar to finding the left bounds but in reverse order.
    • For each wizard, pop elements from the stack while the top of the stack represents a wizard with strength greater than the current wizard.
    • The index of the last popped element will be used to update the right bound for the current wizard.
    • Append the current wizard's index to the stack for future comparisons.

  4. Using Prefix Sums:

    • Calculate the prefix sums for strength array using the accumulate function twice. The first accumulation gives us the running total of strengths, and the second accumulation gives us the running total of these running totals. This is stored in the ss array.
    • Prefix sums allow us to calculate the sum of any subarray in constant time.

  5. Computing the Answer:

    • Iterate through each element in strength again.
    • For each wizard, calculate two sums using the prefix sums array ss:
      • a: The sum of strengths from the left bound to the current wizard.
      • b: The sum of strengths from the current wizard to the right bound.
    • These sums are adjusted according to the number of wizards included in the subarrays to the left and right of the current wizard (using l and r variables).
    • The difference (a - b) is weighted by the current wizard's strength (this represents the weakest strength in the subarray).
    • Take the modulus of the intermediate result to handle the large numbers and update the cumulative ans.

  6. Final Result:

    • After iterating through all wizards, the ans variable holds the sum of the total strengths of all contiguous groups of wizards modulo 10^9 + 7.

To summarize, the algorithm uses a stack-based approach to find the bounds within which each wizard is the weakest, calculates prefix sums to efficiently manage the range sum queries, and combines this information to obtain the final sum of total strengths, while carrying out modular arithmetic operations to comply with the problem's requirement.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following shows the order of node visit in a Breadth-first Search?

Example Walkthrough

Let's consider an array strength of wizard strengths given by: [3, 1, 2, 4]. The goal is to find the sum of total strengths for all possible contiguous subarrays.

  1. Initialization of Auxiliary Arrays: We initialize left, right, and stk as empty.

  2. Finding Left Bounds: We iterate through [3, 1, 2, 4] from left to right:

    • At strength[0] = 3, stk is empty, so we push 0. left[0] remains -1 (a convention to indicate no previous weaker wizard).
    • At strength[1] = 1, we pop 3 from stack because 1 is weaker than 3. Now, stk is empty, so we push 1. left[1] is set to -1.
    • At strength[2] = 2, stk has 1 and 2 is stronger, so we push 2. left[2] is 1.
    • At strength[3] = 4, stk has 1, 2 and since 2 is weaker, we just push 3. left[3] is 2.

    Now, left is [-1, -1, 1, 2].

  3. Finding Right Bounds: We do a similar process in reverse:

    • Start at strength[3] = 4, stk is empty, so we push 3. right[3] remains the length of the array, which is 4, indicating no next weaker wizard.
    • At strength[2] = 2, we pop 4 from stack because 2 is weaker than 4. We push 2. right[2] is 3.
    • At strength[1] = 1, nothing is popped because the stack is empty, so we push 1. right[1] is 4.
    • At strength[0] = 3, we pop 1 and 2 from the stack as 3 is stronger than both. We push 0. right[0] is 1.

    Now, right is [1, 4, 3, 4].

  4. Using Prefix Sums: We calculate prefix sums ss of strengths: [3, 4, 6, 10] and the sum of sums: [3, 7, 13, 23].

  5. Computing the Answer: We iterate again and calculate contributions to the answer:

    • For wizard at index 0, a = 3 * (0 + 1), b = 7 * (1 - 0), and strength is 3. The contribution is 3 * (a - b) = 3 * (3 - 7) = -12.
    • For wizard at index 1, a = 4 * (1 + 1), b = 23 * (4 - 1), and strength is 1. The contribution is 1 * (a - b) = 1 * (8 - 69) = -61.
    • For wizard at index 2, a = 6 * (1 - (-1 + 1)), b = 10 * (3 - 2), and strength is 2. The contribution is 2 * (a - b) = 2 * (6 - 10) = -8.
    • For wizard at index 3, a = 10 * (3 - 2), b = 23 * (4 - 3), and strength is 4. The contribution is 4 * (a - b) = 4 * (10 - 23) = -52.

    The total strength is the sum of contributions: (-12) + (-61) + (-8) + (-52) = -133.

    Note that the negative result occurs due to the way we calculate a - b. The actual contribution is always non-negative since it represents a sum of products of strengths. In practice, we would take each contribution modulo (10^9 + 7) to keep the results properly bounded.

  6. Final Result: The algorithm would thus sum these contributions and apply the modulo to ensure they remain within the specific bounds, giving us the sum of the total strengths of all contiguous groups of wizards modulo (10^9 + 7).

By applying this process to larger arrays, we can find the desired sum while keeping the computational cost within manageable bounds, thus solving traditionally expensive problems both effectively and efficiently.

Solution Implementation

1from itertools import accumulate
2
3class Solution:
4    def totalStrength(self, strength):
5        # Obtain the length of the strength array
6        num_elements = len(strength)
7      
8        # Arrays to hold indices of closest smaller elements to the left and right
9        closest_smaller_left = [-1] * num_elements
10        closest_smaller_right = [num_elements] * num_elements
11      
12        # Stack to assist in finding the closest smaller elements
13        stack = []
14      
15        # Determine closest smaller to the left of each element
16        for index, value in enumerate(strength):
17            while stack and strength[stack[-1]] >= value:
18                stack.pop()
19            if stack:
20                closest_smaller_left[index] = stack[-1]
21            stack.append(index)
22      
23        # Reset the stack for finding the closest smaller elements to the right
24        stack = []
25      
26        # Determine closest smaller to the right of each element
27        for index in range(num_elements - 1, -1, -1):
28            while stack and strength[stack[-1]] > strength[index]:
29                stack.pop()
30            if stack:
31                closest_smaller_right[index] = stack[-1]
32            stack.append(index)
33
34        # Accumulative sums which are accumulated twice
35        summed_strength = list(accumulate(list(accumulate(strength, initial=0)), initial=0))
36      
37        # Modulus for the final result as per problem constraints
38        modulo = int(1e9) + 7
39      
40        # Variable to hold the final answer
41        total_strength = 0
42      
43        # Calculate the total strength according to the given formula
44        for i, value in enumerate(strength):
45            left_index, right_index = closest_smaller_left[i] + 1, closest_smaller_right[i] - 1
46            sum_left = (summed_strength[right_index + 2] - summed_strength[i + 1]) * (i - left_index + 1)
47            sum_right = (summed_strength[i + 1] - summed_strength[left_index]) * (right_index - i + 1)
48            total_strength = (total_strength + (sum_left - sum_right) * value) % modulo
49      
50        # Return the computed total strength
51        return total_strength
52
1import java.util.Arrays;
2import java.util.ArrayDeque;
3import java.util.Deque;
4
5class Solution {
6    public int totalStrength(int[] strength) {
7        // Get the length of the strength array
8        int n = strength.length;
9
10        // Initialize arrays to store the nearest smaller elements' indices
11        int[] nearestSmallerLeftIndex = new int[n];
12        int[] nearestSmallerRightIndex = new int[n];
13
14        // Initialize these arrays with default values
15        Arrays.fill(nearestSmallerLeftIndex, -1);
16        Arrays.fill(nearestSmallerRightIndex, n);
17
18        Deque<Integer> stack = new ArrayDeque<>();
19
20        // Find the nearest smaller element on the left for each element
21        for (int i = 0; i < n; ++i) {
22            while (!stack.isEmpty() && strength[stack.peek()] >= strength[i]) {
23                stack.pop();
24            }
25            if (!stack.isEmpty()) {
26                nearestSmallerLeftIndex[i] = stack.peek();
27            }
28            stack.push(i);
29        }
30
31        // Clear the stack for the next iteration
32        stack.clear();
33
34        // Find the nearest smaller element on the right for each element
35        for (int i = n - 1; i >= 0; --i) {
36            while (!stack.isEmpty() && strength[stack.peek()] > strength[i]) {
37                stack.pop();
38            }
39            if (!stack.isEmpty()) {
40                nearestSmallerRightIndex[i] = stack.peek();
41            }
42            stack.push(i);
43        }
44
45        // Specify the modulus value for the answer
46        int mod = (int) 1e9 + 7;
47
48        // Calculate the prefix sum of the strength array
49        int[] prefixSum = new int[n + 1];
50        for (int i = 0; i < n; ++i) {
51            prefixSum[i + 1] = (prefixSum[i] + strength[i]) % mod;
52        }
53
54        // Calculate the prefix sum of the prefix sum array
55        int[] prefixSumOfPrefixSum = new int[n + 2];
56        for (int i = 0; i < n + 1; ++i) {
57            prefixSumOfPrefixSum[i + 1] = (prefixSumOfPrefixSum[i] + prefixSum[i]) % mod;
58        }
59
60        // Initialize the answer
61        long answer = 0;
62
63        // Calculate the total strength
64        for (int i = 0; i < n; ++i) {
65            int value = strength[i];
66            int left = nearestSmallerLeftIndex[i] + 1;
67            int right = nearestSmallerRightIndex[i] - 1;
68            long sumLeft = (long) (i - left + 1) * (prefixSumOfPrefixSum[right + 2] - prefixSumOfPrefixSum[i + 1]);
69            long sumRight = (long) (right - i + 1) * (prefixSumOfPrefixSum[i + 1] - prefixSumOfPrefixSum[left]);
70            answer = (answer + value * ((sumLeft - sumRight) % mod)) % mod;
71        }
72
73        // Return the final total strength value, adjusted for mod
74        return (int) (answer + mod) % mod;
75    }
76}
77
1class Solution {
2public:
3    // Function to compute the total strength of all subarrays
4    int totalStrength(vector<int>& strength) {
5        int n = strength.size();
6        vector<int> left(n, -1);  // Stores closest index on the left with a lower strength value
7        vector<int> right(n, n);  // Stores closest index on the right with a lower or equal strength value
8        stack<int> stk;  // Stack to help in finding the closest index
9      
10        // Find closest smaller value on the left for each element
11        for (int i = 0; i < n; ++i) {
12            while (!stk.empty() && strength[stk.top()] >= strength[i]) {
13                stk.pop();
14            }
15            if (!stk.empty()) {
16                left[i] = stk.top();
17            }
18            stk.push(i);
19        }
20      
21        // Clear the stack to reuse it for finding closest smaller value on the right
22        stk = stack<int>();
23      
24        // Find closest smaller value on the right for each element
25        for (int i = n - 1; i >= 0; --i) {
26            while (!stk.empty() && strength[stk.top()] > strength[i]) {
27                stk.pop();
28            }
29            if (!stk.empty()) {
30                right[i] = stk.top();
31            }
32            stk.push(i);
33        }
34      
35        int mod = 1e9 + 7;
36        vector<int> prefixSum(n + 1);  // Prefix sums of strengths for quick range query
37        for (int i = 0; i < n; ++i) {
38            prefixSum[i + 1] = (prefixSum[i] + strength[i]) % mod;
39        }
40      
41        vector<int> prefixSumOfPrefixSum(n + 2);  // Prefix sums of prefix sums for range sum query
42        for (int i = 0; i < n + 1; ++i) {
43            prefixSumOfPrefixSum[i + 1] = (prefixSumOfPrefixSum[i] + prefixSum[i]) % mod;
44        }
45      
46        int ans = 0;  // Variable to store the final answer
47      
48        // Calculate total strength for each subarray
49        for (int i = 0; i < n; ++i) {
50            int value = strength[i];
51            int l = left[i] + 1, r = right[i] - 1;
52            long leftPart = (long) (i - l + 1) * (prefixSumOfPrefixSum[r + 2] - prefixSumOfPrefixSum[i + 1]);
53            long rightPart = (long) (r - i + 1) * (prefixSumOfPrefixSum[i + 1] - prefixSumOfPrefixSum[l]);
54            ans = (ans + value * ((leftPart - rightPart) % mod)) % mod;
55        }
56      
57        // Adjust by mod to ensure non-negative result, as mod subtraction can result in negative number
58        return (ans + mod) % mod;
59    }
60};
61
1// Function to compute the total strength of all subarrays
2function totalStrength(strength: number[]): number {
3    const n: number = strength.length;
4    const left: number[] = new Array(n).fill(-1);  // Closest index to the left with a lower strength value
5    const right: number[] = new Array(n).fill(n);  // Closest index to the right with a lower or equal strength value
6    const stack: number[] = [];  // Stack to help find the closest index
7
8    // Find the closest smaller value on the left for each element
9    for (let i = 0; i < n; ++i) {
10        while (stack.length > 0 && strength[stack[stack.length - 1]] >= strength[i]) {
11            stack.pop();
12        }
13        if (stack.length > 0) {
14            left[i] = stack[stack.length - 1];
15        }
16        stack.push(i);
17    }
18  
19    // Clear the stack to reuse for finding the closest smaller value on the right
20    stack.length = 0;
21
22    // Find the closest smaller value on the right for each element
23    for (let i = n - 1; i >= 0; --i) {
24        while (stack.length > 0 && strength[stack[stack.length - 1]] > strength[i]) {
25            stack.pop();
26        }
27        if (stack.length > 0) {
28            right[i] = stack[stack.length - 1];
29        }
30        stack.push(i);
31    }
32
33    const mod: number = 1e9 + 7;
34    const prefixSum: number[] = new Array(n + 1).fill(0);  // Prefix sums of strengths for quick range query
35
36    // Calculate prefix sums of strengths
37    for (let i = 0; i < n; ++i) {
38        prefixSum[i + 1] = (prefixSum[i] + strength[i]) % mod;
39    }
40
41    const prefixSumOfPrefixSum: number[] = new Array(n + 2).fill(0);  // Prefix sums of prefix sums for range sum query
42
43    // Calculate prefix sums of prefix sums
44    for (let i = 0; i < n + 1; ++i) {
45        prefixSumOfPrefixSum[i + 1] = (prefixSumOfPrefixSum[i] + prefixSum[i]) % mod;
46    }
47
48    let answer: number = 0;  // Variable to store the final answer
49
50    // Calculate total strength for each subarray
51    for (let i = 0; i < n; ++i) {
52        const value: number = strength[i];
53        const l: number = left[i] + 1, r: number = right[i] - 1;
54        const leftPart: number = (i - l + 1) * (prefixSumOfPrefixSum[r + 2] - prefixSumOfPrefixSum[i + 1]) % mod;
55        const rightPart: number = (r - i + 1) * (prefixSumOfPrefixSum[i + 1] - prefixSumOfPrefixSum[l]) % mod;
56        answer = (answer + value * ((leftPart - rightPart + mod) % mod)) % mod;
57    }
58
59    // Ensure non-negative result by adjusting with mod, as mod subtraction can result in a negative number
60    return (answer + mod) % mod;
61}
62
Not Sure What to Study? Take the 2-min Quiz๏ผš

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Time and Space Complexity

The given solution aims to find the total strength of non-empty contiguous subarrays of the strength array. To solve this problem efficiently, it uses the monotonic stack technique to precompute the next smaller elements on the left and right for every element.

Time Complexity

  1. The first loop iterates over the array to find the next smaller element on the left for each element. This is done in O(n) time because each element is pushed onto and popped from the stack at most once.
  2. The second loop, similar to the first one, iterates over the array to find the next smaller element on the right for each element, which also takes O(n) time.
  3. The computation of the sum of subarray sums, ss, involves two cumulative sum computations, each of which takes O(n) time. Therefore, this step is also O(n).
  4. Finally, the last loop calculates the total strength for each index, within O(n) time since each index operation is constant due to precomputed sums and smaller elements' indexes.

Considering the loops and operations are sequential, the overall time complexity is O(n) where n is the length of the strength array.

Space Complexity

  1. The space complexity is primarily impacted by the additional data structures: left, right, stk, and ss. Both left and right arrays and the stk stack have a space complexity of O(n).
  2. Similarly, the ss array, which holds the cumulative sums, has a space complexity of O(n).

The space complexity does not stack because these data structures do not depend on each other for space. Therefore, when taking all the auxiliary data structures into account, the resultant space complexity remains O(n), where n is the length of the strength array.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Prefix Sum

Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By

Monotonic Stack/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe The word monotonic means a list or a

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ