Frequency Contribution (How Each Element's Frequency Contributes to Total Result)

Frequency contribution asks how changing one element’s multiplicity shifts a global score—subtract old contribution, add new, instead of recomputing from scratch.

Why this shows up in the real world

Streaming metrics update rolling uniqueness; spreadsheet recalc adjusts aggregates when one cell edits a bucket count.

Core idea (explained for students)

Maintain aggregate f plus per-key counts. On update: f -= old_term(key), change count, f += new_term(key). Works for sums of squares, XOR masks tied to parity, etc., when algebra is local.

Try this in Python

def score_after_updates(nums: list[int], updates: list[tuple[int, int]]) -> list[int]:
    from collections import Counter

    c = Counter(nums)

    def uniq() -> int:
        return sum(1 for v in c.values() if v > 0)

    out = []
    for idx, newv in updates:
        old = nums[idx]
        c[old] -= 1
        c[newv] += 1
        nums[idx] = newv
        out.append(uniq())
    return out


print(score_after_updates([1, 2, 1], [(0, 2)]))

Common mistakes

• Forgetting to clamp counts at zero before removing contribution.
• Non-linear stats where contribution is not separable—cannot use trick.

Key takeaways

• Write contribution(cnt) as a tiny pure function and unit-test it.
• Pair with sliding window for substring problems.