Loading…

easyStrings0Sometimes asked

Gemstones

Q: How do you solve Gemstones using the Test Each Letter Against Every Rock (Baseline) approach?

When to use it: State it first — it reads straight off the definition, then note it rescans rocks for all 26 letters. Translate the definition directly: a gemstone is a letter present in all rocks, so test the 26 candidate letters one at a time. For a letter `c`, walk each rock and ask 'does this rock contain `c`?'. If every rock answers yes, `c` is a gem; tally it. **Why it is correct.** It is the definition expressed as nested loops — letters on the outside, rocks on the inside. There's no insight to overlook, which makes it a clean way to confirm you understand 'present in every rock'. **Why deduping within a rock is irrelevant here.** Because the inner test is membership ('does the rock contain `c`?'), repeats inside a rock don't matter — `contains` is the same whether `c` appears once or five times. That's the same reason the optimal version works on distinct letters. **Why we don't ship it.** For each of the 26 letters you potentially rescan every rock from scratch, repeating the same character reads up to 26 times. You can instead make one pass per rock, record its *distinct* letters, and combine those across rocks. Mention this as the literal reading, give the `O(26 · total)` cost, then move to the intersection / counting solution. Time complexity: O(26 · total characters). Space complexity: O(1).

Arrays & Hashing · 52 of 83 · 6 min

You are given an array of n rocks, each represented by a non-empty string of lowercase letters. Each letter inside a rock is a mineral.

A mineral is called a gem element (or gemstone) if it occurs at least once in every rock.

Return the number of distinct gem elements — that is, how many letters appear in all n rocks.

In plain English

Think of each rock as the *set* of letters it contains (repeats collapse away). A gemstone is a letter that belongs to all of those sets at once — the intersection of every rock's letter-set. The count of that intersection is the answer. Because there are only 26 possible letters, you can track this with a fixed-size table instead of general sets.

Examples

Example 1

Input: rocks = ["abcdde", "baccd", "eeabg"]
Output: 2
Note: Letters in all three: 'a' (yes/yes/yes) and 'b' (yes/yes/yes). 'c' is missing from the third rock, 'd'/'e'/'g' fail somewhere. Two gemstones.

Example 2

Input: rocks = ["basdfj", "asadfg", "alskjf", "bsdfk"]
Output: 1
Note: Only 's' appears in all four rocks. Everything else is missing from at least one.

Example 3

Input: rocks = ["abc"]
Output: 3
Note: With a single rock, every distinct letter in it is a gemstone: a, b, c.

Constraints

1 ≤ n ≤ 100
Each rock string consists of lowercase English letters a–z
1 ≤ length of each rock ≤ 100

Clarifying questions4First question: Does a repeated letter inside one rock count more than once?Explore questions

Q1.Does a repeated letter inside one rock count more than once?
No. Only presence matters per rock, so deduplicate each rock to its distinct letters first.
Q2.Must a gem appear in EVERY rock, or just most?
Every rock. A single rock lacking the letter disqualifies it entirely.
Q3.Could a rock be empty?
Per the constraints each rock is non-empty; if an empty rock were allowed, the intersection would be empty and the answer 0.
Q4.Is the alphabet limited to a–z?
Yes, lowercase English letters. That fixed 26-letter universe lets us use a boolean[26]/int[26] instead of hash sets.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

A gem element is a kind of mineral that appears in every rock. Take the set of distinct letters in the first rock, then intersect it with the letter-set of each remaining rock. Whatever survives all the intersections is present in every rock — its size is the answer. Equivalently, count how many of the 26 letters appear in all rocks. O(total characters) time, O(1) space (26-letter alphabet).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you map 'appears in every rock' onto a set intersection (or a per-letter universal-count), and whether you correctly use distinct letters per rock so within-rock repeats don't skew the result.

Where candidates slip

Counting total occurrences of each letter across all rocks and comparing to the number of rocks — a letter appearing twice in one rock and zero times in another would wrongly hit the threshold.

How to stand out

Offer the O(1)-space counting version: one int[26] where slot c counts how many rocks contain letter c (deduped per rock); the answer is the number of slots equal to the rock count.

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	Test Each Letter Against Every Rock (Baseline)	`O(26 · total characters)`	`O(1)`	State it first — it reads straight off the definition, then note it rescans rocks for all 26 letters.	Read
2	Set Intersection / Per-Letter Universal Count (Optimal)Optimal	`O(total characters)`	`O(1)`	The intended answer. Say 'intersect each rock's distinct letters' or 'count letters present in all n rocks'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewcommon = letters(rock 0)More rocks?YesNoExplore 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

Test Each Letter Against Every Rock (Baseline)

TimeO(26 · total characters)SpaceO(1)

State it first — it reads straight off the definition, then note it rescans rocks for all 26 letters.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition says a gem is in every rock. How would you verify that for one candidate letter?

2Hint 2Explore hint

For each letter from 'a' to 'z', check whether it appears in every rock by scanning each rock.

3Hint 3Explore hint

Count the letters that pass the 'present in all rocks' test. That count is the answer.

A · Core idea

Translate the definition directly: a gemstone is a letter present in all rocks, so test the 26 candidate letters one at a time. For a letter c, walk each rock and ask 'does this rock contain c?'. If every rock answers yes, c is a gem; tally it.

Why it is correct. It is the definition expressed as nested loops — letters on the outside, rocks on the inside. There's no insight to overlook, which makes it a clean way to confirm you understand 'present in every rock'.

Why deduping within a rock is irrelevant here. Because the inner test is membership ('does the rock contain c?'), repeats inside a rock don't matter — contains is the same whether c appears once or five times. That's the same reason the optimal version works on distinct letters.

Why we don't ship it. For each of the 26 letters you potentially rescan every rock from scratch, repeating the same character reads up to 26 times. You can instead make one pass per rock, record its distinct letters, and combine those across rocks. Mention this as the literal reading, give the O(26 · total) cost, then move to the intersection / counting solution.

B · Visual dry run

Interactive dry run

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

rocks = ["ab", "ba", "bc"]

letter 'a'

in "ab"? yes; "ba"? yes; "bc"? no

Statenot a gem

Final result1

C · Code with teaching comments

Reference implementation previewpublic int gemstones(String[] rocks) { int gems = 0; for (char c = 'a'; c <= 'z'; c++) { boolean inAll = true; for (String rock : rocks) {Explore the full code

solution.javaJava

Test Each Letter Against Every Rock (Baseline) — reference

4 teaching notes

1
public int gemstones(String[] rocks) {
2
    int gems = 0;
3
    // Outer loop over the 26 candidate gem letters.
4
    for (char c = 'a'; c <= 'z'; c++) {
5
        boolean inAll = true;
6
        for (String rock : rocks) {
7
            // indexOf rescans the rock for this letter — repeated for every candidate.
8
            if (rock.indexOf(c) == -1) {
9
                // One rock missing the letter disqualifies it; break out early.
10
                inAll = false;
11
                break;
12
            }
13
        }
14
        if (inAll) {
15
            gems++;
16
        }
17
    }
18
    return gems;
19
}

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

D · Why it works and complexityO(26 · total characters) timeO(1) spaceOpen the invariant and proofExplore the proof

Each candidate-letter scan re-reads characters it has already seen. Recording each rock's distinct letters once and intersecting (or tallying) them removes that repetition — you read every character a single time.

ComplexityO(26 · total characters) time, O(1) space — For each of the 26 letters you may scan every rock fully, so the work is 26 × (sum of rock lengths) in the worst case. Only a counter is stored → O(1) extra space.

E · Edge cases and pitfalls3Re-scanning rocks 26 times instead of reading each rock once.Explore edge cases

Pitfalls

Re-scanning rocks 26 times instead of reading each rock once.
Assuming indexOf / `in` is O(1) — each call scans the rock.
Confusing 'present in every rock' (intersection) with 'present in some rock' (union).

03.2

Approach 2 of 2 · Optimal

Set Intersection / Per-Letter Universal Count (Optimal)

TimeO(total characters)SpaceO(1)

The intended answer. Say 'intersect each rock's distinct letters' or 'count letters present in all n rocks'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Flip the loops: instead of asking each letter about every rock, process each rock once and remember its distinct letters. What operation combines those per-rock letter sets into 'present in all'?

2Hint 2Explore hint

Seed a 'common' set with the distinct letters of the first rock, then intersect it with each later rock's letter set. Intersection only removes letters, never adds.

3Hint 3Explore hint

Or count, per letter, how many rocks contain it (dedupe within a rock first). A letter is a gem exactly when that count equals the number of rocks. Answer = number of such letters.

A · Core idea

Process the rocks once. Maintain the set of letters common to all rocks seen so far, starting from the first rock's distinct letters, and intersect it with each subsequent rock. The size of what remains is the gemstone count.

Why intersection is the right operation. 'Appears in every rock' is, by definition, membership in the intersection of all the per-rock letter sets. Folding intersection across the rocks (common = common ∩ rock_letters) keeps exactly the letters that have appeared in every rock processed so far. Intersection is monotone-shrinking: a letter, once dropped because some rock lacked it, can never come back — which matches the rule that one missing rock disqualifies a gem permanently.

Why distinct letters per rock. The intersection cares only about presence, so collapse each rock to its set of distinct letters first. A letter appearing five times in one rock contributes the same as appearing once; deduping avoids letting within-rock repeats distort anything.

The equivalent counting view (and why it's O(1) space). Keep an int[26] where slot c counts how many rocks contain `c`. For each rock, take its distinct letters and bump those slots by one. After all rocks, a letter is a gem exactly when its slot equals n, the number of rocks — it showed up in every one. Counting the slots equal to n gives the answer. The table is fixed at 26 entries regardless of how many or how long the rocks are, so the extra space is constant. Deduping per rock is what makes the threshold check valid — without it, two occurrences in a single rock would push the count toward n dishonestly.

Why both views are the same algorithm. The intersection set is precisely the set of letters whose per-rock count reached n. One expresses it as repeated set ANDs, the other as a tally with a final threshold — pick whichever reads more clearly in the interview.

B · Visual dry run

Interactive dry run

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

rocks = ["abc", "bcd", "cbe"]

Hash-map state

after rock 0

ValueIndex / state

a→ 1

b→ 1

c→ 1

Continue scanning

distinct {a,b,c} → +1 each

Final result2

C · Code with teaching comments

solution.javaJava

Set Intersection / Per-Letter Universal Count (Optimal) — optimal

4 teaching notes

1
public int gemstones(String[] rocks) {
2
    int[] rockCount = new int[26];
3
    for (String rock : rocks) {
4
        // Per-rock presence table — dedupes this rock's letters so each counts once.
5
        boolean[] seen = new boolean[26];
6
        for (int i = 0; i < rock.length(); i++) {
7
            // Mark each distinct letter of the current rock.
8
            seen[rock.charAt(i) - 'a'] = true;
9
        }
10
        for (int c = 0; c < 26; c++) {
11
            if (seen[c]) {
12
                rockCount[c]++;
13
            }
14
        }
15
    }
16
    int gems = 0;
17
    for (int c = 0; c < 26; c++) {
18
        if (rockCount[c] == rocks.length) {
19
            gems++;
20
        }
21
    }
22
    return gems;
23
}

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

D · Why it works and complexityO(total characters) timeO(1) spaceOpen the invariant and proofExplore the proof

'Common to all collections' is the textbook signal for set intersection folded across the inputs. When the element universe is a small fixed alphabet, swap the hash set for a per-letter 'in how many rocks?' counter: it's the same intersection in O(1) space, and the gem test becomes 'count == number of rocks'.

ComplexityO(total characters) time, O(1) space — Each character of each rock is read once to build per-rock presence → O(total characters). The state is a fixed 26-slot table (or a set of ≤26 letters), independent of input size → O(1) auxiliary space.

E · Edge cases and pitfalls6rocks = ["abc"] — Single rock → common is its distinct letters → 3 gemstones.Explore edge cases

Edge cases handled

rocks = ["abc"]Single rock → common is its distinct letters → 3 gemstones.
rocks = ["aaa", "aa", "a"]Deduped, every rock is {a} → intersection {a} → 1 gemstone, repeats ignored.
rocks = ["abc", "def"]Disjoint letter sets → intersection empty → 0 gemstones.

Pitfalls

Counting total occurrences across rocks instead of deduping per rock — a doubled letter in one rock can fake the threshold.
Starting the intersection from an empty set instead of rock 0's letters — yields 0 every time.
Using union (any rock) instead of intersection (every rock).

Practice

Try the solution yourself

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

Editable code previewpublic int gemstones(String[] rocks) { int[] rockCount = new int[26]; for (String rock : rocks) { boolean[] seen = new boolean[26]; for (int i = 0; i < rock.length(); i++) {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.

Total occurrences instead of per-rock presence

If you count every occurrence, a letter appearing twice in rock A and never in rock B can reach the rock-count threshold and be wrongly called a gem. Dedupe each rock first.

Explore the code comparison

Don't write this

from collections import Counter
total = Counter()
for rock in rocks:
    total += Counter(rock)
return sum(1 for c, k in total.items() if k >= len(rocks))

Write this instead

common = set(rocks[0])
for rock in rocks[1:]:
    common &= set(rock)
return len(common)

Union instead of intersection

Using |= (union) collects letters present in ANY rock, which counts far too many. Gems must be in EVERY rock, which is intersection (&=).

Explore the code comparison

Don't write this

common = set(rocks[0])
for rock in rocks[1:]:
    common |= set(rock)
return len(common)

Write this instead

common = set(rocks[0])
for rock in rocks[1:]:
    common &= set(rock)
return len(common)

Seeding the intersection empty

Intersecting an empty set with anything stays empty, so you'd always return 0. Seed with the first rock's distinct letters, then intersect the rest.

Explore the code comparison

Don't write this

Set<Character> common = new HashSet<>();
for (String rock : rocks) {
    common.retainAll(rock.chars().mapToObj(c -> (char) c).collect(Collectors.toSet()));
}

Write this instead

Set<Character> common = rocks[0].chars().mapToObj(c -> (char) c).collect(Collectors.toSet());
for (int r = 1; r < rocks.length; r++) {
    common.retainAll(rocks[r].chars().mapToObj(c -> (char) c).collect(Collectors.toSet()));
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Set intersection across all rows / per-letter universal count

Code pattern to memorize

common = set(rocks[0])
for rock in rocks[1:]:
    common &= set(rock)
return len(common)

Rules to remember

1A gem must appear in every rock — one rock missing a letter eliminates it for good.
2Use distinct letters per rock; repeats inside a single rock don't matter.
3Intersection only shrinks the set — start with rock 0 and keep &=-ing the rest.
4Equivalent counting form: a letter is a gem iff its per-letter count of rocks containing it equals the number of rocks.
5The alphabet is fixed (a–z), so a boolean[26] per rock or a int[26] tally gives O(1) space.

Use this pattern when

You need elements common to *all* of several collections (intersection of many sets)
The universe is a small fixed alphabet so sets become boolean[26] tables
Duplicates within one collection are irrelevant — only presence matters
'Appears in every…' phrasing is a tell for whole-set intersection

Choose another pattern when

You need elements in *any* rock (union) → union, not intersection
Counts across rocks matter (e.g. 'appears at least k times total') → frequency, not presence
Order or position matters → this is no longer a pure set problem
The alphabet is huge/unknown → real hash sets instead of boolean[26]

Interview takeaway

'Common to all' is set intersection; fold it across the collection with `&=`, starting from the first element's set. With a fixed 26-letter alphabet, a per-letter 'in how many rocks?' tally is the same idea in O(1) space — a gem is any letter whose tally equals the rock count.

Continue

Transfer the pattern to another problem

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

Transferable patternSet intersection across many collections. 'Present in every collection' folds intersection across the inputs, seeded by the first one. When the universe is a small fixed alphabet, replace the hash set with a per-letter 'in how many collections?' counter — a gem is any letter whose count equals the number of collections — giving O(1) space. Same shape as Find Common Characters and multi-array intersection.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Find Common Characters
Coming soon
Same intersection across words, but you keep min frequencies and output the actual characters.
Intersection of Two Arrays
Coming soon
The two-collection case of the same set-intersection idea.
Sherlock and Anagrams
Different goal, but again maps strings to frequency signatures and counts matches.
Valid Anagram
Fixed 26-letter tables again, comparing two frequency profiles.

Same pattern

←

Funny String

Continue · Next problem

Pangrams

easyStrings0Sometimes asked

Gemstones

Arrays & Hashing · 52 of 83 · 6 min

You are given an array of n rocks, each represented by a non-empty string of lowercase letters. Each letter inside a rock is a mineral.

A mineral is called a gem element (or gemstone) if it occurs at least once in every rock.

Return the number of distinct gem elements — that is, how many letters appear in all n rocks.

In plain English

Examples

Example 1

Input: rocks = ["abcdde", "baccd", "eeabg"]
Output: 2
Note: Letters in all three: 'a' (yes/yes/yes) and 'b' (yes/yes/yes). 'c' is missing from the third rock, 'd'/'e'/'g' fail somewhere. Two gemstones.

Example 2

Input: rocks = ["basdfj", "asadfg", "alskjf", "bsdfk"]
Output: 1
Note: Only 's' appears in all four rocks. Everything else is missing from at least one.

Example 3

Input: rocks = ["abc"]
Output: 3
Note: With a single rock, every distinct letter in it is a gemstone: a, b, c.

Constraints

1 ≤ n ≤ 100
Each rock string consists of lowercase English letters a–z
1 ≤ length of each rock ≤ 100

Clarifying questions4First question: Does a repeated letter inside one rock count more than once?Explore questions

Q1.Does a repeated letter inside one rock count more than once?
No. Only presence matters per rock, so deduplicate each rock to its distinct letters first.
Q2.Must a gem appear in EVERY rock, or just most?
Every rock. A single rock lacking the letter disqualifies it entirely.
Q3.Could a rock be empty?
Per the constraints each rock is non-empty; if an empty rock were allowed, the intersection would be empty and the answer 0.
Q4.Is the alphabet limited to a–z?
Yes, lowercase English letters. That fixed 26-letter universe lets us use a boolean[26]/int[26] instead of hash sets.

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

Where candidates slip

Counting total occurrences of each letter across all rocks and comparing to the number of rocks — a letter appearing twice in one rock and zero times in another would wrongly hit the threshold.

How to stand out

Offer the O(1)-space counting version: one int[26] where slot c counts how many rocks contain letter c (deduped per rock); the answer is the number of slots equal to the rock count.

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	Test Each Letter Against Every Rock (Baseline)	`O(26 · total characters)`	`O(1)`	State it first — it reads straight off the definition, then note it rescans rocks for all 26 letters.	Read
2	Set Intersection / Per-Letter Universal Count (Optimal)Optimal	`O(total characters)`	`O(1)`	The intended answer. Say 'intersect each rock's distinct letters' or 'count letters present in all n rocks'.	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

Test Each Letter Against Every Rock (Baseline)

TimeO(26 · total characters)SpaceO(1)

State it first — it reads straight off the definition, then note it rescans rocks for all 26 letters.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The definition says a gem is in every rock. How would you verify that for one candidate letter?

2Hint 2Explore hint

For each letter from 'a' to 'z', check whether it appears in every rock by scanning each rock.

3Hint 3Explore hint

Count the letters that pass the 'present in all rocks' test. That count is the answer.

A · Core idea

B · Visual dry run

Interactive dry run

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

rocks = ["ab", "ba", "bc"]

letter 'a'

in "ab"? yes; "ba"? yes; "bc"? no

Statenot a gem

Final result1

C · Code with teaching comments

Reference implementation previewpublic int gemstones(String[] rocks) { int gems = 0; for (char c = 'a'; c <= 'z'; c++) { boolean inAll = true; for (String rock : rocks) {Explore the full code

solution.javaJava

Test Each Letter Against Every Rock (Baseline) — reference

4 teaching notes

1
public int gemstones(String[] rocks) {
2
    int gems = 0;
3
    // Outer loop over the 26 candidate gem letters.
4
    for (char c = 'a'; c <= 'z'; c++) {
5
        boolean inAll = true;
6
        for (String rock : rocks) {
7
            // indexOf rescans the rock for this letter — repeated for every candidate.
8
            if (rock.indexOf(c) == -1) {
9
                // One rock missing the letter disqualifies it; break out early.
10
                inAll = false;
11
                break;
12
            }
13
        }
14
        if (inAll) {
15
            gems++;
16
        }
17
    }
18
    return gems;
19
}

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

D · Why it works and complexityO(26 · total characters) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls3Re-scanning rocks 26 times instead of reading each rock once.Explore edge cases

Pitfalls

Re-scanning rocks 26 times instead of reading each rock once.
Assuming indexOf / `in` is O(1) — each call scans the rock.
Confusing 'present in every rock' (intersection) with 'present in some rock' (union).

03.2

Approach 2 of 2 · Optimal

Set Intersection / Per-Letter Universal Count (Optimal)

TimeO(total characters)SpaceO(1)

The intended answer. Say 'intersect each rock's distinct letters' or 'count letters present in all n rocks'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Flip the loops: instead of asking each letter about every rock, process each rock once and remember its distinct letters. What operation combines those per-rock letter sets into 'present in all'?

2Hint 2Explore hint

Seed a 'common' set with the distinct letters of the first rock, then intersect it with each later rock's letter set. Intersection only removes letters, never adds.

3Hint 3Explore hint

Or count, per letter, how many rocks contain it (dedupe within a rock first). A letter is a gem exactly when that count equals the number of rocks. Answer = number of such letters.

A · Core idea

B · Visual dry run

Interactive dry run

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

rocks = ["abc", "bcd", "cbe"]

Hash-map state

after rock 0

ValueIndex / state

a→ 1

b→ 1

c→ 1

Continue scanning

distinct {a,b,c} → +1 each

Final result2

C · Code with teaching comments

solution.javaJava

Set Intersection / Per-Letter Universal Count (Optimal) — optimal

4 teaching notes

1
public int gemstones(String[] rocks) {
2
    int[] rockCount = new int[26];
3
    for (String rock : rocks) {
4
        // Per-rock presence table — dedupes this rock's letters so each counts once.
5
        boolean[] seen = new boolean[26];
6
        for (int i = 0; i < rock.length(); i++) {
7
            // Mark each distinct letter of the current rock.
8
            seen[rock.charAt(i) - 'a'] = true;
9
        }
10
        for (int c = 0; c < 26; c++) {
11
            if (seen[c]) {
12
                rockCount[c]++;
13
            }
14
        }
15
    }
16
    int gems = 0;
17
    for (int c = 0; c < 26; c++) {
18
        if (rockCount[c] == rocks.length) {
19
            gems++;
20
        }
21
    }
22
    return gems;
23
}

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

D · Why it works and complexityO(total characters) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6rocks = ["abc"] — Single rock → common is its distinct letters → 3 gemstones.Explore edge cases

Edge cases handled

rocks = ["abc"]Single rock → common is its distinct letters → 3 gemstones.
rocks = ["aaa", "aa", "a"]Deduped, every rock is {a} → intersection {a} → 1 gemstone, repeats ignored.
rocks = ["abc", "def"]Disjoint letter sets → intersection empty → 0 gemstones.

Pitfalls

Counting total occurrences across rocks instead of deduping per rock — a doubled letter in one rock can fake the threshold.
Starting the intersection from an empty set instead of rock 0's letters — yields 0 every time.
Using union (any rock) instead of intersection (every rock).

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.

Total occurrences instead of per-rock presence

If you count every occurrence, a letter appearing twice in rock A and never in rock B can reach the rock-count threshold and be wrongly called a gem. Dedupe each rock first.

Explore the code comparison

Don't write this

from collections import Counter
total = Counter()
for rock in rocks:
    total += Counter(rock)
return sum(1 for c, k in total.items() if k >= len(rocks))

Write this instead

common = set(rocks[0])
for rock in rocks[1:]:
    common &= set(rock)
return len(common)

Union instead of intersection

Using |= (union) collects letters present in ANY rock, which counts far too many. Gems must be in EVERY rock, which is intersection (&=).

Explore the code comparison

Don't write this

common = set(rocks[0])
for rock in rocks[1:]:
    common |= set(rock)
return len(common)

Write this instead

common = set(rocks[0])
for rock in rocks[1:]:
    common &= set(rock)
return len(common)

Seeding the intersection empty

Intersecting an empty set with anything stays empty, so you'd always return 0. Seed with the first rock's distinct letters, then intersect the rest.

Explore the code comparison

Don't write this

Set<Character> common = new HashSet<>();
for (String rock : rocks) {
    common.retainAll(rock.chars().mapToObj(c -> (char) c).collect(Collectors.toSet()));
}

Write this instead

Set<Character> common = rocks[0].chars().mapToObj(c -> (char) c).collect(Collectors.toSet());
for (int r = 1; r < rocks.length; r++) {
    common.retainAll(rocks[r].chars().mapToObj(c -> (char) c).collect(Collectors.toSet()));
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Set intersection across all rows / per-letter universal count

Code pattern to memorize

common = set(rocks[0])
for rock in rocks[1:]:
    common &= set(rock)
return len(common)

Rules to remember

1A gem must appear in every rock — one rock missing a letter eliminates it for good.
2Use distinct letters per rock; repeats inside a single rock don't matter.
3Intersection only shrinks the set — start with rock 0 and keep &=-ing the rest.
4Equivalent counting form: a letter is a gem iff its per-letter count of rocks containing it equals the number of rocks.
5The alphabet is fixed (a–z), so a boolean[26] per rock or a int[26] tally gives O(1) space.

Use this pattern when

You need elements common to *all* of several collections (intersection of many sets)
The universe is a small fixed alphabet so sets become boolean[26] tables
Duplicates within one collection are irrelevant — only presence matters
'Appears in every…' phrasing is a tell for whole-set intersection

Choose another pattern when

You need elements in *any* rock (union) → union, not intersection
Counts across rocks matter (e.g. 'appears at least k times total') → frequency, not presence
Order or position matters → this is no longer a pure set problem
The alphabet is huge/unknown → real hash sets instead of boolean[26]

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

Find Common Characters
Coming soon
Same intersection across words, but you keep min frequencies and output the actual characters.
Intersection of Two Arrays
Coming soon
The two-collection case of the same set-intersection idea.
Sherlock and Anagrams
Different goal, but again maps strings to frequency signatures and counts matches.
Valid Anagram
Fixed 26-letter tables again, comparing two frequency profiles.

Same pattern

←

Funny String

Continue · Next problem

Pangrams