Pattern Guide
Contribution Technique
"Count how many times each element contributes to the answer. Reverse the summation."
The contribution technique (also called "counting contribution of each element") reverses the order of summation: instead of summing over all subsets/pairs and computing element value, sum over all elements and count how many subsets/pairs include them. This converts O(n²) enumeration into O(n log n) or O(n) by exploiting structure. Core pattern for sum over all subarrays/subsets, XOR sum, max/min contribution.
Problems you can solve with this pattern
5 problems · click any to start solving
// 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;
}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).
// 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;
}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.