Loading…

mediumArraysFrequently asked

Frequency Queries

Q: How do you solve Frequency Queries using the Brute Force — Single Map, Scan on Query 3 approach?

When to use it: State it to show the inserts/deletes are easy, then note that scanning all counts per type-3 query is the bottleneck. Keep a single map `valueCount` from value to its current occurrence count. Inserts increment it, deletes decrement it (guarding against going below 0). **Why the inserts/deletes are fine.** Each is a single hash-map update — O(1) average. Nothing about maintaining individual counts is slow. **Where it falls apart.** A type-3 query asks 'does *any* value have count exactly x?'. With only `valueCount`, the only way to answer is to walk every entry and check whether its count equals x. That's O(d) per type-3 query, where d is the number of distinct values. If a large fraction of the q queries are type 3, the total balloons to O(q·d) — for q, d near 10⁵ that's ~10¹⁰ operations and times out. **The redundancy to remove.** Across consecutive type-3 queries the count distribution barely changes — yet we re-scan it from scratch every time. Maintaining a running tally of 'how many values have each frequency' eliminates the rescans, making each type-3 query O(1). Time complexity: O(q × d) where d = distinct values. Space complexity: O(d).

Arrays & Hashing · 28 of 83 · 10 min

Process a sequence of queries, each of one of three types:

1 x — insert the value x into the data structure.
2 x — delete one occurrence of x (do nothing if x is not present).
3 x — check whether any integer currently appears exactly x times; output 1 if so, 0 otherwise.

Return the list of answers, one per type-3 query, in order.

In plain English

Type-3 queries ask about the *set of current frequencies*, not about any one value. Recomputing that set each time is O(n). Instead, keep a running map from each frequency to how many values currently have it, updated on every insert/delete, so the question becomes one map lookup.

Examples

Example 1

Input: queries = [[1,5],[1,6],[3,2],[1,10],[1,10],[1,6],[2,5],[3,2]]
Output: [0, 1]
Note: First 3-2: no value yet appears twice → 0. By the second 3-2, both 10 (×2) and 6 (×2) appear twice → 1.

Example 2

Input: queries = [[1,1],[2,2],[3,2],[1,1],[1,1],[2,1],[3,2]]
Output: [0, 1]
Note: First 3-2: value 1 appears once, nothing has freq 2 → 0. After two more inserts and one delete, 1 appears twice → 1.

Example 3

Input: queries = [[3,1],[1,7],[3,1]]
Output: [0, 1]
Note: Initially empty → 0. After inserting 7 once, a value has frequency 1 → 1.

Constraints

1 ≤ number of queries ≤ 10⁵
Query type ∈ {1, 2, 3}
0 < x ≤ 10⁹ for the value argument
Deleting an absent value is a no-op
Type-3 x is a frequency to test (x ≥ 1 in practice)

Clarifying questions4First question: Does query type 3 ask about a value or a frequency?Explore questions

Q1.Does query type 3 ask about a value or a frequency?
A frequency: 'is there any value that occurs exactly x times right now?' Misreading this as 'how many times does value x appear' is the classic trap.
Q2.What happens when I delete a value that isn't present?
Nothing — it's a no-op. You must guard against decrementing a count below 0.
Q3.Can the same value be inserted many times?
Yes — that's the point. valueCount[x] grows with each insert and shrinks with each delete.
Q4.Could x in a type-3 query exceed every current count?
Yes — then freqOfFreq[x] is 0 (absent), so you output 0. A defaultdict / getOrDefault handles it cleanly.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Process insert / delete / 'does any value have frequency exactly x' queries. Keep TWO hash maps in lockstep: valueCount (value → how many times it appears) and freqOfFreq (a frequency → how many distinct values currently have that frequency). Every insert/delete adjusts both maps; the existence query becomes a single O(1) lookup freqOfFreq[x] > 0 instead of scanning all counts.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise query type 3 asks about frequencies (not values) and add a second 'frequency of frequencies' map so it's O(1), instead of scanning all counts.

Where candidates slip

Using only valueCount and scanning its values on every type-3 query (O(n) per query → O(n²) overall), or letting the two maps drift out of sync on delete.

How to stand out

Name the 'frequency of frequencies' map, keep both maps in sync with a decrement-old/increment-new step, and guard delete so counts never go negative and 0 buckets are never stored.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Single Map, Scan on Query 3	`O(q × d) where d = distinct values`	`O(d)`	State it to show the inserts/deletes are easy, then note that scanning all counts per type-3 query is the bottleneck.	Read
2	Two Hash Maps — Frequency of Frequencies (Optimal)Optimal	`O(1) per query, O(q) total`	`O(d)`	The answer they want. Phrase it as 'keep a second map: frequency → how many values have that frequency, so query 3 is O(1)'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewQuery (type, x)type?1 insert2 deleteExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Single Map, Scan on Query 3

TimeO(q × d) where d = distinct valuesSpaceO(d)

State it to show the inserts/deletes are easy, then note that scanning all counts per type-3 query is the bottleneck.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Inserts and deletes are trivial with one map: valueCount[x] up or down. The cost is hidden in the type-3 query.

2Hint 2Explore hint

For a type-3 query, you need to know whether ANY value has count exactly x. With only valueCount, how do you find out?

3Hint 3Explore hint

You'd scan every entry of valueCount looking for a count equal to x — O(d) per query. With up to 10⁵ queries that's O(q·d), too slow when many are type 3.

A · Core idea

Keep a single map valueCount from value to its current occurrence count. Inserts increment it, deletes decrement it (guarding against going below 0).

Why the inserts/deletes are fine. Each is a single hash-map update — O(1) average. Nothing about maintaining individual counts is slow.

Where it falls apart. A type-3 query asks 'does any value have count exactly x?'. With only valueCount, the only way to answer is to walk every entry and check whether its count equals x. That's O(d) per type-3 query, where d is the number of distinct values. If a large fraction of the q queries are type 3, the total balloons to O(q·d) — for q, d near 10⁵ that's ~10¹⁰ operations and times out.

The redundancy to remove. Across consecutive type-3 queries the count distribution barely changes — yet we re-scan it from scratch every time. Maintaining a running tally of 'how many values have each frequency' eliminates the rescans, making each type-3 query O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

queries = [[1,1],[1,1],[3,2],[3,5]]

Hash-map state

state

ValueIndex / state

1→ 2

Continue scanning

value 1 has count 2

Final result[1, 0]

C · Code with teaching comments

Reference implementation previewpublic List<Integer> freqQuery(int[][] queries) { Map<Integer, Integer> valueCount = new HashMap<>(); List<Integer> out = new ArrayList<>(); for (int[] q : queries) { int type = q[0], x = q[1];Explore the full code

solution.javaJava

Brute Force — Single Map, Scan on Query 3 — reference

3 teaching notes

1
public List<Integer> freqQuery(int[][] queries) {
2
    Map<Integer, Integer> valueCount = new HashMap<>();
3
    List<Integer> out = new ArrayList<>();
4
    for (int[] q : queries) {
5
        int type = q[0], x = q[1];
6
        if (type == 1) {
7
            // Insert: add 1 to x's count, creating the entry if new.
8
            valueCount.merge(x, 1, Integer::sum);
9
        } else if (type == 2) {
10
            // Delete: drop the count by 1, removing the key entirely at 0 so it can't
11
            // be falsely matched.
12
            valueCount.computeIfPresent(x, (k, v) -> v > 1 ? v - 1 : null);
13
        } else {
14
            // Type 3: containsValue scans ALL counts — O(d), the bottleneck.
15
            boolean found = valueCount.containsValue(x);
16
            out.add(found ? 1 : 0);
17
        }
18
    }
19
    return out;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(q × d) where d = distinct values timeO(d) spaceOpen the invariant and proofExplore the proof

The slow part is recomputing a global fact (which frequencies are present) on every query when it changes by at most one per insert/delete. Maintaining that fact incrementally — a second map — is the leap to O(1) queries.

ComplexityO(q × d) where d = distinct values time, O(d) space — Insert/delete are O(1) with one hash map. Each type-3 query scans all d distinct values to test for count == x → O(d). With q queries, the worst case (many type-3) is O(q·d), up to ~10¹⁰.

E · Edge cases and pitfalls3Using containsValue / x in .values() on every type-3 query — O(d) each, O(q·d) total.Explore edge cases

Pitfalls

Using containsValue / x in .values() on every type-3 query — O(d) each, O(q·d) total.
Leaving a value at count 0 in the map — containsValue(0) could falsely match.
Reading type-3 x as a value to look up rather than a frequency to test.

03.2

Approach 2 of 2 · Optimal

Two Hash Maps — Frequency of Frequencies (Optimal)

TimeO(1) per query, O(q) totalSpaceO(d)

The answer they want. Phrase it as 'keep a second map: frequency → how many values have that frequency, so query 3 is O(1)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you tracked, for each frequency value, how many distinct numbers currently have that frequency? Then 'any value with frequency x?' is a single lookup.

2Hint 2Explore hint

Keep valueCount (value → count) AND freqOfFreq (count → number of values with that count). On insert/delete, move a value between frequency buckets: decrement its old bucket, increment its new one.

3Hint 3Explore hint

Type 3 x: return 1 if freqOfFreq[x] > 0 else 0. Never store a 0-count bucket, and never let valueCount go negative on a delete.

A · Core idea

Run two maps in lockstep:

valueCount: value → how many times it currently appears.
freqOfFreq: a frequency → how many distinct values currently have exactly that frequency.

freqOfFreq is the 'frequency of frequencies' map, and it's what makes type-3 queries O(1).

Insert x. Let f = valueCount[x] (0 if absent). The value is leaving frequency bucket f and entering f+1, so: decrement freqOfFreq[f] (only if f > 0), set valueCount[x] = f + 1, and increment freqOfFreq[f+1]. Two bucket edits keep the maps consistent.

Delete x. Let f = valueCount[x]. If f == 0, the value isn't present — do nothing (deleting an absent value is a no-op, and decrementing would corrupt the maps). Otherwise the value moves from bucket f to f-1: decrement freqOfFreq[f], set valueCount[x] = f - 1, and increment freqOfFreq[f-1] only if `f-1 > 0` (a count of 0 means the value is gone — don't track a 0 bucket).

Query 3 x. Return 1 if freqOfFreq[x] > 0, else 0. One lookup — no scanning.

Why the two maps must stay synchronized. freqOfFreq is only correct if it's updated on every change to valueCount. The discipline is always 'decrement the old frequency bucket, increment the new one' as a value's count changes by exactly one. Skip either half and the maps drift, producing wrong answers later — the subtle bug graders look for.

Why never store a 0 bucket. freqOfFreq[x] > 0 is the existence test. If you ever set freqOfFreq[0] to a positive number (e.g. by incrementing f-1 when f-1 == 0), a future query 3 0 would wrongly report 1, and you'd be tracking a meaningless 'values with frequency 0'. Guard the +1 with f-1 > 0.

Why this is the version to ship. Every operation is O(1) average, so q queries run in O(q) total — comfortably within limits for 10⁵ queries. The cost is one extra map and the discipline of keeping both in sync.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

queries = [[1,5],[1,6],[3,2],[1,10],[1,10],[1,6],[2,5],[3,2]]

Hash-map state

5→1, 6→1

ValueIndex / state

freq 1→ 2

Continue scanning

two values at frequency 1

Final result[0, 1]

C · Code with teaching comments

solution.javaJava

Two Hash Maps — Frequency of Frequencies (Optimal) — optimal

5 teaching notes

1
public List<Integer> freqQuery(int[][] queries) {
2
    Map<Integer, Integer> valueCount = new HashMap<>();
3
    Map<Integer, Integer> freqOfFreq = new HashMap<>();
4
    List<Integer> out = new ArrayList<>();
5
    for (int[] q : queries) {
6
        int type = q[0], x = q[1];
7
        if (type == 1) {
8
            // Current frequency of x; 0 means it's new.
9
            int f = valueCount.getOrDefault(x, 0);
10
            // x is leaving bucket f — decrement it (skip when f==0, no bucket exists).
11
            if (f > 0) freqOfFreq.merge(f, -1, Integer::sum);
12
            valueCount.put(x, f + 1);
13
            // x now has frequency f+1 — increment that bucket. Maps stay in sync.
14
            freqOfFreq.merge(f + 1, 1, Integer::sum);
15
        } else if (type == 2) {
16
            int f = valueCount.getOrDefault(x, 0);
17
            if (f > 0) {
18
                freqOfFreq.merge(f, -1, Integer::sum);
19
                valueCount.put(x, f - 1);
20
                // On delete, only record the new bucket if f-1 > 0 — never store a
21
                // 0-frequency bucket.
22
                if (f - 1 > 0) freqOfFreq.merge(f - 1, 1, Integer::sum);
23
            }
24
        } else {
25
            // Type 3 is one O(1) lookup: is any value at frequency x?
26
            out.add(freqOfFreq.getOrDefault(x, 0) > 0 ? 1 : 0);
27
        }
28
    }
29
    return out;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(1) per query, O(q) total timeO(d) spaceOpen the invariant and proofExplore the proof

The trick is maintaining a derived statistic (the distribution of counts) incrementally instead of recomputing it. Each insert/delete shifts exactly one value between two adjacent frequency buckets, so the update is O(1). This 'second map of frequencies' idea reappears in LFU cache eviction and the All O`one data-structure problem.

ComplexityO(1) per query, O(q) total time, O(d) space — Every query does a constant number of hash-map operations: insert/delete touch valueCount once and freqOfFreq twice; type-3 is one lookup. So O(1) average per query, O(q) total. Space is O(d) for distinct values plus the frequency buckets.

E · Edge cases and pitfalls6[[2,1],[3,1]] — Delete on empty is a no-op (f==0 → skip). freqOfFreq[1] = 0 → query outputs 0. No negative counts.Explore edge cases

Edge cases handled

[[2,1],[3,1]]Delete on empty is a no-op (f==0 → skip). freqOfFreq[1] = 0 → query outputs 0. No negative counts.
[[1,3],[2,3],[3,1]]Insert 3 (freq 1), delete 3 (freq 0). freqOfFreq[1] decremented back to 0; f-1==0 so no 0-bucket stored → query 1 outputs 0.
[[1,9],[1,9],[1,9],[3,3]]9 reaches frequency 3; freqOfFreq[3] = 1 → query outputs 1. Buckets 1 and 2 were vacated along the way.

Pitfalls

Updating valueCount but forgetting to update freqOfFreq — the maps drift and queries go wrong.
Incrementing freqOfFreq[f-1] when f-1 == 0 — pollutes the map with a meaningless 0 bucket.
Decrementing valueCount on a delete when the value isn't present — pushes the count negative.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic List<Integer> freqQuery(int[][] queries) { Map<Integer, Integer> valueCount = new HashMap<>(); Map<Integer, Integer> freqOfFreq = new HashMap<>(); List<Integer> out = new ArrayList<>(); for (int[] q : queries) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Scanning values on every type-3 query

containsValue / 'x in .values()' is O(d). With many type-3 queries on 10⁵ inputs this becomes O(q·d) and times out. A second map makes it O(1).

Explore the code comparison

Don't write this

out.append(1 if x in value_count.values() else 0)  # O(d) scan

Write this instead

out.append(1 if freq_of_freq.get(x, 0) > 0 else 0)  # O(1) lookup

Maps drifting out of sync

If you change valueCount without moving the value between freqOfFreq buckets, freqOfFreq no longer reflects reality and later type-3 answers are wrong.

Explore the code comparison

Don't write this

valueCount.put(x, f + 1);
// forgot to update freqOfFreq

Write this instead

if (f > 0) freqOfFreq.merge(f, -1, Integer::sum);
valueCount.put(x, f + 1);
freqOfFreq.merge(f + 1, 1, Integer::sum);

Storing a frequency-0 bucket

Incrementing freqOfFreq[f-1] when f-1 is 0 records 'values with frequency 0', which is meaningless and would make a query '3 0' wrongly return 1.

Explore the code comparison

Don't write this

freq_of_freq[f - 1] = freq_of_freq.get(f - 1, 0) + 1  # even when f-1 == 0

Write this instead

if f - 1 > 0:
    freq_of_freq[f - 1] = freq_of_freq.get(f - 1, 0) + 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency-of-frequencies — two synchronized hash maps

Code pattern to memorize

insert x: f=valueCount[x]; freqOfFreq[f]--; valueCount[x]=f+1; freqOfFreq[f+1]++
delete x: f=valueCount[x]; if f>0: freqOfFreq[f]--; valueCount[x]=f-1; if f-1>0: freqOfFreq[f-1]++
query x: return 1 if freqOfFreq[x] > 0 else 0

Rules to remember

1Maintain a second map freqOfFreq (count → number of values having that count) so query type 3 is O(1), not an O(n) scan.
2On every insert/delete, decrement the old frequency bucket and increment the new one — keep both maps perfectly in sync.
3On delete, do nothing if the value's count is already 0 — never push a count negative.
4Never store a 0 frequency in freqOfFreq. A count of 0 means 'no value has this frequency', so don't add a freqOfFreq[0] bucket.
5Query 3 asks about a frequency, not a value: 'is there ANY value occurring exactly x times?'

Use this pattern when

You need O(1) answers to 'does any element have count exactly x?'
A stream of insert/delete with interleaved frequency questions
Tracking a distribution of counts that changes incrementally
Any 'frequency of frequencies' / mode-adjacent bookkeeping

Choose another pattern when

Only ever ask for one specific value's count → a single map suffices, no second map
Need the actual values at a frequency, not just existence → store sets, more memory
Static data, queries only at the end → sort/count once, no incremental maps
Need min/max frequency dynamically → a different structure (e.g. buckets + pointers, as in LFU)

Interview takeaway

When a question targets the *distribution of counts* rather than a single count, maintain a 'frequency of frequencies' map alongside the value map. Keeping the two synchronized turns an O(n) scan into an O(1) lookup — the same idea behind LFU caches and All O`one data structures.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical frequency-of-frequencies bookkeeping. When a query targets the distribution of counts (not a single count), maintain a second map (count → #values) in sync with the value map for O(1) answers. Same idea underpins LFU Cache and All O`one Data Structure.

Practice queueDirect variations and pattern siblings

Direct follow-ups

LFU Cache
Coming soon
Frequency-of-frequencies taken further: buckets per frequency to evict the least-frequently-used in O(1).
All O`one Data Structure
Coming soon
Maintain min/max key frequency in O(1) with a doubly linked list of frequency buckets.
Top K Frequent Elements
Coming soon
Bucket values by frequency, then read buckets from the top — bucket sort on counts.
Sort Characters By Frequency
Coming soon
Count, then order by count — the static cousin of this streaming problem.

Same pattern

←

Divisible Sum Pairs

Continue · Next problem

Alternating Characters

mediumArraysFrequently asked

Frequency Queries

Arrays & Hashing · 28 of 83 · 10 min

Process a sequence of queries, each of one of three types:

1 x — insert the value x into the data structure.
2 x — delete one occurrence of x (do nothing if x is not present).
3 x — check whether any integer currently appears exactly x times; output 1 if so, 0 otherwise.

Return the list of answers, one per type-3 query, in order.

In plain English

Examples

Example 1

Input: queries = [[1,5],[1,6],[3,2],[1,10],[1,10],[1,6],[2,5],[3,2]]
Output: [0, 1]
Note: First 3-2: no value yet appears twice → 0. By the second 3-2, both 10 (×2) and 6 (×2) appear twice → 1.

Example 2

Input: queries = [[1,1],[2,2],[3,2],[1,1],[1,1],[2,1],[3,2]]
Output: [0, 1]
Note: First 3-2: value 1 appears once, nothing has freq 2 → 0. After two more inserts and one delete, 1 appears twice → 1.

Example 3

Input: queries = [[3,1],[1,7],[3,1]]
Output: [0, 1]
Note: Initially empty → 0. After inserting 7 once, a value has frequency 1 → 1.

Constraints

1 ≤ number of queries ≤ 10⁵
Query type ∈ {1, 2, 3}
0 < x ≤ 10⁹ for the value argument
Deleting an absent value is a no-op
Type-3 x is a frequency to test (x ≥ 1 in practice)

Clarifying questions4First question: Does query type 3 ask about a value or a frequency?Explore questions

Q1.Does query type 3 ask about a value or a frequency?
A frequency: 'is there any value that occurs exactly x times right now?' Misreading this as 'how many times does value x appear' is the classic trap.
Q2.What happens when I delete a value that isn't present?
Nothing — it's a no-op. You must guard against decrementing a count below 0.
Q3.Can the same value be inserted many times?
Yes — that's the point. valueCount[x] grows with each insert and shrinks with each delete.
Q4.Could x in a type-3 query exceed every current count?
Yes — then freqOfFreq[x] is 0 (absent), so you output 0. A defaultdict / getOrDefault handles it cleanly.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you realise query type 3 asks about frequencies (not values) and add a second 'frequency of frequencies' map so it's O(1), instead of scanning all counts.

Where candidates slip

Using only valueCount and scanning its values on every type-3 query (O(n) per query → O(n²) overall), or letting the two maps drift out of sync on delete.

How to stand out

Name the 'frequency of frequencies' map, keep both maps in sync with a decrement-old/increment-new step, and guard delete so counts never go negative and 0 buckets are never stored.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Single Map, Scan on Query 3	`O(q × d) where d = distinct values`	`O(d)`	State it to show the inserts/deletes are easy, then note that scanning all counts per type-3 query is the bottleneck.	Read
2	Two Hash Maps — Frequency of Frequencies (Optimal)Optimal	`O(1) per query, O(q) total`	`O(d)`	The answer they want. Phrase it as 'keep a second map: frequency → how many values have that frequency, so query 3 is O(1)'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Single Map, Scan on Query 3

TimeO(q × d) where d = distinct valuesSpaceO(d)

State it to show the inserts/deletes are easy, then note that scanning all counts per type-3 query is the bottleneck.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Inserts and deletes are trivial with one map: valueCount[x] up or down. The cost is hidden in the type-3 query.

2Hint 2Explore hint

For a type-3 query, you need to know whether ANY value has count exactly x. With only valueCount, how do you find out?

3Hint 3Explore hint

You'd scan every entry of valueCount looking for a count equal to x — O(d) per query. With up to 10⁵ queries that's O(q·d), too slow when many are type 3.

A · Core idea

Keep a single map valueCount from value to its current occurrence count. Inserts increment it, deletes decrement it (guarding against going below 0).

Why the inserts/deletes are fine. Each is a single hash-map update — O(1) average. Nothing about maintaining individual counts is slow.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

queries = [[1,1],[1,1],[3,2],[3,5]]

Hash-map state

state

ValueIndex / state

1→ 2

Continue scanning

value 1 has count 2

Final result[1, 0]

C · Code with teaching comments

solution.javaJava

Brute Force — Single Map, Scan on Query 3 — reference

3 teaching notes

1
public List<Integer> freqQuery(int[][] queries) {
2
    Map<Integer, Integer> valueCount = new HashMap<>();
3
    List<Integer> out = new ArrayList<>();
4
    for (int[] q : queries) {
5
        int type = q[0], x = q[1];
6
        if (type == 1) {
7
            // Insert: add 1 to x's count, creating the entry if new.
8
            valueCount.merge(x, 1, Integer::sum);
9
        } else if (type == 2) {
10
            // Delete: drop the count by 1, removing the key entirely at 0 so it can't
11
            // be falsely matched.
12
            valueCount.computeIfPresent(x, (k, v) -> v > 1 ? v - 1 : null);
13
        } else {
14
            // Type 3: containsValue scans ALL counts — O(d), the bottleneck.
15
            boolean found = valueCount.containsValue(x);
16
            out.add(found ? 1 : 0);
17
        }
18
    }
19
    return out;
20
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO(q × d) where d = distinct values timeO(d) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Using containsValue / x in .values() on every type-3 query — O(d) each, O(q·d) total.Explore edge cases

Pitfalls

Using containsValue / x in .values() on every type-3 query — O(d) each, O(q·d) total.
Leaving a value at count 0 in the map — containsValue(0) could falsely match.
Reading type-3 x as a value to look up rather than a frequency to test.

03.2

Approach 2 of 2 · Optimal

Two Hash Maps — Frequency of Frequencies (Optimal)

TimeO(1) per query, O(q) totalSpaceO(d)

The answer they want. Phrase it as 'keep a second map: frequency → how many values have that frequency, so query 3 is O(1)'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you tracked, for each frequency value, how many distinct numbers currently have that frequency? Then 'any value with frequency x?' is a single lookup.

2Hint 2Explore hint

3Hint 3Explore hint

Type 3 x: return 1 if freqOfFreq[x] > 0 else 0. Never store a 0-count bucket, and never let valueCount go negative on a delete.

A · Core idea

Run two maps in lockstep:

valueCount: value → how many times it currently appears.
freqOfFreq: a frequency → how many distinct values currently have exactly that frequency.

freqOfFreq is the 'frequency of frequencies' map, and it's what makes type-3 queries O(1).

Query 3 x. Return 1 if freqOfFreq[x] > 0, else 0. One lookup — no scanning.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

queries = [[1,5],[1,6],[3,2],[1,10],[1,10],[1,6],[2,5],[3,2]]

Hash-map state

5→1, 6→1

ValueIndex / state

freq 1→ 2

Continue scanning

two values at frequency 1

Final result[0, 1]

C · Code with teaching comments

solution.javaJava

Two Hash Maps — Frequency of Frequencies (Optimal) — optimal

5 teaching notes

1
public List<Integer> freqQuery(int[][] queries) {
2
    Map<Integer, Integer> valueCount = new HashMap<>();
3
    Map<Integer, Integer> freqOfFreq = new HashMap<>();
4
    List<Integer> out = new ArrayList<>();
5
    for (int[] q : queries) {
6
        int type = q[0], x = q[1];
7
        if (type == 1) {
8
            // Current frequency of x; 0 means it's new.
9
            int f = valueCount.getOrDefault(x, 0);
10
            // x is leaving bucket f — decrement it (skip when f==0, no bucket exists).
11
            if (f > 0) freqOfFreq.merge(f, -1, Integer::sum);
12
            valueCount.put(x, f + 1);
13
            // x now has frequency f+1 — increment that bucket. Maps stay in sync.
14
            freqOfFreq.merge(f + 1, 1, Integer::sum);
15
        } else if (type == 2) {
16
            int f = valueCount.getOrDefault(x, 0);
17
            if (f > 0) {
18
                freqOfFreq.merge(f, -1, Integer::sum);
19
                valueCount.put(x, f - 1);
20
                // On delete, only record the new bucket if f-1 > 0 — never store a
21
                // 0-frequency bucket.
22
                if (f - 1 > 0) freqOfFreq.merge(f - 1, 1, Integer::sum);
23
            }
24
        } else {
25
            // Type 3 is one O(1) lookup: is any value at frequency x?
26
            out.add(freqOfFreq.getOrDefault(x, 0) > 0 ? 1 : 0);
27
        }
28
    }
29
    return out;
30
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.30 lines

D · Why it works and complexityO(1) per query, O(q) total timeO(d) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6[[2,1],[3,1]] — Delete on empty is a no-op (f==0 → skip). freqOfFreq[1] = 0 → query outputs 0. No negative counts.Explore edge cases

Edge cases handled

[[2,1],[3,1]]Delete on empty is a no-op (f==0 → skip). freqOfFreq[1] = 0 → query outputs 0. No negative counts.
[[1,3],[2,3],[3,1]]Insert 3 (freq 1), delete 3 (freq 0). freqOfFreq[1] decremented back to 0; f-1==0 so no 0-bucket stored → query 1 outputs 0.
[[1,9],[1,9],[1,9],[3,3]]9 reaches frequency 3; freqOfFreq[3] = 1 → query outputs 1. Buckets 1 and 2 were vacated along the way.

Pitfalls

Updating valueCount but forgetting to update freqOfFreq — the maps drift and queries go wrong.
Incrementing freqOfFreq[f-1] when f-1 == 0 — pollutes the map with a meaningless 0 bucket.
Decrementing valueCount on a delete when the value isn't present — pushes the count negative.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Scanning values on every type-3 query

containsValue / 'x in .values()' is O(d). With many type-3 queries on 10⁵ inputs this becomes O(q·d) and times out. A second map makes it O(1).

Explore the code comparison

Don't write this

out.append(1 if x in value_count.values() else 0)  # O(d) scan

Write this instead

out.append(1 if freq_of_freq.get(x, 0) > 0 else 0)  # O(1) lookup

Maps drifting out of sync

If you change valueCount without moving the value between freqOfFreq buckets, freqOfFreq no longer reflects reality and later type-3 answers are wrong.

Explore the code comparison

Don't write this

valueCount.put(x, f + 1);
// forgot to update freqOfFreq

Write this instead

if (f > 0) freqOfFreq.merge(f, -1, Integer::sum);
valueCount.put(x, f + 1);
freqOfFreq.merge(f + 1, 1, Integer::sum);

Storing a frequency-0 bucket

Incrementing freqOfFreq[f-1] when f-1 is 0 records 'values with frequency 0', which is meaningless and would make a query '3 0' wrongly return 1.

Explore the code comparison

Don't write this

freq_of_freq[f - 1] = freq_of_freq.get(f - 1, 0) + 1  # even when f-1 == 0

Write this instead

if f - 1 > 0:
    freq_of_freq[f - 1] = freq_of_freq.get(f - 1, 0) + 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Frequency-of-frequencies — two synchronized hash maps

Code pattern to memorize

insert x: f=valueCount[x]; freqOfFreq[f]--; valueCount[x]=f+1; freqOfFreq[f+1]++
delete x: f=valueCount[x]; if f>0: freqOfFreq[f]--; valueCount[x]=f-1; if f-1>0: freqOfFreq[f-1]++
query x: return 1 if freqOfFreq[x] > 0 else 0

Rules to remember

1Maintain a second map freqOfFreq (count → number of values having that count) so query type 3 is O(1), not an O(n) scan.
2On every insert/delete, decrement the old frequency bucket and increment the new one — keep both maps perfectly in sync.
3On delete, do nothing if the value's count is already 0 — never push a count negative.
4Never store a 0 frequency in freqOfFreq. A count of 0 means 'no value has this frequency', so don't add a freqOfFreq[0] bucket.
5Query 3 asks about a frequency, not a value: 'is there ANY value occurring exactly x times?'

Use this pattern when

You need O(1) answers to 'does any element have count exactly x?'
A stream of insert/delete with interleaved frequency questions
Tracking a distribution of counts that changes incrementally
Any 'frequency of frequencies' / mode-adjacent bookkeeping

Choose another pattern when

Only ever ask for one specific value's count → a single map suffices, no second map
Need the actual values at a frequency, not just existence → store sets, more memory
Static data, queries only at the end → sort/count once, no incremental maps
Need min/max frequency dynamically → a different structure (e.g. buckets + pointers, as in LFU)

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

LFU Cache
Coming soon
Frequency-of-frequencies taken further: buckets per frequency to evict the least-frequently-used in O(1).
All O`one Data Structure
Coming soon
Maintain min/max key frequency in O(1) with a doubly linked list of frequency buckets.
Top K Frequent Elements
Coming soon
Bucket values by frequency, then read buckets from the top — bucket sort on counts.
Sort Characters By Frequency
Coming soon
Count, then order by count — the static cousin of this streaming problem.

Same pattern

←

Divisible Sum Pairs

Continue · Next problem

Alternating Characters