Build count[x]=|{i:a[i]=x}|. Compute later results only from keys and counts; consuming an instance decrements its count and may delete the key at zero.
Recognition signals
Order is irrelevant and only multiplicities affect the answer.
Two multisets must be compared.
The key domain is finite or the distinct-key count is much smaller than n.
The task asks for complements, highest frequency, unique values, or reconstruction by counts.
False friends
Signal
Why it is different
Adjacency order matters
A frequency map discards positions and arrangement, so it cannot recover sequence patterns.
Huge sparse numeric domain
Do not allocate through the maximum value; use hashing or coordinate compression.
Core invariant
After scanning a prefix, count[x] equals x's exact multiplicity there; counts stay nonnegative and their sum equals inserted items minus consumed items.
State, transition, and processing order
Item
Definition
State
An array or dictionary key→count, plus optional distinct count, maximum frequency, or frequency buckets.
Transition
On input x increment count[x]; on matching or consumption verify positivity, decrement, and optionally remove a zero key.
Frontier / order
Scanned items are compressed into counts, and the key domain replaces input indexes as the next iteration domain.
Python skeleton
def multiset_equal(left, right):
if len(left) != len(right):
return False
count = {}
for value in left:
count[value] = count.get(value, 0) + 1
for value in right:
remaining = count.get(value, 0)
if remaining == 0:
return False
if remaining == 1:
del count[value]
else:
count[value] = remaining - 1
return not count
Correctness sketch
After the first pass, count is an exact multiset representation of left.
Each right item must consume one equal instance; a missing instance immediately proves inequality.
With equal lengths, complete consumption leaves an empty map exactly when every key has equal multiplicity.
Complexity
Time
Space
Parameters
Expected O(n+m)
O(k)
n and m are lengths and k is distinct keys; a small finite-domain array provides deterministic O(1) access.
Edge cases
Empty input has an empty table.
Use a dictionary for negative or composite hashable keys.
Verify a positive count before repeated consumption.
Floating-point keys require care around precision and NaN equality.
Error patterns
Pattern
Why it fails / fix
Using a set and losing multiplicity
{a,a,b} and {a,b,b} have the same set but different multisets.
Leaving zero keys while using map length
If distinct count is dictionary size, delete zero-frequency keys.
Allocating an uncontrolled value-domain array
A huge max-min span wastes memory; use hashing.
Selection and exclusion rules
When only multiplicities matter, sketch a frequency map first.
Use an array for a small contiguous key domain and a dictionary otherwise.
When original positions matter, frequency is only auxiliary state, not a replacement.