We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Total Strength of Wizards

Number: 2368

Difficulty: Hard

Paid? No

Companies: Amazon, Meta, Apple

Problem Description

Given an array representing the strength of each wizard, we must compute for every contiguous subarray the product of (the minimum strength in that subarray) and (the sum of strengths in that subarray). The final answer is the sum of total strengths for all contiguous groups, returned modulo 10^9+7.

Key Insights

  • Use a monotonic stack to find, for every index:
    • The nearest index on the left with a strictly smaller strength.
    • The nearest index on the right with a strictly smaller strength.
  • Each wizard’s strength becomes the minimum for several subarrays. Determine the range in which that wizard’s strength is the minimum.
  • Employ prefix sums and prefix-of-prefix sums to quickly compute the sum of subarray sums for fast aggregation.
  • The contribution for each wizard (as the minimum) is computed using derived formulas based on its range boundaries.

Space and Time Complexity

Time Complexity: O(n), where n is the number of wizards.
Space Complexity: O(n) for the stacks and prefix sum arrays.

Solution

We compute left and right boundaries for each wizard index using a monotonic stack. For an index i, let:

  • l = the index of the previous smaller element (or -1 if none),
  • r = the index of the next smaller element (or n if none).

Thus, strength[i] is the minimum for all subarrays starting in (l+1, i) and ending in (i, r-1).

To quickly compute the sum of wizard strengths over any subarray, we build a prefix sum array P such that P[i+1] = P[i] + strength[i]. Next, a second prefix array PP is built where PP[i+1] = PP[i] + P[i+1]. With these, the sum of strengths of subarray [i, j] equals P[j+1] - P[i].

For the contribution where strength[i] is the minimum, we combine subarray sums over ranges partitioned by i. The derived formula to compute the total contribution for index i is:

contribution = strength[i] * [((PP[r] - PP[i]) * (i - l)) - ((PP[i] - PP[l+1]) * (r - i))]

We sum the contributions for all indices and take the result modulo 10^9+7.

Code Solutions

# Python solution with line-by-line comments

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        mod = 10**9 + 7
        n = len(strength)
        # Build left boundaries: previous index with a smaller value
        left = [-1] * n
        stack = []
        for i in range(n):
            # maintain a non-decreasing stack
            while stack and strength[stack[-1]] >= strength[i]:
                stack.pop()
            left[i] = stack[-1] if stack else -1
            stack.append(i)
        
        # Build right boundaries: next index with a smaller value
        right = [n] * n
        stack = []
        for i in range(n-1, -1, -1):
            # maintain a strictly decreasing stack (pop equal or larger)
            while stack and strength[stack[-1]] > strength[i]:
                stack.pop()
            right[i] = stack[-1] if stack else n
            stack.append(i)
        
        # Build prefix sum array: P[i+1] is sum of strength[0...i]
        P = [0] * (n + 1)
        for i in range(n):
            P[i+1] = (P[i] + strength[i]) % mod
        
        # Build prefix-of-prefix sum array: PP[i+1] = sum(P[0...i])
        PP = [0] * (n + 2)
        for i in range(n+1):
            PP[i+1] = (PP[i] + P[i]) % mod
        
        result = 0
        # Calculate the contribution for each index where strength[i] is the minimum
        for i in range(n):
            l = left[i]
            r = right[i]
            # total sum for subarrays to the right of i minus those that do not include i
            right_sum = (PP[r+1] - PP[i+1]) % mod
            left_sum = (PP[i+1] - PP[l+1]) % mod
            # Multiply by the counts based on distance to boundaries and then by strength[i]
            contribution = strength[i] * ((right_sum * (i - l) - left_sum * (r - i)) % mod) % mod
            result = (result + contribution) % mod
        
        return result
← Back to All Questions