LeetCode 433: Minimum Genetic Mutation — Python Solution

LeetCode 433: Minimum Genetic Mutation is a Medium graph bfs problem. This Python walkthrough develops a single-character BFS solution, ties every code decision to a concrete invariant, and includes the regression check used before publication.

This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.

Recognizing the pattern

BFS explores an unweighted state graph in increasing move count, so the first arrival gives a shortest transformation.

For this problem specifically, bFS through valid bank strings formed by replacing one position with A, C, G, or T. The invariant worth writing beside the code is: Every queued gene is valid and reached in the minimum number of mutations.

Step-by-step algorithm

1. Identify the input state consumed by minMutation(startGene, endGene, bank) and initialize the data required by the single-character BFS pattern.
2. BFS through valid bank strings formed by replacing one position with A, C, G, or T.
3. After each update, verify the page’s central invariant: Every queued gene is valid and reached in the minimum number of mutations.
4. Finish only after the boundary behavior is covered: If the end gene is absent from the bank it is unreachable unless it already equals the start.

Python solution

from collections import deque

class Solution:
    def minMutation(self, startGene, endGene, bank):
        if startGene == endGene: return 0
        allowed = set(bank)
        if endGene not in allowed: return -1
        queue = deque([(startGene, 0)]); seen = {startGene}
        for_queue = "ACGT"
        while queue:
            gene, steps = queue.popleft()
            for i in range(len(gene)):
                for base in for_queue:
                    candidate = gene[:i] + base + gene[i + 1:]
                    if candidate == endGene: return steps + 1
                    if candidate in allowed and candidate not in seen:
                        seen.add(candidate); queue.append((candidate, steps + 1))
        return -1

Reading the implementation

The main entry point is minMutation(startGene, endGene, bank). The named working state includes allowed, queue, for_queue, gene, candidate; those variables make the single-character BFS state visible instead of hiding it in incidental control flow.

The implementation uses 3 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. In concrete terms, bFS through valid bank strings formed by replacing one position with A, C, G, or T.

Correctness argument

Initialization. The starting state is the only item in the first frontier, so its distance or level is exact.

Preservation. BFS through valid bank strings formed by replacing one position with A, C, G, or T. Because the queue processes earlier layers first, every queued gene is valid and reached in the minimum number of mutations.

Termination. Each state is accepted at most once. The first accepted goal therefore has the minimum possible layer, or exhausting the queue proves no valid path exists.

Complexity and trade-offs

O(BL) practical time and O(B) space. The auxiliary-space figure excludes the returned output unless the output itself is the structure being built.

DFS can determine reachability but cannot stop at the first found path when a minimum number of moves is required. That comparison is useful in an interview because it explains why the final implementation is preferable, not merely that it passes.

Regression check

The published implementation belongs to a 100-problem suite that is compiled and exercised behaviorally before deployment.

One reference assertion from that suite is shown below. It targets the normal path while the edge conditions in the next section cover the failure-prone boundaries.

assert Solution().minMutation("AACCGGTT","AACCGGTA",["AACCGGTA"])==1

Common mistakes and edge cases

• Problem-specific boundary: If the end gene is absent from the bank it is unreachable unless it already equals the start.
• Pattern-level pitfall: Generate only legal neighbors, mark them before enqueueing, and count layers consistently with the problem’s definition of a move.
• Invariant check: after every update, confirm that every queued gene is valid and reached in the minimum number of mutations.

Interview review checklist

• Explain why single-character BFS matches the structure of this input.
• State the invariant in one sentence before tracing code: Every queued gene is valid and reached in the minimum number of mutations.
• Derive O(BL) practical time and O(B) space from how many times each element or state is visited.
• Test the boundary explicitly: If the end gene is absent from the bank it is unreachable unless it already equals the start.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 909. Snakes and Ladders · Next: 127. Word Ladder