Category: LeetCode Solutions

Solve LeetCode 909: Snakes and Ladders in Python with a board-index BFS approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move.

Algorithm

1. Map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move.
2. Maintain this invariant: The first time BFS reaches a square uses the minimum number of dice throws.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def snakesAndLadders(self, board):
        n = len(board)
        def coordinates(square):
            row_from_bottom, offset = divmod(square - 1, n)
            row = n - 1 - row_from_bottom
            col = offset if row_from_bottom % 2 == 0 else n - 1 - offset
            return row, col
        queue, seen = deque([(1, 0)]), {1}
        while queue:
            square, moves = queue.popleft()
            if square == n * n: return moves
            for rolled in range(square + 1, min(square + 6, n * n) + 1):
                r, c = coordinates(rolled)
                destination = board[r][c] if board[r][c] != -1 else rolled
                if destination not in seen:
                    seen.add(destination); queue.append((destination, moves + 1))
        return -1

Why this is correct

The proof follows the maintained state: The first time BFS reaches a square uses the minimum number of dice throws. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(n^2) time and O(n^2) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

Do not chain a second jump in the same move; row direction alternates from the bottom.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 210. Course Schedule II · Next: 433. Minimum Genetic Mutation

Solve LeetCode 433: Minimum Genetic Mutation in Python with a single-character BFS approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

BFS through valid bank strings formed by replacing one position with A, C, G, or T.

Algorithm

1. BFS through valid bank strings formed by replacing one position with A, C, G, or T.
2. Maintain this invariant: Every queued gene is valid and reached in the minimum number of mutations.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

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

Why this is correct

The proof follows the maintained state: Every queued gene is valid and reached in the minimum number of mutations. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

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

Edge cases

If the end gene is absent from the bank it is unreachable unless it already equals the start.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

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

Solve LeetCode 127: Word Ladder in Python with a wildcard-neighbor BFS approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern.

Algorithm

1. Index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern.
2. Maintain this invariant: The first BFS layer reaching a word uses the shortest transformation sequence.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        if endWord not in wordList: return 0
        patterns = defaultdict(list)
        width = len(beginWord)
        for word in wordList:
            for i in range(width): patterns[word[:i] + "*" + word[i + 1:]].append(word)
        queue, seen = deque([(beginWord, 1)]), {beginWord}
        while queue:
            word, distance = queue.popleft()
            for i in range(width):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbor in patterns[pattern]:
                    if neighbor == endWord: return distance + 1
                    if neighbor not in seen:
                        seen.add(neighbor); queue.append((neighbor, distance + 1))
                patterns[pattern] = []
        return 0

Why this is correct

The proof follows the maintained state: The first BFS layer reaching a word uses the shortest transformation sequence. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(NL^2) preprocessing and traversal time and O(NL) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

The end word must be in the dictionary; each transformation changes exactly one character.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 433. Minimum Genetic Mutation · Next: 208. Implement Trie (Prefix Tree)

Solve LeetCode 208: Implement Trie (Prefix Tree) in Python with a nested child maps approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes.

Algorithm

1. Each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes.
2. Maintain this invariant: The node reached after a prefix represents exactly that character sequence.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for char in word: node = node.setdefault(char, {})
        node["$"] = True

    def search(self, word):
        node = self._find(word)
        return node is not None and "$" in node

    def startsWith(self, prefix):
        return self._find(prefix) is not None

    def _find(self, text):
        node = self.root
        for char in text:
            if char not in node: return None
            node = node[char]
        return node

Why this is correct

The proof follows the maintained state: The node reached after a prefix represents exactly that character sequence. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(L) time per operation and O(total inserted characters) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

An inserted word can also be a prefix of a longer word.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 127. Word Ladder · Next: 211. Design Add and Search Words Data Structure

Solve LeetCode 211: Design Add and Search Words Data Structure in Python with a trie plus wildcard DFS approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Insert normally. During search, a dot branches to every child while a letter follows one matching edge.

Algorithm

1. Insert normally. During search, a dot branches to every child while a letter follows one matching edge.
2. Maintain this invariant: The DFS states represent all trie nodes consistent with the processed pattern prefix.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class WordDictionary:
    def __init__(self):
        self.root = {}

    def addWord(self, word):
        node = self.root
        for char in word: node = node.setdefault(char, {})
        node["$"] = True

    def search(self, word):
        def match(index, node):
            if index == len(word): return "$" in node
            char = word[index]
            if char == ".":
                return any(key != "$" and match(index + 1, child) for key, child in node.items())
            return char in node and match(index + 1, node[char])
        return match(0, self.root)

Why this is correct

The proof follows the maintained state: The DFS states represent all trie nodes consistent with the processed pattern prefix. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(L) insert and O(branching^wildcards) worst-case search time. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

A wildcard matches exactly one character, and a match must end at a terminal node.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 208. Implement Trie (Prefix Tree) · Next: 212. Word Search II

Solve LeetCode 212: Word Search II in Python with a trie-guided board DFS approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Build a trie of target words and DFS from each board cell, pruning paths absent from the trie and removing words after discovery to avoid duplicates.

Algorithm

1. Build a trie of target words and DFS from each board cell, pruning paths absent from the trie and removing words after discovery to avoid duplicates.
2. Maintain this invariant: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def findWords(self, board, words):
        root = {}
        for word in words:
            node = root
            for char in word: node = node.setdefault(char, {})
            node["$"] = word
        rows, cols, answer = len(board), len(board[0]), []
        def search(r, c, parent):
            char = board[r][c]
            if char not in parent: return
            node = parent[char]
            word = node.pop("$", None)
            if word: answer.append(word)
            board[r][c] = "#"
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] != "#": search(nr, nc, node)
            board[r][c] = char
            if not node: parent.pop(char)
        for r in range(rows):
            for c in range(cols): search(r, c, root)
        return answer

Why this is correct

The proof follows the maintained state: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(mn·4^L) worst-case time with strong trie pruning and O(total word characters) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

The same word should be emitted once; restore board cells after backtracking.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 211. Design Add and Search Words Data Structure

Solve LeetCode 130: Surrounded Regions in Python with a boundary flood fill approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Mark all O cells reachable from the boundary as safe, flip every remaining O to X, then restore the safe marks.

Algorithm

1. Mark all O cells reachable from the boundary as safe, flip every remaining O to X, then restore the safe marks.
2. Maintain this invariant: Marked cells are exactly the open cells connected to some boundary open cell.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def solve(self, board):
        if not board: return
        rows, cols = len(board), len(board[0])
        def mark(r, c):
            if r < 0 or c < 0 or r == rows or c == cols or board[r][c] != "O": return
            board[r][c] = "S"
            mark(r + 1, c); mark(r - 1, c); mark(r, c + 1); mark(r, c - 1)
        for r in range(rows): mark(r, 0); mark(r, cols - 1)
        for c in range(cols): mark(0, c); mark(rows - 1, c)
        for r in range(rows):
            for c in range(cols):
                board[r][c] = "O" if board[r][c] == "S" else "X"

Why this is correct

The proof follows the maintained state: Marked cells are exactly the open cells connected to some boundary open cell. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(mn) time and O(mn) worst-case space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

Boundary cells can never be captured; thin boards are handled naturally.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 200. Number of Islands · Next: 133. Clone Graph

Solve LeetCode 133: Clone Graph in Python with a DFS memoized cloning approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Create and memoize a clone before recursively cloning neighbors, then attach cloned neighbor references.

Algorithm

1. Create and memoize a clone before recursively cloning neighbors, then attach cloned neighbor references.
2. Maintain this invariant: The map contains the unique clone for every discovered original node, preventing infinite recursion and duplicate clones.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

LeetCode provides the list, tree, or graph node definition used by the method.

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def cloneGraph(self, node):
        copies = {}
        def clone(original):
            if not original: return None
            if original in copies: return copies[original]
            copy = Node(original.val)
            copies[original] = copy
            copy.neighbors = [clone(neighbor) for neighbor in original.neighbors]
            return copy
        return clone(node)

Why this is correct

The proof follows the maintained state: The map contains the unique clone for every discovered original node, preventing infinite recursion and duplicate clones. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(V+E) time and O(V) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

The graph may contain cycles, self-loops, or a single node.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 130. Surrounded Regions · Next: 399. Evaluate Division

Solve LeetCode 399: Evaluate Division in Python with a weighted graph search approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Represent each equation as two reciprocal weighted edges. For a query, search for a path and multiply weights along it.

Algorithm

1. Represent each equation as two reciprocal weighted edges. For a query, search for a path and multiply weights along it.
2. Maintain this invariant: The accumulated product equals the ratio from the query source to the current graph node.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def calcEquation(self, equations, values, queries):
        graph = defaultdict(list)
        for (a, b), value in zip(equations, values):
            graph[a].append((b, value)); graph[b].append((a, 1.0 / value))
        def search(start, end):
            if start not in graph or end not in graph: return -1.0
            stack, seen = [(start, 1.0)], {start}
            while stack:
                node, product = stack.pop()
                if node == end: return product
                for neighbor, weight in graph[node]:
                    if neighbor not in seen:
                        seen.add(neighbor); stack.append((neighbor, product * weight))
            return -1.0
        return [search(a, b) for a, b in queries]

Why this is correct

The proof follows the maintained state: The accumulated product equals the ratio from the query source to the current graph node. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O((V+E) per query) time and O(V+E) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

Unknown variables and disconnected pairs return -1; a known variable divided by itself is one.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 133. Clone Graph · Next: 207. Course Schedule

Solve LeetCode 207: Course Schedule in Python with a Kahn topological sort approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

This guide paraphrases the task and does not reproduce LeetCode’s prompt. Use the official page for the complete statement, examples, constraints, and submission runner.

What the problem is testing

Count prerequisites as indegrees, repeatedly remove zero-indegree courses, and reduce the indegrees of dependent courses.

Algorithm

1. Count prerequisites as indegrees, repeatedly remove zero-indegree courses, and reduce the indegrees of dependent courses.
2. Maintain this invariant: The queue contains exactly the currently schedulable courses with no remaining prerequisites.
3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

Python solution

from collections import Counter, defaultdict, deque, OrderedDict
import random

class Solution:
    def canFinish(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]; indegree = [0] * numCourses
        for course, prerequisite in prerequisites:
            graph[prerequisite].append(course); indegree[course] += 1
        queue = deque(i for i, degree in enumerate(indegree) if degree == 0)
        completed = 0
        while queue:
            course = queue.popleft(); completed += 1
            for following in graph[course]:
                indegree[following] -= 1
                if indegree[following] == 0: queue.append(following)
        return completed == numCourses

Why this is correct

The proof follows the maintained state: The queue contains exactly the currently schedulable courses with no remaining prerequisites. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

Complexity

O(V+E) time and O(V+E) space. The stated auxiliary space excludes the returned output unless the output is the data structure being built.

Edge cases

Processing fewer than all courses proves a directed cycle.

Tested reference code

This implementation is included in the site’s downloadable 100-solution Python library. The complete suite compiles every solution and runs a behavioral assertion for every problem before publication.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 399. Evaluate Division · Next: 210. Course Schedule II