Pattern Reference
Contribution Technique
"Count how many subarrays each element participates in."
Loading...
Deep Dive Tutorial
The key insight: instead of "for each pair (i,j), add f(arr[i..j])," rewrite as "for each element arr[k], in how many pairs (i,j) with i≤k≤j does arr[k] contribute?" Often the count has a closed form based on distances to boundaries or using monotonic stack to find "reach" of each element. This converts O(n²) sums into O(n) or O(n log n).
Contribution of each element to subarray sums
// Sum of all subarray sums = Σ arr[i] * (i+1) * (n-i)
// Reasoning: element arr[i] appears in subarrays [l,r] where l∈[0,i] and r∈[i,n-1]
// Count = (i+1) choices for l × (n-i) choices for r
function sumOfSubarraySums(arr) {
const n = arr.length;
let total = 0;
for (let i = 0; i < n; i++) {
total += arr[i] * (i + 1) * (n - i);
}
return total;
}
// Sum of subarray minimums = Σ arr[i] * (left_reach[i]+1) * (right_reach[i]+1)
// left_reach[i] = how far left can arr[i] be minimum (until a smaller element)
// right_reach[i] = how far right can arr[i] be minimum
// Use monotonic stack to compute both in O(n)
function sumSubarrayMins(arr) {
const n = arr.length, MOD = 1e9 + 7;
const left = new Array(n), right = new Array(n);
const stack = [];
// Left: distance to previous smaller element
for (let i = 0; i < n; i++) {
while (stack.length && arr[stack.at(-1)] >= arr[i]) stack.pop();
left[i] = stack.length ? i - stack.at(-1) - 1 : i;
stack.push(i);
}
stack.length = 0;
// Right: distance to next smaller or equal element
for (let i = n - 1; i >= 0; i--) {
while (stack.length && arr[stack.at(-1)] > arr[i]) stack.pop();
right[i] = stack.length ? stack.at(-1) - i - 1 : n - 1 - i;
stack.push(i);
}
let ans = 0;
for (let i = 0; i < n; i++) ans = (ans + arr[i] * (left[i]+1) * (right[i]+1)) % MOD;
return ans;
}Worked Problems
puzzle
Contribution technique template:
1. Identify what each element contributes to the final answer
2. Count in how many subsets/subarrays/pairs that element "dominates" or "appears"
3. Multiply element × count, sum over all elements
Finding count (common helpers):
- For each element being subarray min/max: monotonic stack → O(n)
- For each element being first occurrence of char: last-occurrence array → O(n)
- For each element in all subarrays: element at index i → (i+1) × (n-i) subarrays
Key insight: Σ over subarrays of f(subarray) = Σ over elements of contribution(element). Swapping the order of summation often reveals a simpler structure.
1. Identify what each element contributes to the final answer
2. Count in how many subsets/subarrays/pairs that element "dominates" or "appears"
3. Multiply element × count, sum over all elements
Finding count (common helpers):
- For each element being subarray min/max: monotonic stack → O(n)
- For each element being first occurrence of char: last-occurrence array → O(n)
- For each element in all subarrays: element at index i → (i+1) × (n-i) subarrays
Key insight: Σ over subarrays of f(subarray) = Σ over elements of contribution(element). Swapping the order of summation often reveals a simpler structure.