HardNo. 2281
Sum of Total Strength of Wizards — LeetCode 2281 Python Solution
- Pattern
- Prefix Sum
- Topics
- Stack, Array, Prefix Sum, Monotonic Stack
- 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
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1856 | Maximum Subarray Min-Product | Medium |
| 2289 | Steps to Make Array Non-decreasing | Medium |
| 0084 | Largest Rectangle in Histogram | Hard |
| 0456 | 132 Pattern | Medium |
| 0503 | Next Greater Element II | Medium |
| 0654 | Maximum Binary Tree | Medium |
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.