How hard is LeetCode 2281. Sum of Total Strength of Wizards?

LeetCode 2281. Sum of Total Strength of Wizards is rated Hard on LeetCode.

What is the time complexity of LeetCode 2281. Sum of Total Strength of Wizards?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 2281. Sum of Total Strength of Wizards?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 2281. Sum of Total Strength of Wizards cover?

LeetCode 2281. Sum of Total Strength of Wizards is tagged Stack, Array, Prefix Sum and Monotonic Stack on LeetCode.

Sum of Total Strength of Wizards — LeetCode 2281 Python Solution

HardStackArrayPrefix SumMonotonic Stack

Problem: #2281
Pattern: Prefix Sum
Reading time: 6 min
Source: leetcode.com

The 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 ith wizard.

Example

Input: strength = [1,3,1,2]
Output: 44
Explanation: The following are all the contiguous groups of wizards:

Python solution

Python

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        n = len(strength)
        left = [-1] * n
        right = [n] * n
        stk = []
        for i, v in enumerate(strength):
            while stk and strength[stk[-1]] >= v:
                stk.pop()
            if stk:
                left[i] = stk[-1]
            stk.append(i)
        stk = []
        for i in range(n - 1, -1, -1):
            while stk and strength[stk[-1]] > strength[i]:
                stk.pop()
            if stk:
                right[i] = stk[-1]
            stk.append(i)

        ss = list(accumulate(list(accumulate(strength, initial=0)), initial=0))
        mod = int(1e9) + 7
        ans = 0
        for i, v in enumerate(strength):
            l, r = left[i] + 1, right[i] - 1
            a = (ss[r + 2] - ss[i + 1]) * (i - l + 1)
            b = (ss[i + 1] - ss[l]) * (r - i + 1)
            ans = (ans + (a - b) * v) % mod
        return ans

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2281. Sum of Total Strength of Wizards is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2281. Sum of Total Strength of Wizards?: LeetCode 2281. Sum of Total Strength of Wizards is rated Hard on LeetCode.
What is the time complexity of LeetCode 2281. Sum of Total Strength of Wizards?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 2281. Sum of Total Strength of Wizards?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 2281. Sum of Total Strength of Wizards cover?: LeetCode 2281. Sum of Total Strength of Wizards is tagged Stack, Array, Prefix Sum and Monotonic Stack on LeetCode.