Scale Engineer

Minimum Genetic Mutation

Med
#0420Time: O(N^2 * L), where N is the number of genes in the `bank` and L is the length of a gene. In the worst case, for each of the N+1 genes we visit, we iterate through the entire `bank` of N genes to find neighbors, and each comparison takes O(L) time.Space: O(N * L), where N is the number of genes in the `bank` and L is the length of a gene string. This space is used for the queue and the `visited` set.1 company
Algorithms
Breadth-First Search
Data structures
Hash TableString
Companies
X

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach models the problem as finding the shortest path in a graph. The nodes of the graph are the valid gene strings (startGene and the genes in the bank), and an edge exists between two genes if they differ by a single character. Breadth-First Search (BFS) is the ideal algorithm for finding the shortest path in an unweighted graph like this.

We start a BFS from startGene. In each step, we explore all unvisited neighbors of the current gene. A neighbor is defined as a gene within the bank that is exactly one mutation away. We continue this search level by level. The level number corresponds to the number of mutations. The search terminates when we find the endGene, and we return the current level count.

Algorithm

  • Initialize a queue and add the startGene.
  • Use a Set called visited to keep track of genes from the bank that have been processed to avoid cycles.
  • Initialize a variable mutations to 0.
  • Start a Breadth-First Search. In each level of the search, process all genes currently in the queue.
  • For each currentGene dequeued:
    • If currentGene equals endGene, the shortest path is found. Return mutations.
    • Iterate through every gene in the bank.
    • For each bankGene, check if it's a valid one-step mutation from currentGene and if it has not been visited.
    • A valid mutation is a gene that differs by exactly one character.
    • If it's a valid and unvisited mutation, add it to the queue and the visited set.
  • After processing all genes at the current level, increment mutations.
  • If the queue becomes empty and endGene has not been reached, it means no such mutation path exists. Return -1.

Walkthrough

The algorithm works by performing a level-order traversal (BFS) starting from the startGene. We use a queue to manage the genes to visit and a set to keep track of visited genes to prevent redundant processing and infinite loops. At each level of the BFS, we represent one mutation step. We iterate through all genes in the bank to find valid next steps (neighbors) for the current gene. A gene from the bank is a valid neighbor if it's one character different from the current gene and hasn't been visited before. If we find such a neighbor, we add it to the queue for the next level. If we successfully reach the endGene, the current level count is the minimum number of mutations. If the queue becomes empty before we find the endGene, no path exists.

import java.util.*; class Solution {    public int minMutation(String startGene, String endGene, String[] bank) {        Queue<String> queue = new LinkedList<>();        Set<String> visited = new HashSet<>(Arrays.asList(bank));        // We can only mutate to genes in the bank, so if a gene is not in the bank, we can't visit it.        // We use the visited set to remove genes from consideration once they are added to the queue.         queue.add(startGene);        // Note: startGene might not be in the bank, but it's our starting point.        // We don't need to add it to visited because we won't encounter it again in the bank.         int mutations = 0;         while (!queue.isEmpty()) {            int levelSize = queue.size();            for (int i = 0; i < levelSize; i++) {                String currentGene = queue.poll();                if (currentGene.equals(endGene)) {                    return mutations;                }                 // Find neighbors by iterating through the bank                // This is inefficient but a valid approach.                // We need a way to iterate over the remaining valid genes.                // A copy of the bank or iterating and checking against a visited set works.                for (String bankGene : bank) {                    if (visited.contains(bankGene) && isMutation(currentGene, bankGene)) {                        // Add to queue and mark as visited (by removing from the set of available genes)                        queue.add(bankGene);                        visited.remove(bankGene);                    }                }            }            mutations++;        }         return -1;    }     private boolean isMutation(String gene1, String gene2) {        int diff = 0;        for (int i = 0; i < gene1.length(); i++) {            if (gene1.charAt(i) != gene2.charAt(i)) {                diff++;            }        }        return diff == 1;    }}

Complexity

Time

O(N^2 * L), where N is the number of genes in the `bank` and L is the length of a gene. In the worst case, for each of the N+1 genes we visit, we iterate through the entire `bank` of N genes to find neighbors, and each comparison takes O(L) time.

Space

O(N * L), where N is the number of genes in the `bank` and L is the length of a gene string. This space is used for the queue and the `visited` set.

Trade-offs

Pros

  • The logic is straightforward and directly translates the problem into a graph traversal.

  • It's guaranteed to find the shortest path if one exists.

Cons

  • This approach is inefficient because for every gene we process, we scan the entire bank to find its neighbors. This results in a quadratic time complexity relative to the size of the bank, which is slow for larger banks.

Solutions

class Solution {public  int minMutation(String start, String end, String[] bank) {    Set<String> s = new HashSet<>();    for (String b : bank) {      s.add(b);    }    Map<Character, String> mp = new HashMap<>(4);    mp.put('A', "TCG");    mp.put('T', "ACG");    mp.put('C', "ATG");    mp.put('G', "ATC");    Deque<Pair<String, Integer>> q = new LinkedList<>();    q.offer(new Pair<>(start, 0));    while (!q.isEmpty()) {      Pair<String, Integer> p = q.poll();      String t = p.getKey();      int step = p.getValue();      if (end.equals(t)) {        return step;      }      for (int i = 0; i < t.length(); ++i) {        for (char c : mp.get(t.charAt(i)).toCharArray()) {          String next = t.substring(0, i) + c + t.substring(i + 1);          if (s.contains(next)) {            q.offer(new Pair<>(next, step + 1));            s.remove(next);          }        }      }    }    return -1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem