Contribution Counting — Subarray & Subset Aggregation Patterns

Instead of iterating over all subarrays and checking a property, flip the perspective: for each element (or pair, or bit), ask “how many subarrays does this contribute to?” This is often the difference between O(n^2) and O(n).

Quick Navigation: “I need to…”

Table of Contents

1. Core Idea: The Mental Flip
2. Foundation: Element Containment Formula
3. Monotonic Stack + Contribution: Sum of Subarray Minimums
4. Sum of Subarray Ranges: Dual Contribution
5. Per-Character Contribution: Unique Characters
6. Bit-Level Contribution
7. Pair Contribution
8. Subsequence Contribution
9. When Contribution Counting Does NOT Work
10. Pattern Recognition Cheat Sheet
11. Problem Roadmap

1. Core Idea: The Mental Flip

Traditional approach:

for each subarray [l..r]:
    compute property → accumulate

This is O(n^2) subarrays × O(cost per subarray).

Contribution counting:

for each element/pair/bit:
    count how many subarrays it participates in → accumulate

This is O(n) elements × O(1) amortized per element = O(n).

The “amortized” matters. When the per-element count is a closed-form formula (§2, §7, §8) the work really is O(1) each. When you need each element’s span — how far it dominates to the left and right (§3, §4) — you get those spans from a monotonic stack, where a single element can trigger many pops. No element is ever pushed or popped more than once across the whole scan, so the total stays O(n), but any individual step can be O(n).

The Analogy

Imagine counting total tips at a restaurant:

• Subarray approach: Go table by table, sum each table’s tips, then total everything -- slow with many tables.
• Contribution approach: Ask each waiter “how many tables did you serve?” and multiply by their tip rate -- one pass over waiters.

Key Insight

Every aggregate over all subarrays can be decomposed as:

Total = Σ (contribution of each unit × number of subarrays containing that unit)

The “unit” can be an element, a pair, a bit position, a character occurrence -- whatever the problem decomposes into.

★ Insight ───────────────────────────────────── This is the same summation-order swap that powers edge contribution on trees — here the “bridge” is a subarray boundary instead of a tree edge. Σ_subarrays property = Σ_units (unit's value × subarrays containing it). The swap is legal only when a subarray’s property is a sum of independent per-unit terms (sum, min-as-minimum-indicator, XOR-per-bit, distinctness-per-char). The instant the property depends on a combination of units — “at least k pairs”, “max − min ≤ k” — the terms stop being independent and the swap is invalid (see §9). ─────────────────────────────────────────────────

2. Foundation: Element Containment Formula

Question: For an array of length n, how many subarrays contain element at index i?

A subarray [l..r] contains index i when l <= i and r >= i.

Choices for l: 0, 1, ..., i       → (i + 1) choices
Choices for r: i, i+1, ..., n-1   → (n - i) choices

Subarrays containing nums[i] = (i + 1) × (n - i)

Visual:

Array:  [a, b, c, d, e]    n = 5
              ^
              i = 2

l can be: 0, 1, 2     → 3 choices  (i + 1)
r can be: 2, 3, 4     → 3 choices  (n - i)
Total subarrays containing c: 3 × 3 = 9

The 9 subarrays: [c], [b,c], [a,b,c], [c,d], [b,c,d], [a,b,c,d],
                 [c,d,e], [b,c,d,e], [a,b,c,d,e]

This is the building block for everything below.

★ Insight ───────────────────────────────────── (i+1) × (n-i) is just “count the left endpoints × count the right endpoints” — a subarray is pinned down entirely by its (l, r) pair, and l ranges freely over [0, i] while r ranges over [i, n-1]. Multiplying independent choice-counts is the whole formula. Every harder variant only narrows those ranges: a min-problem clips l to “after the previous smaller” and r to “before the next smaller”; a distinct-char problem clips to “after previous same char” and “before next same char”. Same skeleton left_choices × right_choices — different fences. ─────────────────────────────────────────────────

Application: Sum of All Subarray Sums

Problem: Find the sum of sums of all subarrays.

Brute force: O(n^2) -- enumerate all subarrays.

Contribution: Each nums[i] appears in (i+1) × (n-i) subarrays:

def sum_of_subarray_sums(nums):
    n = len(nums)
    total = 0
    for i in range(n):
        total += nums[i] * (i + 1) * (n - i)
    return total

O(n). That’s it.

Verification

nums = [1, 2, 3]

Subarrays: [1]=1, [2]=2, [3]=3, [1,2]=3, [2,3]=5, [1,2,3]=6
Total = 1 + 2 + 3 + 3 + 5 + 6 = 20

Contribution:
  nums[0]=1: appears in (0+1)×(3-0) = 3 subarrays → 1 × 3 = 3
  nums[1]=2: appears in (1+1)×(3-1) = 4 subarrays → 2 × 4 = 8
  nums[2]=3: appears in (2+1)×(3-2) = 3 subarrays → 3 × 3 = 9
  Total = 3 + 8 + 9 = 20 ✓

3. Monotonic Stack + Contribution: Sum of Subarray Minimums

Problem: LC 907 -- Sum of Subarray Minimums

For each nums[i], find: in how many subarrays is it the minimum?

You need the span where nums[i] dominates as the minimum:

• left[i]: number of consecutive elements to the left where nums[i] is still the min (distance to previous smaller element)
• right[i]: number of consecutive elements to the right where nums[i] is still the min (distance to next smaller-or-equal element)

nums:    [3, 1, 2, 4]
          0  1  2  3

For nums[2] = 2:
  left boundary:  index 1 (value 1 < 2)
  left[2] = 2 - 1 = 1   (only index 2 itself)
  right boundary: index 4 (end of array)
  right[2] = 4 - 2 = 2  (indices 2, 3)

  Subarrays where 2 is minimum: 1 × 2 = 2
    → [2], [2, 4]

Why Strict < on One Side, <= on the Other?

To avoid double counting with duplicates:

nums = [2, 2]

If both use strict <:
  nums[0]: left=1, right=2 → 2 subarrays
  nums[1]: left=2, right=1 → 2 subarrays
  Total = 4, but there are only 3 subarrays!

  Subarray [2,2] is counted TWICE (once by each 2).

Fix: Use strict < for previous, and <= for next.
  nums[0]: left=1, right=1 → 1   (only [2] at index 0)
  nums[1]: left=2, right=1 → 2   ([2] at index 1, and [2,2])
  Total = 3 ✓

Implementation

def sumSubarrayMins(nums):
    n = len(nums)
    MOD = 10**9 + 7

    # Previous Less Element (strictly less)
    left = [0] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)

    # Next Less-or-Equal Element
    right = [0] * n
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)

    return sum(nums[i] * left[i] * right[i] for i in range(n)) % MOD

Time: O(n), Space: O(n)

Walkthrough

nums = [3, 1, 2, 4]

Previous Less (strict <):
  i=0: stack=[], left[0]=0+1=1.     stack=[0]
  i=1: pop 0 (3>=1), stack=[], left[1]=1+1=2.  stack=[1]
  i=2: 1<2, stop. left[2]=2-1=1.    stack=[1,2]
  i=3: 2<4, stop. left[3]=3-2=1.    stack=[1,2,3]

  left = [1, 2, 1, 1]

Next Less-or-Equal (strict > in pop condition):
  i=3: stack=[], right[3]=4-3=1.     stack=[3]
  i=2: 4>2, pop 3. stack=[], right[2]=4-2=2.  stack=[2]
  i=1: 2>1, pop 2. stack=[], right[1]=4-1=3.  stack=[1]
  i=0: 1 not > 3, stop. right[0]=1-0=1. stack=[0,1]

  right = [1, 3, 2, 1]

Contributions:
  3 × 1 × 1 = 3
  1 × 2 × 3 = 6
  2 × 1 × 2 = 4
  4 × 1 × 1 = 4
  Total = 17

Verify: subarrays and their mins:
  [3]=3, [1]=1, [2]=2, [4]=4, [3,1]=1, [1,2]=1, [2,4]=2, [3,1,2]=1, [1,2,4]=1, [3,1,2,4]=1
  Sum = 3+1+2+4+1+1+2+1+1+1 = 17 ✓

★ Insight ───────────────────────────────────── The strict-< on one side, <= on the other is the single subtlety that makes duplicate values behave. If both boundaries used strict comparison, a subarray of equal minimums like [2,2] would be claimed by both 2s as “the subarray where I am the minimum” and counted twice. Breaking the tie asymmetrically — “I own the subarray only if I’m the leftmost occurrence of the minimum” (strict on the previous side, non-strict on the next) — assigns every subarray to exactly one owner. This tie-break rule recurs everywhere spans partition a range: it is why NGE/NLE templates flip one comparison, not both. ─────────────────────────────────────────────────

4. Sum of Subarray Ranges: Dual Contribution

Problem: LC 2104 -- Sum of Subarray Ranges

Sum of (max - min) over all subarrays = Σ(max) - Σ(min) over all subarrays.

Apply contribution counting twice: once for minimums (same as LC 907), once for maximums (flip the comparisons).

def subArrayRanges(nums):
    n = len(nums)

    def contribution(compare_pop, compare_pop_right):
        """
        compare_pop: condition to pop for left pass
        compare_pop_right: condition to pop for right pass
        """
        left = [0] * n
        right = [0] * n

        stack = []
        for i in range(n):
            while stack and compare_pop(nums[stack[-1]], nums[i]):
                stack.pop()
            left[i] = i - stack[-1] if stack else i + 1
            stack.append(i)

        stack = []
        for i in range(n - 1, -1, -1):
            while stack and compare_pop_right(nums[stack[-1]], nums[i]):
                stack.pop()
            right[i] = stack[-1] - i if stack else n - i
            stack.append(i)

        return sum(nums[i] * left[i] * right[i] for i in range(n))

    # Sum of maximums: pop when stack top <= current (finding previous greater)
    sum_max = contribution(lambda a, b: a <= b, lambda a, b: a < b)
    # Sum of minimums: pop when stack top >= current (finding previous smaller)
    sum_min = contribution(lambda a, b: a >= b, lambda a, b: a > b)

    return sum_max - sum_min

Time: O(n), Space: O(n)

5. Per-Character Contribution: Unique Characters

Problem: LC 828 -- Count Unique Characters of All Substrings

For each character occurrence, count subarrays where it is unique (appears exactly once).

A character at index j is unique in [l..r] if the previous same character is before l and the next same character is after r.

s = "ABA"
     0 1 2

For A at index 0:
  prev same char: -1 (none)
  next same char: 2
  l choices: l in [0, 0] → (-1, 0) exclusive → 0 - (-1) = 1
  r choices: r in [0, 1] → (0, 2) exclusive → 2 - 0 = 2
  Contribution: 1 × 2 = 2   → subarrays [A], [AB]

For B at index 1:
  prev same char: -1 (none)
  next same char: 3 (none)
  l choices: 1 - (-1) = 2
  r choices: 3 - 1 = 2
  Contribution: 2 × 2 = 4   → [B], [AB], [BA], [ABA]

For A at index 2:
  prev same char: 0
  next same char: 3 (none)
  l choices: 2 - 0 = 2
  r choices: 3 - 2 = 1
  Contribution: 2 × 1 = 2   → [BA], [A]

Total = 2 + 4 + 2 = 8

def uniqueLetterString(s):
    n = len(s)
    # For each char, track indices where it appears
    last = {}   # char → list of indices
    for i, c in enumerate(s):
        last.setdefault(c, [-1]).append(i)
    for c in last:
        last[c].append(n)  # sentinel

    total = 0
    for c in last:
        indices = last[c]
        for k in range(1, len(indices) - 1):
            prev_idx = indices[k - 1]
            curr_idx = indices[k]
            next_idx = indices[k + 1]
            total += (curr_idx - prev_idx) * (next_idx - curr_idx)
    return total

Time: O(n), Space: O(n)

Variant: LC 2262 -- Total Appeal of a String

Appeal = number of distinct characters in a substring. Each character contributes 1 to appeal for every subarray where it appears at least once.

For character at index i with previous occurrence at prev:

Subarrays where this occurrence is the FIRST of its character:
  l choices: prev+1, prev+2, ..., i  → (i - prev)
  r choices: i, i+1, ..., n-1        → (n - i)
  Contribution: (i - prev) × (n - i)

def appealSum(s):
    n = len(s)
    prev = {}  # char → last seen index
    total = 0
    for i, c in enumerate(s):
        p = prev.get(c, -1)
        total += (i - p) * (n - i)
        prev[c] = i
    return total

O(n) time, O(26) space. Elegantly simple.

★ Insight ───────────────────────────────────── For character problems the fences are the same-character neighbors, not smaller/greater ones. A char occurrence “owns” a subarray for uniqueness when the previous identical char sits left of l and the next identical char sits right of r → (i − prev) × (next − i). LC 2262 (appeal) is a one-line collapse of this: instead of both neighbors, only prev matters because you count each occurrence as the first of its kind in a subarray, so (i − prev) × (n − i). Recognizing that “unique here” and “first-occurrence here” are the same fencing idea with one fence dropped is what turns a monotonic-stack problem into a single running-dictionary pass. ─────────────────────────────────────────────────

6. Bit-Level Contribution

Problem: LC 477 -- Total Hamming Distance

For each bit position, count elements with that bit set vs unset. Each (set, unset) pair contributes 1 to Hamming distance.

def totalHammingDistance(nums):
    total = 0
    n = len(nums)
    for bit in range(30):
        ones = sum(1 for x in nums if x & (1 << bit))
        zeros = n - ones
        total += ones * zeros
    return total

Time: O(30n), Space: O(1)

★ Insight ───────────────────────────────────── Bits are the cleanest “independent units” of all: a number’s bits never interact, so you decompose the whole problem into 30 (or 64) parallel one-bit problems and sum the answers. For Hamming distance, bit b contributes ones × zeros — every set/unset pair differs in that bit, and pairs are independent across bits. For XOR-of-subarrays the per-bit trick is prefix-parity: a subarray’s bit is 1 iff an odd number of that bit falls inside, i.e. iff the two enclosing prefix parities differ, so the count is count[0] × count[1]. When you see “sum/xor/hamming over all …”, split by bit first — the per-bit subproblem is almost always trivial. ─────────────────────────────────────────────────

Problem: Sum of XOR of All Subarrays

For each bit position b and index i, nums[i]’s bit b contributes to the XOR of subarray [l..r] only if the count of set bits at position b in [l..r] is odd.

Use prefix XOR to count:

def sum_xor_all_subarrays(nums):
    total = 0
    n = len(nums)
    for bit in range(30):
        # prefix[i] = XOR of bit b for nums[0..i-1]
        # Count prefix values where bit b is 0 vs 1
        count = [1, 0]  # count[0]=1 for empty prefix
        prefix_bit = 0
        for num in nums:
            prefix_bit ^= (num >> bit) & 1
            count[prefix_bit] += 1
        # Subarrays with odd count = pairs (prefix=0, prefix=1)
        total += count[0] * count[1] * (1 << bit)
    return total

Bit-width assumption: range(30) assumes every value fits in 30 bits (0 ≤ nums[i] < 2^30 ≈ 1.07e9). For larger values (e.g. up to 2^63) widen the loop to range(64).

Trace on [1, 2, 3]

A subarray’s XOR is odd-count-per-bit. Enumerate to get the target, then rebuild it bit by bit.

Subarrays: [1]=1, [2]=2, [3]=3, [1,2]=3, [2,3]=1, [1,2,3]=0
Total XOR sum = 1 + 2 + 3 + 3 + 1 + 0 = 10

Per-bit via prefix XOR (count[v] = how many prefixes have this bit = v; empty prefix seeds count[0]=1). A subarray [l..r] has an odd bit count iff prefix[l] and prefix[r+1] differ, so its contribution count is count[0] × count[1]:

bit 0 (value 1): nums bit0 = [1, 0, 1]
  start count=[1,0], prefix=0
  1 → prefix=1  count=[1,1]
  2 → prefix=1  count=[1,2]   (bit0 of 2 is 0, no flip)
  3 → prefix=0  count=[2,2]
  pairs = count[0]×count[1] = 2×2 = 4  → contributes 4 × 1 = 4

bit 1 (value 2): nums bit1 = [0, 1, 1]
  start count=[1,0], prefix=0
  1 → prefix=0  count=[2,0]   (bit1 of 1 is 0)
  2 → prefix=1  count=[2,1]
  3 → prefix=0  count=[3,1]
  pairs = 3×1 = 3  → contributes 3 × 2 = 6

Total = 4 + 6 = 10 ✓   (matches the brute-force sum)

7. Pair Contribution

For a pair of indices (i, j) with i < j, a subarray [l..r] contains both when l <= i and r >= j:

Count of subarrays containing pair (i, j) = (i + 1) × (n - j)

Application: Total Equal Pairs Across All Subarrays

def total_equal_pairs(nums):
    n = len(nums)
    from collections import defaultdict

    # For fixed j, sum the contribution (i+1) × (n-j) over all previous i
    # with nums[i] == nums[j]. Track a running sum of (i+1) per value so each
    # j is O(1): total += (running sum of (i+1) for this value) × (n - j).
    total = 0
    prefix_sum = defaultdict(int)  # value → running sum of (i+1)
    for j in range(n):
        total += prefix_sum[nums[j]] * (n - j)
        prefix_sum[nums[j]] += j + 1
    return total

Time: O(n), Space: O(n)

8. Subsequence Contribution

Problem: LC 891 -- Sum of Subsequence Widths

Width = max - min of a subsequence. For each element, count subsequences where it’s the max minus where it’s the min.

After sorting: For nums[i] in sorted order:

• Subsequences where nums[i] is the max: any subset of nums[0..i-1] plus nums[i] → 2^i subsequences
• Subsequences where nums[i] is the min: any subset of nums[i+1..n-1] plus nums[i] → 2^(n-1-i) subsequences

def sumSubseqWidths(nums):
    MOD = 10**9 + 7
    nums.sort()
    n = len(nums)
    total = 0
    for i in range(n):
        # As max: contributes +nums[i] × 2^i
        # As min: contributes -nums[i] × 2^(n-1-i)
        total += nums[i] * (pow(2, i, MOD) - pow(2, n - 1 - i, MOD))
        total %= MOD
    return total % MOD

Time: O(n log n) for sort, Space: O(1)

9. When Contribution Counting Does NOT Work

Contribution counting works when contributions are independent and additive. It fails when the problem requires a threshold or interaction between contributions within the same subarray.

The Dividing Line

Ask: “Can I compute each unit’s contribution independently of other units?”

• YES → Contribution counting. Each element/pair/bit contributes some value × (number of subarrays containing it).
• NO → The answer depends on the combination of elements within a subarray. Use sliding window, DP, or segment tree instead.

The “At Least k” Trap

For LC 2537 (Count Good Subarrays, at least k equal pairs):

You CAN count total equal pairs across ALL subarrays using contribution: each pair (i,j) appears in (i+1) × (n-j) subarrays.

But you CANNOT count subarrays with at least k pairs, because that requires knowing how many pairs are simultaneously inside each specific subarray. The contributions interact -- you need sliding window for that.

★ Insight ───────────────────────────────────── The litmus test: does the property factor into a sum of per-unit terms, or does it involve a comparison/threshold across units? “Total equal pairs” factors — each pair (i,j) contributes its containment count regardless of the others, so contribution counting works. “At least k equal pairs” does not factor — whether a subarray qualifies depends on the joint count of all its pairs, an interaction. Same trap hides in “min > X” (needs the whole window’s min), “≤ k distinct” (needs the window’s distinct set), “range ≤ k” (needs both extremes at once). Additive → contribution counting, O(n). Threshold/interaction → sliding window / DP / segment tree. Misreading this is the one way to apply the technique to a problem it silently gets wrong. ─────────────────────────────────────────────────

10. Pattern Recognition Cheat Sheet

Decision Flowchart

Problem asks for aggregate over ALL subarrays?
├── YES → Can each element/pair contribute independently?
│   ├── YES → CONTRIBUTION COUNTING
│   │   ├── Involves min/max? → + Monotonic Stack
│   │   ├── Involves distinct chars? → + Last occurrence tracking
│   │   └── Involves bits? → + Bit decomposition
│   └── NO (threshold / k constraint) → Sliding Window or DP
└── NO (single subarray: longest, count satisfying X) → Sliding Window / DP / Binary Search

11. Problem Roadmap

Tier 1 -- Direct Element Contribution

Tier 2 -- Monotonic Stack + Contribution

Tier 3 -- Per-Character / Occurrence Contribution

Tier 4 -- Bit-Level & Pair Contribution

Tier 5 -- Advanced Contribution

Summary

The core skill is always the same: stop thinking about subarrays, start thinking about what each element (or pair, or bit) contributes to the final answer.

Total = Σ (value of unit) × (number of subarrays/subsets containing that unit)

THREE MOVES BEHIND EVERY CONTRIBUTION PROBLEM

1. PICK THE UNIT     Element? pair? bit? character occurrence? The unit is
                     whatever makes the property a SUM of independent terms.

2. FENCE THE SPAN    Count subarrays/subsets containing the unit:
                       plain element   → (i+1) × (n-i)
                       as minimum       → (i-PLE) × (NLE-i)   [monotonic stack]
                       as distinct char → (i-prev) × (next-i)  [last occurrence]
                       across a pair    → (i+1) × (n-j)
                       in a subset       → powers of 2 after sorting

3. CHECK ADDITIVITY  Does the property factor into per-unit terms? YES → sum
                     value×span, O(n). NO (threshold / "at least k" / range≤k)
                     → wrong tool; use sliding window / DP / segment tree.

Master the containment formula (i+1) × (n-i), learn to combine it with monotonic stacks for min/max problems and with last-occurrence tracking for character problems, and you’ll solve an entire class of “aggregate over all subarrays” problems in O(n).

Self-Test

Answer these from memory, out loud or on paper, before looking. Recognition is not recall: rereading an explanation feels like knowing, and it is not. A question you cannot answer cold names the exact section to revisit — you do not need to reread the guide.

1. State the summation swap in one line, and the condition that makes it legal.

2. How many subarrays contain index i in an array of length n, and why?

3. For “sum of subarray minimums”, what does each element need, and how do you get it?

4. Why must the tie-breaking be asymmetric in that problem?

5. How does per-bit decomposition turn an XOR-sum problem into counting?

6. Give a problem where contribution counting does not apply, and say why.

7. Is the per-element cost really O(1)?

See Also

• Stack & Queue §2 — the monotonic stack primitive that §3-4 depend on. Learn it there first if the strict-vs-non-strict tie-breaking feels arbitrary.
• Edge Contribution & Rerooting — the same mental flip on a tree: count what each edge contributes instead of enumerating node pairs.
• Bitmask Techniques — background for the per-bit decomposition in §6.
• Prefix Sum §7 — prefix XOR, the tool §6 uses to make each bit’s count O(n).
• Sliding Window — where to go when §9 tells you contribution counting does not apply, because the constraint is a threshold over the window rather than an independent per-element property.
• Pattern Decision Map — the router: which technique does a cold problem call for?
• Pattern Mastery Program — the spaced-repetition schedule, mastery checklist, and drill formats that turn reading into recall.

Pattern mastered — stop enumerating subarrays; count what each unit contributes and let the total assemble itself.