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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Sum of Total Strength of Wizards

Difficulty: Hard

Problem Description

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, the total strength is defined as the product of the strength of the weakest wizard in the group and the total of all the individual strengths of the wizards in the group. Return the sum of the total strengths of all contiguous groups of wizards, modulo 10^9 + 7.

Key Insights

  • The strength of a contiguous subarray can be computed based on its minimum element and its total sum.
  • Using a monotonic stack can help efficiently identify the range of contiguous subarrays for which each wizard is the weakest.
  • Prefix sums can be utilized to quickly compute the total strength of subarrays.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we will use the following approach:

  1. Monotonic Stack: We will maintain a stack to keep track of the indices of the wizards in a way that allows us to efficiently find the nearest smaller strength on both the left and the right.
  2. Prefix Sums: By maintaining a prefix sum array, we can quickly calculate the sum of any contiguous subarray.
  3. For each wizard, we will determine how many contiguous subarrays it is the minimum strength for, and calculate the contribution of that wizard to the total strength using the prefix sums.

The algorithm involves iterating through the list of strengths, using the monotonic stack to find the range where each wizard is the minimum, and calculating the contribution to the total strength accordingly.

Code Solutions

def sum_of_total_strength(strength):
    MOD = 10**9 + 7
    n = len(strength)
    
    # Calculate prefix sums
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = (prefix_sum[i] + strength[i]) % MOD
    
    # Monotonic stack to find the nearest smaller elements
    left = [0] * n
    right = [0] * n
    stack = []
    
    for i in range(n):
        while stack and strength[stack[-1]] >= strength[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and strength[stack[-1]] > strength[i]:
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    
    total_strength = 0
    for i in range(n):
        # Calculate contribution of strength[i]
        total_strength += strength[i] * (prefix_sum[right[i]] - prefix_sum[left[i] + 1]) % MOD
        total_strength %= MOD
        total_strength *= (right[i] - i) * (i - left[i]) % MOD
        total_strength %= MOD
    
    return total_strength

# Example usage
print(sum_of_total_strength([1, 3, 1, 2]))  # Output: 44
← Back to All Questions