433. Minimum Genetic Mutation Solution Guide

Q: Is Minimum Genetic Mutation easy or hard?

Minimum Genetic Mutation is rated Medium difficulty. The main challenge is recognizing that the problem forms an implicit graph where each valid mutation is an edge. Once modeled correctly, the BFS implementation is straightforward.

Q: How to solve Minimum Genetic Mutation in O(N)?

An optimized BFS with a hash set for the gene bank effectively runs in near O(N × L) time since L is a small constant. Each valid gene is processed once, and mutation candidates are generated by changing one character at a time. Using a set allows O(1) lookup when verifying whether a mutation exists in the bank.

Q: What is the best approach for Minimum Genetic Mutation?

Breadth-First Search (BFS) is the best approach because the problem asks for the minimum number of mutations, which maps directly to the shortest path in an unweighted graph. Each gene represents a node and each valid one-character mutation forms an edge. BFS guarantees the first time you reach the target gene is the minimum number of steps.

Q: What data structure is used in Minimum Genetic Mutation?

The core data structures are a queue for BFS traversal and a hash set for storing the gene bank and visited genes. The queue processes genes level by level, while the hash set allows constant-time checks to validate mutations and prevent revisiting states.

Q: What is the time complexity of Minimum Genetic Mutation?

The typical BFS solution runs in O(N × L × 4) time, where N is the number of genes in the bank and L is the gene length (usually 8). For every gene explored, you attempt L positions and 4 possible characters. Space complexity is O(N) for the queue and visited set.

Q: Minimum Genetic Mutation Python or Java solution approach?

Both Python and Java implementations typically use BFS with a queue and a hash set. Generate mutations by iterating over each position in the gene string and replacing it with A, C, G, or T. If the mutated gene exists in the bank and hasn't been visited, add it to the queue for the next BFS level.

Q: Is Minimum Genetic Mutation asked at Google, Amazon, or Meta?

Minimum Genetic Mutation is a common interview-style graph problem similar to Word Ladder. Variants that use BFS on strings or transformation graphs have appeared in interviews at companies like Amazon, Google, and Meta. Interviewers use it to test graph traversal and state-space search.

The problem

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 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 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.

Example 1:

Input: startGene = "AACCGGTT", endGene = "AACCGGTA", bank = ["AACCGGTA"]
Output: 1

Example 2:

Input: startGene = "AACCGGTT", endGene = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
Output: 2

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'].

Approach overview

Problem Overview: You start with a gene string and need to transform it into a target gene. Each mutation changes exactly one character, and every intermediate gene must exist in the given bank. The task is to compute the minimum number of mutations required, or return -1 if the transformation is impossible.

Approach 1: Breadth-First Search (BFS) (Time: O(N × L × 4), Space: O(N))

Treat each gene as a node in an implicit graph. Two genes are connected if they differ by exactly one character. Start a BFS from the startGene and explore all valid mutations level by level. For each position in the gene string, try replacing it with the four possible characters (A, C, G, T). If the new gene exists in the bank and has not been visited, push it into the queue. Because Breadth-First Search explores by distance, the first time you reach endGene gives the minimum mutation count.

Using a hash table or set for the bank enables O(1) membership checks while generating mutations. The gene length L is fixed (typically 8), so each state generates at most L × 4 candidates. BFS works well here because the problem asks for the shortest transformation path in an unweighted graph.

Approach 2: Bidirectional BFS (Time: O(N × L × 4), Space: O(N))

Bidirectional BFS improves practical performance by searching from both the start and end genes simultaneously. Maintain two frontier sets: one expanding from startGene and another from endGene. At each step, expand the smaller frontier by generating all one-character mutations and checking whether any mutation appears in the opposite frontier.

This approach reduces the search depth roughly by half, which significantly cuts the number of explored states when the bank is large. A hash set stores the valid genes, and visited genes are removed to avoid revisiting. The mutation generation logic is the same as in the standard BFS, still operating on the string representation of genes.

Recommended for interviews: The standard BFS solution is what most interviewers expect first because it directly models the problem as a shortest-path search in an unweighted graph. Implementing BFS with a queue and hash set demonstrates solid graph traversal fundamentals. After presenting it, mentioning Bidirectional BFS shows deeper optimization awareness and stronger problem-solving maturity.

Approach 1: Breadth-First Search (BFS) Approach

In this approach, we utilize the Breadth-First Search algorithm to explore the mutation process. The problem can be transformed into finding the shortest path in an unweighted graph (where nodes are gene strings and edges represent valid transformations as per the gene bank).

Steps involved:

Use a queue to perform the BFS starting from the startGene.
Use a set to store visited nodes to prevent re-processing.
The queue will store pairs representing the current gene string and the number of mutations so far.
Iteratively explore valid mutations (one letter changes) that are in the gene bank.
If the endGene is reached, return the mutation count.
If the queue is exhausted without finding the endGene, return -1.

Python

from collections import deque

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: [str]) -> int:
        gene_set = set(bank)
        if endGene not in gene_set:
            return -1

        queue = deque([(startGene, 0)])
        while queue:
            current_gene, mutations = queue.popleft()

            if current_gene == endGene:
                return mutations

            for i in range(len(current_gene)):
                for nucleotide in 'ACGT':
                    if current_gene[i] != nucleotide:
                        mutated_gene = current_gene[:i] + nucleotide + current_gene[i + 1:]

                        if mutated_gene in gene_set:
                            gene_set.remove(mutated_gene)
                            queue.append((mutated_gene, mutations + 1))
        return -1

print(Solution().minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]))

Java

import java.util.*;

public class GeneticMutation {
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> geneBank = new HashSet<>(Arrays.asList(bank));
        if (!geneBank.contains(endGene)) return -1;

        char[] choices = {'A', 'C', 'G', 'T'};
        Queue<Pair<String, Integer>> queue = new LinkedList<>();
        queue.offer(new Pair<>(startGene, 0));

        while (!queue.isEmpty()) {
            Pair<String, Integer> current = queue.poll();
            String gene = current.getKey();
            int steps = current.getValue();

            if (gene.equals(endGene)) return steps;

            for (int i = 0; i < gene.length(); i++) {
                char old = gene.charAt(i);
                for (char nucleotide : choices) {
                    if (nucleotide == old) continue;
                    StringBuilder modifiedGene = new StringBuilder(gene);
                    modifiedGene.setCharAt(i, nucleotide);
                    String newGene = modifiedGene.toString();
                    if (geneBank.contains(newGene)) {
                        queue.offer(new Pair<>(newGene, steps + 1));
                        geneBank.remove(newGene);
                    }
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        GeneticMutation gm = new GeneticMutation();
        String startGene = "AACCGGTT";
        String endGene = "AAACGGTA";
        String[] bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        System.out.println(gm.minMutation(startGene, endGene, bank));
    }
}

class Pair<K, V> {
    private K key;
    private V value;

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey() { return key; }
    public V getValue() { return value; }
    public void setKey(K key) { this.key = key; }
    public void setValue(V value) { this.value = value; }
}

C++

#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;

int minMutation(string startGene, string endGene, vector<string>& bank) {
    unordered_set<string> geneBank(bank.begin(), bank.end());
    if (geneBank.find(endGene) == geneBank.end()) return -1;

    vector<char> choices = {'A', 'C', 'G', 'T'};
    queue<pair<string, int>> q;
    q.push({startGene, 0});

    while (!q.empty()) {
        auto [current, steps] = q.front(); q.pop();

        if (current == endGene) return steps;

        for (int i = 0; i < current.size(); i++) {
            char original = current[i];
            for (char c : choices) {
                if (c == original) continue;
                current[i] = c;
                if (geneBank.find(current) != geneBank.end()) {
                    q.push({current, steps + 1});
                    geneBank.erase(current);
                }
            }
            current[i] = original;
        }
    }
    return -1;
}

int main() {
    vector<string> bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    cout << minMutation("AACCGGTT", "AAACGGTA", bank) << endl;
    return 0;
}

JavaScript

var minMutation = function(startGene, endGene, bank) {
    const geneSet = new Set(bank);
    if (!geneSet.has(endGene)) return -1;

    const queue = [];
    queue.push([startGene, 0]);
    const choices = ['A', 'C', 'G', 'T'];

    while (queue.length > 0) {
        let [current, steps] = queue.shift();

        if (current === endGene) return steps;

        for (let i = 0; i < current.length; i++) {
            for (let nucleotide of choices) {
                if (current[i] === nucleotide) continue;
                let mutated = current.slice(0, i) + nucleotide + current.slice(i + 1);
                if (geneSet.has(mutated)) {
                    geneSet.delete(mutated);
                    queue.push([mutated, steps + 1]);
                }
            }
        }
    }
    return -1;
};

console.log(minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]));

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

int minMutation(char *startGene, char *endGene, char **bank, int bankSize) {
    char *genes[] = {"A", "C", "G", "T"};
    int wordLen = 8;
    int maxSteps = 10;
    bool visited[maxSteps];
    memset(visited, 0, sizeof(visited));
    
    typedef struct {
        char current[9];
        int step;
    } QueueNode;
    
    QueueNode *queue = (QueueNode *)malloc(sizeof(QueueNode) * bankSize);
    int front = 0, rear = 0;
    strcpy(queue[rear].current, startGene);
    queue[rear++].step = 0;
    
    while (front < rear) {
        QueueNode current = queue[front++];
        
        if (strcmp(current.current, endGene) == 0) {
            free(queue);
            return current.step;
        }

        for (int i = 0; i < wordLen; i++) {
            char original = current.current[i];
            for (int j = 0; j < 4; j++) {
                current.current[i] = genes[j][0];

                for (int k = 0; k < bankSize; k++) {
                    if (!visited[k] && strcmp(current.current, bank[k]) == 0) {
                        visited[k] = true;
                        strcpy(queue[rear].current, bank[k]);
                        queue[rear++].step = current.step + 1;
                    }
                }

            }
            current.current[i] = original;
        }
    }
    free(queue);
    return -1;
}

int main() {
    char *startGene = "AACCGGTT";
    char *endGene = "AAACGGTA";
    char *bank[] = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    int bankSize = sizeof(bank) / sizeof(bank[0]);

    int minMutations = minMutation(startGene, endGene, bank, bankSize);
    printf("Minimum mutations: %d\n", minMutations);
    return 0;
}

using System;
using System.Collections.Generic;

public class GeneticMutation {
    public int MinMutation(string startGene, string endGene, string[] bank) {
        var geneBank = new HashSet<string>(bank);
        if (!geneBank.Contains(endGene)) return -1;

        var choices = new char[] {'A', 'C', 'G', 'T'};
        var queue = new Queue<(string gene, int steps)>();
        queue.Enqueue((startGene, 0));

        while (queue.Count > 0) {
            var (gene, steps) = queue.Dequeue();

            if (gene == endGene) return steps;

            for (int i = 0; i < gene.Length; i++) {
                var geneArray = gene.ToCharArray();
                char original = gene[i];

                foreach (var choice in choices) {
                    if (choice == original) continue;
                    geneArray[i] = choice;
                    string newGene = new string(geneArray);

                    if (geneBank.Contains(newGene)) {
                        geneBank.Remove(newGene);
                        queue.Enqueue((newGene, steps + 1));
                    }
                }
                geneArray[i] = original;
            }
        }
        return -1;
    }

    public static void Main() {
        var gm = new GeneticMutation();
        string startGene = "AACCGGTT";
        string endGene = "AAACGGTA";
        string[] bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
        Console.WriteLine(gm.MinMutation(startGene, endGene, bank));
    }
}

The Python solution uses deque for BFS, with a set for fast checks and reductions on the bank. The core idea is to iterate over each gene character, trying possible valid mutations.

Complexity

Time Complexity: O(N * M * 4) where N is number of genes and M is the gene length.

Space Complexity: O(N) for storing genes in the queue and set.

Try this approach in the editor

Approach 2: Bidirectional BFS Approach

This approach aims to optimize the BFS by conducting simultaneous searches from both the start and end genes. This reduces the search space effectively.

Steps:

Initialize forward and backward sets with the startGene and endGene, respectively.
Use a set for the gene bank to ensure quick look-up and process unvisited genes.
Iteratively expand the forward and backward sets, swapping as necessary to always expand the smaller set.
If a common gene is found in both sets, return the combined step count.
If expansion is exhausted without finding an intersection, return -1.

Python

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: [str]) -> int:
        gene_set = set(bank)
        if endGene not in gene_set:
            return -1

        forward = set([startGene])
        backward = set([endGene])
        steps = 0
        choices = 'ACGT'

        while forward and backward:
            if len(forward) > len(backward):
                forward, backward = backward, forward

            next_level = set()
            for gene in forward:
                for i in range(len(gene)):
                    for nucleotide in choices:
                        if gene[i] == nucleotide:
                            continue
                        mutated = gene[:i] + nucleotide + gene[(i + 1):]
                        if mutated in backward:
                            return steps + 1
                        if mutated in gene_set:
                            next_level.add(mutated)
                            gene_set.remove(mutated)
            forward = next_level
            steps += 1
        return -1

solution = Solution()
print(solution.minMutation("AACCGGTT", "AAACGGTA", ["AACCGGTA", "AACCGCTA", "AAACGGTA"]))

C++

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

int minMutation(string startGene, string endGene, vector<string>& bank) {
    unordered_set<string> geneBank(begin(bank), end(bank));
    if (!geneBank.count(endGene)) return -1;

    unordered_set<string> forward = {startGene};
    unordered_set<string> backward = {endGene};

    int steps = 0;
    vector<char> choices = {'A', 'C', 'G', 'T'};

    while (!forward.empty() && !backward.empty()) {
        if (forward.size() > backward.size())
            swap(forward, backward);

        unordered_set<string> nextLevel;

        for (const string& gene : forward) {
            string currentGene = gene;
            
            for (int i = 0; i < currentGene.size(); ++i) {
                char original = currentGene[i];
                for (char c : choices) {
                    currentGene[i] = c;
                    if (backward.find(currentGene) != backward.end())
                        return steps + 1;

                    if (geneBank.find(currentGene) != geneBank.end()) {
                        nextLevel.insert(currentGene);
                        geneBank.erase(currentGene);
                    }
                }
                currentGene[i] = original;
            }
        }

        swap(forward, nextLevel);
        ++steps;
    }

    return -1;
}

int main() {
    vector<string> bank = {"AACCGGTA", "AACCGCTA", "AAACGGTA"};
    cout << minMutation("AACCGGTT", "AAACGGTA", bank) << endl;
    return 0;
}

The Python implementation of bidirectional BFS harnesses two sets to represent forward and backward search layers, refining the mutation search space substantially.

Complexity

Time Complexity: O(N * M * 4) with fewer checks due to expansion from both directions.

Space Complexity: O(N) for the forward and backward sets respective space.

Try this approach in the editor

Approach 3: BFS

We define a queue q to store the current gene sequence and the number of changes, and a set vis to store the visited gene sequences. Initially, we add the starting gene sequence start to the queue q and the set vis.

Then, we continuously take out a gene sequence from the queue q. If this gene sequence equals the target gene sequence, we return the current number of changes. Otherwise, we iterate through the gene bank bank, calculate the difference value between the current gene sequence and the gene sequence in the gene bank. If the difference value is 1 and the gene sequence in the gene bank has not been visited, we add it to the queue q and the set vis.

If the queue q is empty, it means that the gene change cannot be completed, so we return -1.

The time complexity is O(C times n times m), and the space complexity is O(n times m). Where n and m are the lengths of the gene sequence and the gene bank respectively, and C is the size of the character set of the gene sequence. In this problem, C = 4.

TypeScript

function minMutation(startGene: string, endGene: string, bank: string[]): number {
    const q: [string, number][] = [[startGene, 0]];
    const vis = new Set<string>([startGene]);
    for (const [gene, depth] of q) {
        if (gene === endGene) {
            return depth;
        }
        for (const next of bank) {
            let c = 2;
            for (let k = 0; k < 8 && c > 0; ++k) {
                if (gene[k] !== next[k]) {
                    --c;
                }
            }
            if (c && !vis.has(next)) {
                q.push([next, depth + 1]);
                vis.add(next);
            }
        }
    }
    return -1;
}

func minMutation(startGene string, endGene string, bank []string) int {
	type pair struct {
		s     string
		depth int
	}
	q := []pair{pair{startGene, 0}}
	vis := map[string]bool{startGene: true}
	for len(q) > 0 {
		p := q[0]
		q = q[1:]
		if p.s == endGene {
			return p.depth
		}
		for _, next := range bank {
			diff := 0
			for i := 0; i < len(startGene); i++ {
				if p.s[i] != next[i] {
					diff++
				}
			}
			if diff == 1 && !vis[next] {
				vis[next] = true
				q = append(q, pair{next, p.depth + 1})
			}
		}
	}
	return -1
}

Rust

use std::collections::{HashSet, VecDeque};

impl Solution {
    pub fn min_mutation(start_gene: String, end_gene: String, bank: Vec<String>) -> i32 {
        let mut q = VecDeque::new();
        q.push_back((start_gene.clone(), 0));
        let mut vis = HashSet::new();
        vis.insert(start_gene);

        while let Some((gene, depth)) = q.pop_front() {
            if gene == end_gene {
                return depth;
            }
            for next in &bank {
                let mut c = 2;
                for k in 0..8 {
                    if gene.as_bytes()[k] != next.as_bytes()[k] {
                        c -= 1;
                    }
                    if c == 0 {
                        break;
                    }
                }
                if c > 0 && !vis.contains(next) {
                    vis.insert(next.clone());
                    q.push_back((next.clone(), depth + 1));
                }
            }
        }
        -1
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Breadth-First Search (BFS) Approach	Time Complexity: O(N * M * 4) where N is number of genes and M is the gene length. Space Complexity: O(N) for storing genes in the queue and set.
Bidirectional BFS Approach	Time Complexity: O(N * M * 4) with fewer checks due to expansion from both directions. Space Complexity: O(N) for the forward and backward sets respective space.
BFS	–

Approach

Complexity

Breadth-First Search (BFS) Approach

Time Complexity: O(N * M * 4) where N is number of genes and M is the gene length.

Space Complexity: O(N) for storing genes in the queue and set.

Bidirectional BFS Approach

Time Complexity: O(N * M * 4) with fewer checks due to expansion from both directions.

Space Complexity: O(N) for the forward and backward sets respective space.

BFS

–

Complexity analysis

Approach	Time	Space	When to Use
Breadth-First Search (BFS)	O(N × L × 4)	O(N)	General solution. Best when modeling the problem as shortest path in an unweighted graph.
Bidirectional BFS	O(N × L × 4)	O(N)	Prefer when the gene bank is large and you want to reduce search depth by expanding from both start and end.

Frequently asked questions

Is Minimum Genetic Mutation easy or hard?

Minimum Genetic Mutation is rated Medium difficulty. The main challenge is recognizing that the problem forms an implicit graph where each valid mutation is an edge. Once modeled correctly, the BFS implementation is straightforward.

How to solve Minimum Genetic Mutation in O(N)?

An optimized BFS with a hash set for the gene bank effectively runs in near O(N × L) time since L is a small constant. Each valid gene is processed once, and mutation candidates are generated by changing one character at a time. Using a set allows O(1) lookup when verifying whether a mutation exists in the bank.

What is the best approach for Minimum Genetic Mutation?

Breadth-First Search (BFS) is the best approach because the problem asks for the minimum number of mutations, which maps directly to the shortest path in an unweighted graph. Each gene represents a node and each valid one-character mutation forms an edge. BFS guarantees the first time you reach the target gene is the minimum number of steps.

What data structure is used in Minimum Genetic Mutation?

The core data structures are a queue for BFS traversal and a hash set for storing the gene bank and visited genes. The queue processes genes level by level, while the hash set allows constant-time checks to validate mutations and prevent revisiting states.

What is the time complexity of Minimum Genetic Mutation?

The typical BFS solution runs in O(N × L × 4) time, where N is the number of genes in the bank and L is the gene length (usually 8). For every gene explored, you attempt L positions and 4 possible characters. Space complexity is O(N) for the queue and visited set.

Minimum Genetic Mutation Python or Java solution approach?

Both Python and Java implementations typically use BFS with a queue and a hash set. Generate mutations by iterating over each position in the gene string and replacing it with A, C, G, or T. If the mutated gene exists in the bank and hasn't been visited, add it to the queue for the next BFS level.

Is Minimum Genetic Mutation asked at Google, Amazon, or Meta?

Minimum Genetic Mutation is a common interview-style graph problem similar to Word Ladder. Variants that use BFS on strings or transformation graphs have appeared in interviews at companies like Amazon, Google, and Meta. Interviewers use it to test graph traversal and state-space search.

Minimum Genetic Mutation solution and explanation

The problem

Approach overview

Approach 1: Breadth-First Search (BFS) Approach

Approach 2: Bidirectional BFS Approach

Approach 3: BFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Genetic Mutation solution and explanation

The problem

Approach overview

Approach 1: Breadth-First Search (BFS) Approach

Approach 2: Bidirectional BFS Approach

Approach 3: BFS

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems