Loading…

mediumGraphsLC #433Sometimes asked

Minimum Genetic Mutation

Q: How do you solve Minimum Genetic Mutation using the BFS by Scanning the Bank for One-Away Neighbours approach?

When to use it: Offer when the bank is small (here ≤ 10): instead of generating 24 mutations per gene, just scan the bank for genes a Hamming distance of 1 away. This variant keeps the exact same BFS skeleton but swaps how neighbours are discovered. **Generate vs scan.** The optimal approach *generates* every one-character mutation (8 × 3 = 24 strings) and tests each against the bank set. The alternative *scans*: for the current gene, walk the whole bank and keep any candidate whose Hamming distance from the current gene is exactly 1. Both produce the identical neighbour set — genes that differ in one position and are valid — they just trade off differently. **When scanning wins.** The generate-and-hash approach costs roughly `L × |alphabet|` per gene, independent of bank size; scanning costs `B × L` per gene. With a four-letter alphabet and `L = 8` the generate cost is ~24 hashes, while scanning a bank of `B ≤ 10` is ~10 cheap comparisons. For these constraints scanning is marginally simpler and avoids allocating mutated strings. For a *large* dictionary (as in Word Ladder), generation wins decisively because it doesn't grow with the dictionary size. **The Hamming-distance helper.** `oneAway(a, b)` counts mismatched positions and bails out the moment the count exceeds 1 — so it's O(L) but usually returns early. Two genes are neighbours exactly when that count equals 1. **Same correctness guarantees.** Because the neighbour set is identical, the BFS still explores by increasing distance and the first arrival at `endGene` is still the minimum. The visited set still prevents revisits and cycles. The only thing that changed is the constant-factor cost of finding neighbours. Time complexity: O(B² × L). Space complexity: O(B).

LCPractice

Graphs · 10 of 34 · 10 min

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Given the two gene strings startGene and endGene and the gene bank, return the minimum number of mutations needed to mutate from `startGene` to `endGene`. If there is no such a mutation, return -1.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

In plain English

We want the fewest single-character changes to turn startGene into endGene, where every intermediate (and the final) gene must appear in the bank. That's a shortest path on a graph whose nodes are genes and whose edges connect genes one character apart — solved by BFS.

Examples

Example 1

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Note: One character (the last) changes from 'T' to 'A', and the result is in the bank.

Example 2

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
Note: AACCGGTT → AACCGGTA → AAACGGTA, two valid mutations via the bank.

Example 3

Input: startGene = "AAAAACCC", endGene = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
Output: 3
Note: AAAAACCC → AAAACCCC → AAACCCCC → AACCCCCC, three single-character steps all present in the bank.

Constraints

0 ≤ bank.length ≤ 10
startGene.length == endGene.length == bank[i].length == 8
startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T']

Clarifying questions4First question: Does every intermediate gene need to be in the bank, or only the final one?Explore questions

Q1.Does every intermediate gene need to be in the bank, or only the final one?
Every mutated gene along the way must be in the bank. The start is assumed valid even if it isn't listed. So endGene must be in the bank to be reachable.
Q2.Is a 'mutation' always exactly one character change?
Yes — exactly one of the 8 positions changes to a different base from {A, C, G, T}. Two genes are neighbours iff their Hamming distance is 1.
Q3.What should I return if endGene can't be reached?
-1. That includes the case where endGene isn't in the bank at all (and differs from startGene).
Q4.What if startGene already equals endGene?
Then zero mutations are needed — return 0. My BFS returns this immediately on the first dequeue.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Treat each valid gene string as a node and connect two genes with an edge when they differ by exactly one character (and the target is in the bank). The fewest mutations from start to end is then the shortest path on this unweighted graph → BFS. From a gene, generate all single-character mutations (8 positions × the other 3 of {A,C,G,T}), keep the ones present in the bank, and explore them level by level. The layer at which you first dequeue endGene is the answer; if the queue empties first, return -1. A hash set of the bank gives O(1) validity checks.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise a 'minimum number of single edits through valid states' problem as a shortest-path BFS over an implicit graph, and use a hash set for O(1) bank membership.

Where candidates slip

Using DFS (finds a path, not the shortest), forgetting to mark genes visited (revisiting and looping), or doing O(n) linear scans of the bank instead of a hash-set lookup.

How to stand out

Frame it as Word Ladder with alphabet {A,C,G,T}, explain why BFS guarantees the minimum, choose the cheaper neighbour-generation strategy for the given sizes, and mention bidirectional BFS as a scaling option.

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	BFS by Generating One-Character Mutations (Optimal)Optimal	`O(B × L × 4)`	`O(B)`	Lead with this. Phrase it as 'fewest single edits through a dictionary is a shortest path on an unweighted graph, so BFS, with a hash set for valid genes'.	Read
2	BFS by Scanning the Bank for One-Away Neighbours	`O(B² × L)`	`O(B)`	Offer when the bank is small (here ≤ 10): instead of generating 24 mutations per gene, just scan the bank for genes a Hamming distance of 1 away.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewFewest single-char edits start → endEdges equal cost?Yes (1 per mutation)NoExplore 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 · Optimal

BFS by Generating One-Character Mutations (Optimal)

TimeO(B × L × 4)SpaceO(B)

Lead with this. Phrase it as 'fewest single edits through a dictionary is a shortest path on an unweighted graph, so BFS, with a hash set for valid genes'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Picture each valid gene as a node; two genes are connected if they differ in exactly one position. The answer is the shortest path from start to end.

2Hint 2Explore hint

Every mutation costs the same (one step), so BFS finds the minimum. Put the bank in a hash set so checking 'is this gene valid?' is O(1).

3Hint 3Explore hint

From a gene, generate all neighbours: for each of the 8 positions, swap in each of the other 3 bases. Keep the ones in the bank and not yet visited; explore level by level and count layers.

A · Core idea

The phrase 'minimum number of mutations' over equal-cost steps is the unmistakable signature of a shortest-path BFS.

Why this is a graph problem. Make every valid gene a node. Draw an edge between two genes whenever they differ in exactly one of the 8 characters — that's a single legal mutation. The number of mutations from start to end is the length of the shortest path between those two nodes. Because each edge costs exactly one mutation, the graph is unweighted, and BFS visits nodes in strictly increasing distance from the source. So the first time BFS reaches endGene, it has reached it via the fewest possible mutations. DFS, by contrast, would dive down a chain and might find a long route first — it cannot guarantee the minimum.

Why a hash set for the bank. A mutation is only legal if the resulting gene is in the bank. We'll test that condition once per generated candidate, so it must be fast. Loading the bank into a hash set turns each validity test into an O(1) lookup; a linear scan of the bank per candidate would multiply the running time by the bank size for no reason. This is the 'hash-map' half of the pattern — the set is what makes the BFS efficient.

Generating neighbours. From the current gene we enumerate every one-character mutation: for each of the 8 positions, replace its base with each of the other three letters in {A, C, G, T}. That's at most 8 × 3 = 24 candidates per gene. We keep a candidate only if it's in the bank and hasn't been visited, then mark it visited and enqueue it. Skipping the position's current letter avoids generating the gene unchanged.

Mark visited on enqueue. As with every BFS, we record a gene as visited the instant we enqueue it, not when we dequeue it. Otherwise the same gene can be enqueued by several neighbours, inflating the queue and re-expanding nodes. The visited set also doubles as cycle protection — gene graphs can have cycles (A↔B mutations), and without visited tracking BFS would loop forever.

Counting layers. We drain the queue one full layer per outer iteration and bump the mutation counter after each layer. The layer index when endGene is first dequeued is the minimum count. Seeding the queue with startGene (marked visited) and checking equality on dequeue means start == end correctly returns 0. If the queue empties without ever reaching endGene, no valid path exists and we return -1.

B · Visual dry run

Interactive dry run

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

start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Interactive diagram

Gene graph for example 2

steps=0

Active call / nodeSupporting contextReturned stateNot active

Each edge is a single-character mutation through a valid bank gene; BFS finds the shortest chain.

Final result2

C · Code with teaching comments

solution.javaJava

BFS by Generating One-Character Mutations (Optimal) — optimal

6 teaching notes

1
public int minMutation(String startGene, String endGene, String[] bank) {
2
    // Hash set gives O(1) 'is this gene valid?' checks — the core of the hash-map half
3
    // of the pattern.
4
    Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
5
    char[] choices = {'A', 'C', 'G', 'T'};
6
    Queue<String> queue = new LinkedList<>();
7
    Set<String> visited = new HashSet<>();
8
    queue.offer(startGene);
9
    visited.add(startGene);
10
    int mutations = 0;
11
    while (!queue.isEmpty()) {
12
        int size = queue.size();
13
        for (int i = 0; i < size; i++) {
14
            String gene = queue.poll();
15
            if (gene.equals(endGene)) {
16
                return mutations;
17
            }
18
            char[] arr = gene.toCharArray();
19
            for (int p = 0; p < arr.length; p++) {
20
                char original = arr[p];
21
                for (char ch : choices) {
22
                    if (ch == original) {
23
                        continue;
24
                    }
25
                    arr[p] = ch;
26
                    String mutated = new String(arr);
27
                    if (bankSet.contains(mutated) && !visited.contains(mutated)) {
28
                        visited.add(mutated);
29
                        queue.offer(mutated);
30
                    }
31
                }
32
                arr[p] = original; // restore for the next position
33
            }
34
        }
35
        mutations++;
36
    }
37
    return -1;
38
}

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

D · Why it works and complexityO(B × L × 4) timeO(B) spaceOpen the invariant and proofExplore the proof

This is Word Ladder with the alphabet pinned to four letters and the length pinned to eight. The shape — 'BFS over one-edit neighbours, validity checked against a hash set' — is the reusable template. Recognising that two superficially different problems (genes vs words) are the same graph is exactly the transfer interviewers look for.

ComplexityO(B × L × 4) time, O(B) space — Let B be the bank size and L = 8 the gene length. Each gene is dequeued once and generates L × 3 candidate mutations, each an O(L) string build and O(1) set lookup → O(B × L × 4) ≈ O(B) for the tiny fixed L. The visited set and bank set are O(B) space.

E · Edge cases and pitfalls7start == end — Dequeued immediately and equals end → returns 0.Explore edge cases

Edge cases handled

start == endDequeued immediately and equals end → returns 0.
endGene not in bank (and != start)It's never generated as a valid neighbour → queue empties → return -1.
empty bankNo valid mutations exist; unless start == end, returns -1.

Pitfalls

Using DFS — yields a path, not the minimum number of mutations.
Scanning the bank list per candidate instead of a hash-set lookup — needlessly O(B) each time.
Forgetting the visited set — gene graphs have cycles, so BFS would loop forever.
Not restoring the mutated character before trying the next position.

03.2

Approach 2 of 2

BFS by Scanning the Bank for One-Away Neighbours

TimeO(B² × L)SpaceO(B)

Offer when the bank is small (here ≤ 10): instead of generating 24 mutations per gene, just scan the bank for genes a Hamming distance of 1 away.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Neighbour generation has two flavours: build all single-character mutations, or scan the candidate list for entries that differ in exactly one position.

2Hint 2Explore hint

When the bank is tiny, scanning it (B genes, each an O(L) Hamming-distance check) can be simpler than generating 24 mutations and hashing each.

3Hint 3Explore hint

Everything else — BFS, visited set, layer counting — is identical.

A · Core idea

This variant keeps the exact same BFS skeleton but swaps how neighbours are discovered.

Generate vs scan. The optimal approach generates every one-character mutation (8 × 3 = 24 strings) and tests each against the bank set. The alternative scans: for the current gene, walk the whole bank and keep any candidate whose Hamming distance from the current gene is exactly 1. Both produce the identical neighbour set — genes that differ in one position and are valid — they just trade off differently.

When scanning wins. The generate-and-hash approach costs roughly L × |alphabet| per gene, independent of bank size; scanning costs B × L per gene. With a four-letter alphabet and L = 8 the generate cost is ~24 hashes, while scanning a bank of B ≤ 10 is ~10 cheap comparisons. For these constraints scanning is marginally simpler and avoids allocating mutated strings. For a large dictionary (as in Word Ladder), generation wins decisively because it doesn't grow with the dictionary size.

The Hamming-distance helper. oneAway(a, b) counts mismatched positions and bails out the moment the count exceeds 1 — so it's O(L) but usually returns early. Two genes are neighbours exactly when that count equals 1.

Same correctness guarantees. Because the neighbour set is identical, the BFS still explores by increasing distance and the first arrival at endGene is still the minimum. The visited set still prevents revisits and cycles. The only thing that changed is the constant-factor cost of finding neighbours.

B · Visual dry run

Interactive dry run

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

start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]

steps=0

AAAAACCC: bank scan → AAAACCCC is 1-away, enqueue

Statequeue=[AAAACCCC]

Final result3

C · Code with teaching comments

Reference implementation previewpublic int minMutation(String startGene, String endGene, String[] bank) { Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>(); queue.offer(startGene); visited.add(startGene);Explore the full code

solution.javaJava

BFS by Scanning the Bank for One-Away Neighbours — reference

4 teaching notes

1
public int minMutation(String startGene, String endGene, String[] bank) {
2
    Queue<String> queue = new LinkedList<>();
3
    Set<String> visited = new HashSet<>();
4
    queue.offer(startGene);
5
    visited.add(startGene);
6
    int mutations = 0;
7
    while (!queue.isEmpty()) {
8
        int size = queue.size();
9
        for (int i = 0; i < size; i++) {
10
            String gene = queue.poll();
11
            if (gene.equals(endGene)) {
12
                return mutations;
13
            }
14
            for (String candidate : bank) {
15
                if (!visited.contains(candidate) && oneAway(gene, candidate)) {
16
                    visited.add(candidate);
17
                    queue.offer(candidate);
18
                }
19
            }
20
        }
21
        mutations++;
22
    }
23
    return -1;
24
}
25
 
26
private boolean oneAway(String a, String b) {
27
    int diff = 0;
28
    for (int i = 0; i < a.length(); i++) {
29
        if (a.charAt(i) != b.charAt(i)) {
30
            diff++;
31
            if (diff > 1) {
32
                return false;
33
            }
34
        }
35
    }
36
    // Neighbours differ in exactly one position; identical genes (diff 0) are not
37
    // neighbours.
38
    return diff == 1;
39
}

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

D · Why it works and complexityO(B² × L) timeO(B) spaceOpen the invariant and proofExplore the proof

Neighbour generation is a tunable knob in transformation BFS: generate candidates when the alphabet is small and the dictionary is large; scan the dictionary when it's small. Recognising that both strategies yield the same graph — and choosing based on the input sizes — is a mark of fluency.

ComplexityO(B² × L) time, O(B) space — Each of B genes, when dequeued, compares against all B bank genes with an O(L) Hamming check → O(B² × L). For B ≤ 10 and L = 8 that's trivial, and it avoids building mutated strings.

E · Edge cases and pitfalls6very small bank — Scanning beats generation here — fewer comparisons than 24 mutations.Explore edge cases

Edge cases handled

very small bankScanning beats generation here — fewer comparisons than 24 mutations.
large dictionary (Word Ladder)Generation would win; scanning becomes O(B²·L) and grows with the dictionary.
start == endReturns 0 immediately on the first dequeue.

Pitfalls

Treating identical genes (Hamming distance 0) as neighbours — they're not.
Scanning the bank when it's huge — O(B²) blows up; generate mutations instead.
Omitting the early exit in the Hamming check on longer strings.

Practice

Try the solution yourself

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

Editable code previewpublic int minMutation(String startGene, String endGene, String[] bank) { Set<String> bankSet = new HashSet<>(Arrays.asList(bank)); char[] choices = {'A', 'C', 'G', 'T'}; Queue<String> queue = new LinkedList<>(); Set<String> visited = new HashSet<>();Explore the playground

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

public int minMutation(String startGene, String endGene, String[] bank) {
    Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
    char[] choices = {'A', 'C', 'G', 'T'};
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.offer(startGene);
    visited.add(startGene);
    int mutations = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            String gene = queue.poll();
            if (gene.equals(endGene)) {
                return mutations;
            }
            char[] arr = gene.toCharArray();
            for (int p = 0; p < arr.length; p++) {
                char original = arr[p];
                for (char ch : choices) {
                    if (ch == original) {
                        continue;
                    }
                    arr[p] = ch;
                    String mutated = new String(arr);
                    if (bankSet.contains(mutated) && !visited.contains(mutated)) {
                        visited.add(mutated);
                        queue.offer(mutated);
                    }
                }
                arr[p] = original; // restore for the next position
            }
        }
        mutations++;
    }
    return -1;
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Forgetting the visited set

Gene graphs are full of cycles (A can mutate to B and back). Without tracking visited genes, BFS re-enqueues the same nodes forever and never terminates.

Explore the code comparison

Don't write this

queue = deque([startGene])
while queue:
    gene = queue.popleft()
    for candidate in bank:
        if one_away(gene, candidate):
            queue.append(candidate)   # no visited check → infinite loop

Write this instead

queue = deque([startGene])
visited = {startGene}
while queue:
    gene = queue.popleft()
    for candidate in bank:
        if candidate not in visited and one_away(gene, candidate):
            visited.add(candidate)
            queue.append(candidate)

Linear bank scan per candidate

When generating mutations, validating each against a list is O(B) per check. With many candidates this multiplies the runtime needlessly; a hash set makes each check O(1).

Explore the code comparison

Don't write this

String mutated = new String(arr);
if (Arrays.asList(bank).contains(mutated)) { // O(B) per candidate
    queue.offer(mutated);
}

Write this instead

Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
// ...
String mutated = new String(arr);
if (bankSet.contains(mutated)) { // O(1)
    queue.offer(mutated);
}

Choosing DFS for a shortest-path question

DFS follows one mutation chain to its end and may report a long route before a short one exists. Only BFS, exploring by increasing distance, guarantees the minimum number of mutations.

Explore the code comparison

Don't write this

def dfs(gene, count):
    if gene == endGene:
        return count          # not necessarily minimal
    for candidate in bank:
        if one_away(gene, candidate):
            return dfs(candidate, count + 1)

Write this instead

queue = deque([startGene]); steps = 0
while queue:
    for _ in range(len(queue)):
        gene = queue.popleft()
        if gene == endGene:
            return steps      # BFS ⇒ first arrival is minimal
    steps += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shortest transformation sequence → BFS over one-edit neighbours (hash set for the bank)

Code pattern to memorize

bankSet = set(bank); seen = {start}; q = [start]; steps = 0
while q:
    for gene in this layer:
        if gene == end: return steps
        for each position p, each base b != gene[p]:
            cand = mutate(gene, p, b)
            if cand in bankSet and cand not in seen:
                seen.add(cand); q.push(cand)
    steps += 1
return -1

Rules to remember

1Each single-character change is one move of equal cost, so BFS (not DFS) gives the minimum.
2A mutation is only legal if the result is in the bank — store the bank in a hash set for O(1) checks.
3Generate neighbours by trying each of the 8 positions with the other 3 bases of {A, C, G, T}.
4Mark a gene visited when enqueued so it isn't expanded twice.
5If endGene is unreachable (never dequeued) return -1; if start == end, the answer is 0.

Use this pattern when

Shortest number of single-step edits between two strings/states
Each intermediate state must be valid (in a dictionary / bank)
Implicit graph where edges are 'differs by one unit' transformations
Word-ladder-style minimum transformation problems

Choose another pattern when

You need ALL transformation sequences → DFS / backtracking, not BFS alone
Edits have different costs → weighted shortest path (Dijkstra)
No validity constraint and unlimited alphabet → the graph is too dense to enumerate; rethink

Interview takeaway

Minimum Genetic Mutation is Word Ladder with a 4-letter alphabet and fixed length 8. Once you see 'fewest single-character changes through a dictionary', it's BFS over one-edit neighbours with a hash set for validity — the same template solves Word Ladder and Open the Lock.

Continue

Transfer the pattern to another problem

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

Transferable patternBFS for shortest transformation over an implicit graph of one-edit neighbours, with a hash set for O(1) validity checks. Same template as Word Ladder, Open the Lock, and Word Ladder II — the tell is 'minimum number of single-character/single-step changes through valid states'.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Word Ladder
Same BFS over one-edit neighbours, but with a 26-letter alphabet and variable word length — generation wins over scanning.
Open the Lock
Coming soon
BFS over 4-digit lock states; each wheel turn (±1 mod 10) is a one-edit neighbour, with deadends blocked.
Word Ladder II
Coming soon
Return ALL shortest transformation sequences — BFS to build the layer graph, then DFS to reconstruct paths.
Snakes and Ladders
Another unweighted shortest-path BFS, on a flattened board instead of strings.

Same pattern

←

Course Schedule II

Continue · Next problem

Snakes and Ladders

mediumGraphsLC #433Sometimes asked

Minimum Genetic Mutation

LCPractice

Graphs · 10 of 34 · 10 min

A gene string can be represented by an 8-character long string, with choices from 'A', 'C', 'G', and 'T'.

Suppose we need to investigate a mutation from a gene string startGene to a gene string endGene where one mutation is defined as one single character changed in the gene string.

For example, "AACCGGTT" --> "AACCGGTA" is one mutation.

There is also a gene bank that records all the valid gene mutations. A gene must be in bank to make it a valid gene string.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

In plain English

Examples

Example 1

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1
Note: One character (the last) changes from 'T' to 'A', and the result is in the bank.

Example 2

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2
Note: AACCGGTT → AACCGGTA → AAACGGTA, two valid mutations via the bank.

Example 3

Input: startGene = "AAAAACCC", endGene = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
Output: 3
Note: AAAAACCC → AAAACCCC → AAACCCCC → AACCCCCC, three single-character steps all present in the bank.

Constraints

0 ≤ bank.length ≤ 10
startGene.length == endGene.length == bank[i].length == 8
startGene, endGene, and bank[i] consist of only the characters ['A', 'C', 'G', 'T']

Clarifying questions4First question: Does every intermediate gene need to be in the bank, or only the final one?Explore questions

Q1.Does every intermediate gene need to be in the bank, or only the final one?
Every mutated gene along the way must be in the bank. The start is assumed valid even if it isn't listed. So endGene must be in the bank to be reachable.
Q2.Is a 'mutation' always exactly one character change?
Yes — exactly one of the 8 positions changes to a different base from {A, C, G, T}. Two genes are neighbours iff their Hamming distance is 1.
Q3.What should I return if endGene can't be reached?
-1. That includes the case where endGene isn't in the bank at all (and differs from startGene).
Q4.What if startGene already equals endGene?
Then zero mutations are needed — return 0. My BFS returns this immediately on the first dequeue.

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 recognise a 'minimum number of single edits through valid states' problem as a shortest-path BFS over an implicit graph, and use a hash set for O(1) bank membership.

Where candidates slip

Using DFS (finds a path, not the shortest), forgetting to mark genes visited (revisiting and looping), or doing O(n) linear scans of the bank instead of a hash-set lookup.

How to stand out

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	BFS by Generating One-Character Mutations (Optimal)Optimal	`O(B × L × 4)`	`O(B)`	Lead with this. Phrase it as 'fewest single edits through a dictionary is a shortest path on an unweighted graph, so BFS, with a hash set for valid genes'.	Read
2	BFS by Scanning the Bank for One-Away Neighbours	`O(B² × L)`	`O(B)`	Offer when the bank is small (here ≤ 10): instead of generating 24 mutations per gene, just scan the bank for genes a Hamming distance of 1 away.	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 · Optimal

BFS by Generating One-Character Mutations (Optimal)

TimeO(B × L × 4)SpaceO(B)

Lead with this. Phrase it as 'fewest single edits through a dictionary is a shortest path on an unweighted graph, so BFS, with a hash set for valid genes'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Picture each valid gene as a node; two genes are connected if they differ in exactly one position. The answer is the shortest path from start to end.

2Hint 2Explore hint

Every mutation costs the same (one step), so BFS finds the minimum. Put the bank in a hash set so checking 'is this gene valid?' is O(1).

3Hint 3Explore hint

From a gene, generate all neighbours: for each of the 8 positions, swap in each of the other 3 bases. Keep the ones in the bank and not yet visited; explore level by level and count layers.

A · Core idea

The phrase 'minimum number of mutations' over equal-cost steps is the unmistakable signature of a shortest-path BFS.

B · Visual dry run

Interactive dry run

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

start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]

Interactive diagram

Gene graph for example 2

steps=0

Active call / nodeSupporting contextReturned stateNot active

Each edge is a single-character mutation through a valid bank gene; BFS finds the shortest chain.

Final result2

C · Code with teaching comments

solution.javaJava

BFS by Generating One-Character Mutations (Optimal) — optimal

6 teaching notes

1
public int minMutation(String startGene, String endGene, String[] bank) {
2
    // Hash set gives O(1) 'is this gene valid?' checks — the core of the hash-map half
3
    // of the pattern.
4
    Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
5
    char[] choices = {'A', 'C', 'G', 'T'};
6
    Queue<String> queue = new LinkedList<>();
7
    Set<String> visited = new HashSet<>();
8
    queue.offer(startGene);
9
    visited.add(startGene);
10
    int mutations = 0;
11
    while (!queue.isEmpty()) {
12
        int size = queue.size();
13
        for (int i = 0; i < size; i++) {
14
            String gene = queue.poll();
15
            if (gene.equals(endGene)) {
16
                return mutations;
17
            }
18
            char[] arr = gene.toCharArray();
19
            for (int p = 0; p < arr.length; p++) {
20
                char original = arr[p];
21
                for (char ch : choices) {
22
                    if (ch == original) {
23
                        continue;
24
                    }
25
                    arr[p] = ch;
26
                    String mutated = new String(arr);
27
                    if (bankSet.contains(mutated) && !visited.contains(mutated)) {
28
                        visited.add(mutated);
29
                        queue.offer(mutated);
30
                    }
31
                }
32
                arr[p] = original; // restore for the next position
33
            }
34
        }
35
        mutations++;
36
    }
37
    return -1;
38
}

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

D · Why it works and complexityO(B × L × 4) timeO(B) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7start == end — Dequeued immediately and equals end → returns 0.Explore edge cases

Edge cases handled

start == endDequeued immediately and equals end → returns 0.
endGene not in bank (and != start)It's never generated as a valid neighbour → queue empties → return -1.
empty bankNo valid mutations exist; unless start == end, returns -1.

Pitfalls

Using DFS — yields a path, not the minimum number of mutations.
Scanning the bank list per candidate instead of a hash-set lookup — needlessly O(B) each time.
Forgetting the visited set — gene graphs have cycles, so BFS would loop forever.
Not restoring the mutated character before trying the next position.

03.2

Approach 2 of 2

BFS by Scanning the Bank for One-Away Neighbours

TimeO(B² × L)SpaceO(B)

Offer when the bank is small (here ≤ 10): instead of generating 24 mutations per gene, just scan the bank for genes a Hamming distance of 1 away.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Neighbour generation has two flavours: build all single-character mutations, or scan the candidate list for entries that differ in exactly one position.

2Hint 2Explore hint

When the bank is tiny, scanning it (B genes, each an O(L) Hamming-distance check) can be simpler than generating 24 mutations and hashing each.

3Hint 3Explore hint

Everything else — BFS, visited set, layer counting — is identical.

A · Core idea

This variant keeps the exact same BFS skeleton but swaps how neighbours are discovered.

B · Visual dry run

Interactive dry run

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

start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]

steps=0

AAAAACCC: bank scan → AAAACCCC is 1-away, enqueue

Statequeue=[AAAACCCC]

Final result3

C · Code with teaching comments

solution.javaJava

BFS by Scanning the Bank for One-Away Neighbours — reference

4 teaching notes

1
public int minMutation(String startGene, String endGene, String[] bank) {
2
    Queue<String> queue = new LinkedList<>();
3
    Set<String> visited = new HashSet<>();
4
    queue.offer(startGene);
5
    visited.add(startGene);
6
    int mutations = 0;
7
    while (!queue.isEmpty()) {
8
        int size = queue.size();
9
        for (int i = 0; i < size; i++) {
10
            String gene = queue.poll();
11
            if (gene.equals(endGene)) {
12
                return mutations;
13
            }
14
            for (String candidate : bank) {
15
                if (!visited.contains(candidate) && oneAway(gene, candidate)) {
16
                    visited.add(candidate);
17
                    queue.offer(candidate);
18
                }
19
            }
20
        }
21
        mutations++;
22
    }
23
    return -1;
24
}
25
 
26
private boolean oneAway(String a, String b) {
27
    int diff = 0;
28
    for (int i = 0; i < a.length(); i++) {
29
        if (a.charAt(i) != b.charAt(i)) {
30
            diff++;
31
            if (diff > 1) {
32
                return false;
33
            }
34
        }
35
    }
36
    // Neighbours differ in exactly one position; identical genes (diff 0) are not
37
    // neighbours.
38
    return diff == 1;
39
}

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

D · Why it works and complexityO(B² × L) timeO(B) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6very small bank — Scanning beats generation here — fewer comparisons than 24 mutations.Explore edge cases

Edge cases handled

very small bankScanning beats generation here — fewer comparisons than 24 mutations.
large dictionary (Word Ladder)Generation would win; scanning becomes O(B²·L) and grows with the dictionary.
start == endReturns 0 immediately on the first dequeue.

Pitfalls

Treating identical genes (Hamming distance 0) as neighbours — they're not.
Scanning the bank when it's huge — O(B²) blows up; generate mutations instead.
Omitting the early exit in the Hamming check on longer strings.

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.

Forgetting the visited set

Gene graphs are full of cycles (A can mutate to B and back). Without tracking visited genes, BFS re-enqueues the same nodes forever and never terminates.

Explore the code comparison

Don't write this

queue = deque([startGene])
while queue:
    gene = queue.popleft()
    for candidate in bank:
        if one_away(gene, candidate):
            queue.append(candidate)   # no visited check → infinite loop

Write this instead

queue = deque([startGene])
visited = {startGene}
while queue:
    gene = queue.popleft()
    for candidate in bank:
        if candidate not in visited and one_away(gene, candidate):
            visited.add(candidate)
            queue.append(candidate)

Linear bank scan per candidate

When generating mutations, validating each against a list is O(B) per check. With many candidates this multiplies the runtime needlessly; a hash set makes each check O(1).

Explore the code comparison

Don't write this

String mutated = new String(arr);
if (Arrays.asList(bank).contains(mutated)) { // O(B) per candidate
    queue.offer(mutated);
}

Write this instead

Set<String> bankSet = new HashSet<>(Arrays.asList(bank));
// ...
String mutated = new String(arr);
if (bankSet.contains(mutated)) { // O(1)
    queue.offer(mutated);
}

Choosing DFS for a shortest-path question

DFS follows one mutation chain to its end and may report a long route before a short one exists. Only BFS, exploring by increasing distance, guarantees the minimum number of mutations.

Explore the code comparison

Don't write this

def dfs(gene, count):
    if gene == endGene:
        return count          # not necessarily minimal
    for candidate in bank:
        if one_away(gene, candidate):
            return dfs(candidate, count + 1)

Write this instead

queue = deque([startGene]); steps = 0
while queue:
    for _ in range(len(queue)):
        gene = queue.popleft()
        if gene == endGene:
            return steps      # BFS ⇒ first arrival is minimal
    steps += 1

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Shortest transformation sequence → BFS over one-edit neighbours (hash set for the bank)

Code pattern to memorize

bankSet = set(bank); seen = {start}; q = [start]; steps = 0
while q:
    for gene in this layer:
        if gene == end: return steps
        for each position p, each base b != gene[p]:
            cand = mutate(gene, p, b)
            if cand in bankSet and cand not in seen:
                seen.add(cand); q.push(cand)
    steps += 1
return -1

Rules to remember

1Each single-character change is one move of equal cost, so BFS (not DFS) gives the minimum.
2A mutation is only legal if the result is in the bank — store the bank in a hash set for O(1) checks.
3Generate neighbours by trying each of the 8 positions with the other 3 bases of {A, C, G, T}.
4Mark a gene visited when enqueued so it isn't expanded twice.
5If endGene is unreachable (never dequeued) return -1; if start == end, the answer is 0.

Use this pattern when

Shortest number of single-step edits between two strings/states
Each intermediate state must be valid (in a dictionary / bank)
Implicit graph where edges are 'differs by one unit' transformations
Word-ladder-style minimum transformation problems

Choose another pattern when

You need ALL transformation sequences → DFS / backtracking, not BFS alone
Edits have different costs → weighted shortest path (Dijkstra)
No validity constraint and unlimited alphabet → the graph is too dense to enumerate; rethink

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

Word Ladder
Same BFS over one-edit neighbours, but with a 26-letter alphabet and variable word length — generation wins over scanning.
Open the Lock
Coming soon
BFS over 4-digit lock states; each wheel turn (±1 mod 10) is a one-edit neighbour, with deadends blocked.
Word Ladder II
Coming soon
Return ALL shortest transformation sequences — BFS to build the layer graph, then DFS to reconstruct paths.
Snakes and Ladders
Another unweighted shortest-path BFS, on a flattened board instead of strings.

Same pattern

←

Course Schedule II

Continue · Next problem

Snakes and Ladders