Sponsored
Sponsored
This approach leverages a monotonic stack to determine the contribution of each element when it is the minimum in its subarrays. Using this, we can efficiently calculate the total subarray strength including this minimum. Along with this, prefix sums help in computing the sum of elements in a range efficiently.
Time Complexity: O(n), where n is the length of the strength array. Space Complexity: O(n) due to the prefix sums and stack usage.
1function totalStrength(strength) {
2 const MOD = 1_000_000_007;
3 const n = strength.length;
4 const prefix = Array(n + 1).fill(0);
5 for (let i = 0; i < n; i++) {
6 prefix[i + 1] = (prefix[i] + strength[i]) % MOD;
7 }
8
9 const prevSmaller = Array(n).fill(-1);
10 const nextSmaller = Array(n).fill(n);
11 const stack = [];
12
13 for (let i = 0; i < n; i++) {
14 while (stack.length && strength[stack[stack.length - 1]] > strength[i]) {
15 nextSmaller[stack.pop()] = i;
16 }
17 stack.push(i);
18 }
19
20 stack.length = 0;
21 for (let i = n - 1; i >= 0; i--) {
22 while (stack.length && strength[stack[stack.length - 1]] >= strength[i]) {
23 prevSmaller[stack.pop()] = i;
24 }
25 stack.push(i);
26 }
27
28 let result = 0;
29 for (let i = 0; i < n; i++) {
30 const l = prevSmaller[i];
31 const r = nextSmaller[i];
32 const leftPart = (prefix[i] - (l >= 0 ? prefix[l + 1] : 0)) % MOD;
33 const rightPart = (prefix[r] - (i + 1 < n ? prefix[i + 1] : 0)) % MOD;
34 const posCount = ((i - l) * (r - i)) % MOD;
35 result = (result + strength[i] * (posCount * leftPart - rightPart) % MOD) % MOD;
36 }
37
38 return result;
39}
40
41// Example usage:
42console.log(totalStrength([1,3,1,2])); // Output: 44This JavaScript code follows the same logic as the Python implementation. It calculates prefix sums, uses a monotonic stack to determine the range each element is minimal, and calculates its contribution to the total strength using the formula that considers prefix sums and position multipliers.
This approach directly calculates each subarray's total strength using nested loops with some optimizations to reduce redundant calculations, like avoiding repeated strength sums by leveraging previous computations.
Time Complexity: O(n), since each element is pushed and popped from the stack once. Space Complexity: O(n), due to the prefix arrays and auxiliary space used for indices.
1#include <vector>
2#include <numeric>
3using namespace std;
4
5class Solution {
public:
int totalStrength(vector<int>& strength) {
const int MOD = 1e9 + 7;
int n = strength.size();
vector<long long> prefix(n + 1);
for (int i = 0; i < n; ++i)
prefix[i + 1] = (prefix[i] + strength[i]) % MOD;
vector<int> prev_smaller(n, -1), next_smaller(n, n);
vector<int> stack;
for (int i = 0; i < n; ++i) {
while (!stack.empty() && strength[stack.back()] > strength[i]) {
next_smaller[stack.back()] = i;
stack.pop_back();
}
stack.push_back(i);
}
stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!stack.empty() && strength[stack.back()] >= strength[i]) {
prev_smaller[stack.back()] = i;
stack.pop_back();
}
stack.push_back(i);
}
long long total_strength = 0;
for (int i = 0; i < n; ++i) {
int l = prev_smaller[i], r = next_smaller[i];
long long left_part = (prefix[i] - (l >= 0 ? prefix[l + 1] : 0)) % MOD;
long long right_part = (prefix[r] - (i + 1 < n ? prefix[i + 1] : 0)) % MOD;
long long pos_count = (i - l) * (r - i) % MOD;
total_strength = (total_strength + strength[i] * (pos_count * left_part - right_part) % MOD) % MOD;
}
return (total_strength + MOD) % MOD;
}
};
// Example usage:
// Solution sol;
// vector<int> strength = {1,3,1,2};
// cout << sol.totalStrength(strength); // Output: 44This C++ solution applies a similar logic as the previous approach with the computational optimization related to prefix sums and using indices to denote the boundaries of subarrays. It uses loops to push and pop indices on and off the 'stack' appropriately while checking for conditions on strength values.