PATTERN 18: Contribution Technique (Count-Per-Element Thinking)

D

Qubits of DPK

April 11, 2026

Core DSA

Core Idea (lock this)

“Instead of iterating over all subarrays,
count
You are not enumerating ranges.
You are assigning responsibility to elements.
If prefix sums reduce recomputation,
Contribution technique removes enumeration entirely.

How to Recognize This Pattern (CRITICAL)

You should instantly think Contribution Technique when:
  • The problem asks for:
  • Brute force is:
  • Each element:
Trigger phrases:
  • “sum of subarray …”
  • “total strength / total score”
  • “consider all subarrays”
  • “for every possible range”

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (Mathematical Contribution Awareness)

Goal: Stop enumerating ranges.
  1. #
    Sum of All Subarrays (Mathematical formula) — GFG
  2. #
    Sum of All Odd-Length Subarrays — LC 1588
  3. #
    Total Appeal of a String (Intro idea) — LC 2262
  4. #
    Count Subarrays Where Max = K (basic reasoning) — LC 795
  5. #
    Subarray Ranges (conceptual difference view) — LC 2104
  6. #
    Number of Subarrays With Bounded Maximum — LC 795
  7. #
    Count of Substrings With Unique Characters — LC 828
  8. #
    Total Strength of Wizards (understanding idea) — LC 2281
  9. #
    Sum of Subarray Minimums (intro) — LC 907
  10. #
    Sum of Distances in Tree (intro) — LC 834
After these you must instinctively think:
How many subarrays include index i?
Which equals:
(i - left) * (right - i)

️ MEDIUM (Monotonic Boundaries + Element Responsibility)

Now it becomes mechanical.
  1. #
    Sum of Subarray Minimums — LC 907
  2. #
    Sum of Subarray Ranges — LC 2104
  3. #
    Total Appeal of a String (optimized) — LC 2262
  4. #
    Count Subarrays With Fixed Bounds — LC 2444
  5. #
    Total Strength of Wizards — LC 2281
  6. #
    Number of Valid Subarrays — LC 1063
  7. #
    Count Subarrays Where Max Appears Exactly Once — GFG
  8. #
    Count Subarrays With Exactly K Odd Numbers (contribution view) — LC 1248
  9. #
    Count Good Subarrays — LC 2537
  10. #
    Minimum Cost to Make Array Non-decreasing (contribution view) — GFG
This section forces:
  • Strict vs non-strict boundaries
  • Equal element handling
  • Previous less / next less logic
  • Combining stack + prefix

HARD (Full Contribution Mastery)

Now we combine multiple layers.
  1. #
    Total Strength of Wizards (full optimized) — LC 2281
  2. #
    Maximum Subarray Min-Product — LC 1856
  3. #
    Sum of Total Strength of Wizards (derivation approach) — LC 2281 variant
  4. #
    Count Subarrays With Median K — LC 2488
  5. #
    Maximum Score of a Good Subarray — LC 1793
  6. #
    Number of Subarrays With LCM Equal to K — LC 2470
  7. #
    Count Subarrays With Score < K — LC 2302
  8. #
    Sum of All Subsequence Widths — LC 891
  9. #
    Count Subarrays Where Max Appears Exactly K Times — LC 2062
  10. #
    Sum of Distances — LC 2615
Now HARD demands:
  • Stack boundaries
  • Prefix-of-prefix integration
  • Modulo arithmetic care
  • Mathematical clarity

Pattern 18 is now LOCKED

The ONE Rule That Wins Interviews

Always be able to answer:
“For how many subarrays is this element the
If you can answer that clearly,
the solution writes itself.

Common Interview Mistakes

  • Enumerating subarrays explicitly
  • Forgetting strict vs non-strict boundaries
  • Mixing min and max logic
  • Missing equal elements handling

INTERVIEW REVISION CARD — Pattern 18

1️⃣ Pattern in One Line

"Instead of iterating all subarrays, ask: how many subarrays is this element responsible for?"

2️⃣ Recognize It When...

  • Sum/count over ALL subarrays needed
  • Trigger words: "sum of subarray minimums/maximums", "total contribution", "aggregate over all ranges"
  • Brute force is O(N²) or O(N³)
  • Each element independently affects many subarrays

3️⃣ Don't Confuse With...

  • Prefix Sum (P3) → prefix answers one range query; contribution counts all ranges per element
  • Monotonic Stack (P8) → stack finds nearest; contribution technique USES stack to count ranges
  • DP (P13) → DP optimizes choices; contribution counts responsibilities

4️⃣ Approach in 3 Steps

  1. #
    For each element, find: left boundary (previous greater/smaller) and right boundary (next greater/smaller)
  2. #
    Count subarrays where this element is the min/max: (i - left) × (right - i)
  3. #
    Multiply element value by its count and accumulate

5️⃣ Invariant to Maintain

"For element at index i, (i - left) × (right - i) always equals the exact number of subarrays where arr[i] is the chosen minimum/maximum."

6️⃣ Complexity to Justify

  • Time: O(N) — monotonic stack finds boundaries in O(N)
  • Space: O(N) — stack storage
  • Why: Each element's contribution computed independently in O(1) after preprocessing

7️⃣ Edge Cases to Always Check

  • Duplicate elements — use strict inequality on one side to avoid double counting
  • Single element array — contributes to exactly 1 subarray
  • All elements same — every element contributes equally
  • Modular arithmetic for large sums
  • Empty array

8️⃣ One Line to Say in Interview

"Instead of enumerating all subarrays, I'll compute each element's contribution — how many subarrays it's the min/max of — using a monotonic stack in O(N)."