Blog

  • Test a HUB75 FPGA Row Scanner in VHDL | Self-Checking Testbench

    A HUB75 controller can look correct in a screenshot and still be wrong at the panel connector. A missing blanking cycle, an off-by-one column counter, or a latch pulse one clock too early produces flicker and ghosting that may disappear when you slow the design down. A small self-checking VHDL testbench catches those ordering errors before hardware bring-up. This tutorial builds one with GHDL and the row scanner from the preceding timing tutorial.

    The goal is not to model a particular panel’s internal driver IC. The goal is to assert the contract owned by the FPGA: all shifting and latching happen while the output is blank, one latch follows exactly one row’s worth of columns, the address settles before display enable, and the row counter wraps cleanly.

    The four invariants worth testing first

    InvariantFailure symptomTestbench observation
    LAT is never high while OE is enabled.Old and new row data bleed together; visible ghosting.Assert not (lat = '1' and oe_n = '0') every clock.
    CLK is never high while OE is enabled.Shift-register activity appears on the display.Assert not (hub_clk = '1' and oe_n = '0').
    One transaction shifts exactly COLUMNS clock phases.Columns wrap early, shift off the end, or latch stale data.Count the clock-high states before LAT.
    Row address changes only while blank and wraps.Wrong row lights or the panel stops after the last row.Sample row_addr at display enable and after dwell_done.

    Use a tiny panel in simulation

    The testbench overrides the scanner generics to COLUMNS = 4 and ROW_GROUPS = 2. That makes a complete transaction easy to read in a waveform while preserving the same state transitions as a 64-column, 16-row panel. A smaller simulation is not a different design; it is the same parameterized design with fewer repetitions.

    The stimulus drives a known six-bit RGB word, releases reset, counts the four high clock phases, waits for LAT, and then checks that the panel remains blank for the latch and address-settling cycles. It enables row zero, pulses dwell_done, and checks that the scanner blanks and advances to row one.

    A self-checking VHDL-2008 testbench

    library ieee;
    use ieee.std_logic_1164.all;
    use ieee.numeric_std.all;
    use std.env.all;
    
    entity tb_hub75_row_scanner is
    end entity;
    
    architecture sim of tb_hub75_row_scanner is
      constant COLUMNS    : positive := 4;
      constant ROW_GROUPS : positive := 2;
      signal clk        : std_logic := '0';
      signal rst        : std_logic := '1';
      signal dwell_done : std_logic := '0';
      signal pixel_bits : std_logic_vector(5 downto 0) := "101011";
      signal hub_clk    : std_logic;
      signal lat        : std_logic;
      signal oe_n       : std_logic;
      signal row_addr   : natural range 0 to ROW_GROUPS - 1;
      signal rgb        : std_logic_vector(5 downto 0);
    begin
      clk <= not clk after 5 ns;
    
      dut: entity work.hub75_row_scanner
        generic map (COLUMNS => COLUMNS, ROW_GROUPS => ROW_GROUPS)
        port map (
          clk => clk, rst => rst, dwell_done => dwell_done,
          pixel_bits => pixel_bits, hub_clk => hub_clk, lat => lat,
          oe_n => oe_n, row_addr => row_addr, rgb => rgb
        );
    
      stimulus: process
        variable shift_cycles : natural := 0;
      begin
        wait for 25 ns;
        rst <= '0';
    
        while true loop
          wait until rising_edge(clk);
          wait for 1 ns;
    
          assert not (oe_n = '0' and lat = '1')
            report "LAT asserted while the panel output was enabled"
            severity failure;
          assert not (oe_n = '0' and hub_clk = '1')
            report "HUB75 clock toggled while the panel output was enabled"
            severity failure;
    
          if hub_clk = '1' then
            shift_cycles := shift_cycles + 1;
            assert rgb = "000000"
              report "RGB data was not blanked during the high clock phase"
              severity failure;
          end if;
    
          exit when lat = '1';
        end loop;
    
        assert shift_cycles = COLUMNS
          report "The scanner latched after the wrong number of column clocks"
          severity failure;
        assert oe_n = '1'
          report "OE was enabled during the latch phase"
          severity failure;
    
        wait until rising_edge(clk);
        wait for 1 ns;
        assert lat = '0' and oe_n = '1'
          report "The scanner did not keep the panel blank after LAT"
          severity failure;
    
        wait until rising_edge(clk);
        wait for 1 ns;
        assert oe_n = '0' and row_addr = 0
          report "The scanner did not enable row zero after address settling"
          severity failure;
    
        dwell_done <= '1';
        wait until rising_edge(clk);
        wait for 1 ns;
        dwell_done <= '0';
        assert oe_n = '1' and row_addr = 1
          report "The scanner did not blank and advance to the next row"
          severity failure;
    
        report "HUB75 row scanner timing checks passed" severity note;
        finish;
      end process;
    end architecture;

    Run it with GHDL

    Run from the example directory. The --std=08 flag matters because the testbench uses VHDL-2008’s std.env.finish to end a successful simulation without an artificial stop time.

    ghdl -a --std=08 rtl/hub75_row_scanner.vhd tb/tb_hub75_row_scanner.vhd
    ghdl -e --std=08 tb_hub75_row_scanner
    ghdl -r --std=08 tb_hub75_row_scanner

    A passing run ends with HUB75 row scanner timing checks passed. To prove that the assertions are doing useful work, temporarily change oe_n to enable during the latch state or change the column terminal condition from COLUMNS - 1 to COLUMNS - 2. GHDL should stop at the corresponding failure rather than returning a misleading green result.

    Turn the smoke test into a real verification layer

    This first test checks control ordering, not image correctness. The next useful extensions are:

    • Drive changing pixels. Replace the constant pixel_bits with a column counter and assert that the expected value is present during every shift_low state.
    • Check every row. Hold dwell_done high for one display interval repeatedly and assert the sequence 0, 1, ..., ROW_GROUPS - 1, 0.
    • Add a bitplane scheduler. Give each plane a different dwell length and assert that the total visible slots match the numeric brightness code.
    • Test reset at awkward times. Assert reset during shifting, latching, and display. The safe result is always blank output and a known row/column restart.
    • Test the frame boundary. Connect a double-buffered framebuffer and assert that a bank swap is accepted only while the scan engine is at its defined frame boundary.

    For larger designs, move the same ideas into reusable assertions around the DUT. The companion FPGA LED controller verification guide covers the invariant style for PWM, BCM, and HUB75 controllers; this VHDL testbench is the smallest place to start because every failure maps to one visible control signal.

    A waveform-reading shortcut

    When the test fails, inspect the signals in this order: OE first, then LAT, then row address, then CLK/RGB. If OE is low during a control transition, the panel can visibly show it even if the pixel data is perfect. If OE stays high but the latch count is wrong, the problem is in the column counter or state transition. If the latch count passes but the row is wrong, inspect the address update and wrap condition. Only after those boundaries are correct should you debug bit packing, channel order, gamma, or framebuffer reads.

    That order keeps the test useful as the design grows. A testbench that only compares a final RGB value can miss the exact timing error that makes a physical panel flicker. A few cycle-level assertions give the simulator a definition of “ghost-free” that does not depend on a camera, a particular panel, or a lucky clock rate.


    Continue the FPGA LED controller path

    Read the HUB75 row-scanner timing tutorial, then use the FPGA LED controller hub to connect the verified scan transaction to PWM/BCM brightness, a frame buffer, and a tear-free clock-domain crossing.

  • VHDL HUB75 Row Scanner: Blanking, Latch & Address Timing

    A HUB75 panel is forgiving about the shape of your pixel data and unforgiving about the order of its control signals. The safe transaction is simple: blank the outputs, shift one row’s pixels, pulse the latch, change the row address while the panel is still blank, then enable the new row for its dwell time. This tutorial turns that sequence into a small VHDL-2008 state machine and explains the timing decisions that prevent ghosting and wrong-row flashes.

    This is the implementation layer of the FPGA LED controller tutorial series. The examples below are deliberately small enough to simulate first. They do not pretend to know your panel’s scan ratio, logic thresholds, or maximum ribbon-cable clock; those are board and panel constraints you still need to verify.

    The transaction a HUB75 panel expects

    For a typical 1/16-scan RGB panel, the controller drives two physical rows at once. The six data inputs are usually named R1/G1/B1 and R2/G2/B2, while CLK shifts one column’s worth of those six bits into the panel’s internal registers. LAT transfers the shifted register into the display register. OE is active low on many panels, so oe_n = '1' means blank and oe_n = '0' means display. The exact connector labels vary; the electrical sequence is the important part.

    SignalSafe controller ruleWhy it matters
    RGB dataPresent the next six bits before the rising shift clock.The panel samples data on its clock edge.
    CLKToggle only while OE is blanked.Some panels show shifted data immediately if OE is left enabled.
    LATPulse after the final column, with OE still blank.The pulse copies the shift register into the active display register.
    Row addressChange it after LAT and before OE is enabled.Address settling while blank prevents the old row from lighting with new data.
    OEEnable only during the controlled dwell interval.It defines the visible brightness time for the selected row.

    A six-state VHDL sequence

    The reference module in the example bundle uses six states. There are two states per shifted column so the RGB bus is stable for one FPGA clock before the clock-high phase; the remaining states make the blank, latch, address, and display boundaries visible in a waveform.

    StateOutputsTransition
    blankOE high; column counter reset.Move to shift_low.
    shift_lowOE high; drive the next RGB bits; CLK low.Move to shift_high.
    shift_highOE high; CLK high; RGB cleared.Advance the column or move to latch.
    latchOE high; LAT high for one FPGA clock.Move to set_row.
    set_rowOE high; row address is now stable.Move to display.
    displayOE low for the current dwell.On dwell_done, advance the row and blank again.

    That extra set_row cycle is not decorative. It gives the row-address outputs a complete clock period to settle before OE falls. A fast design can combine operations if its timing constraints and panel data sheet justify doing so; starting with explicit states makes the first waveform understandable and gives you a clean place to add a calibrated blanking interval later.

    Reference implementation

    This compact scanner shifts a six-bit RGB word for each column, then waits for a caller-provided dwell_done pulse. A real BCM controller would supply a different pixel_bits value for each bitplane and calculate the dwell from that plane’s weight; the scan transaction stays the same.

    library ieee;
    use ieee.std_logic_1164.all;
    use ieee.numeric_std.all;
    
    entity hub75_row_scanner is
      generic (COLUMNS : positive := 64; ROW_GROUPS : positive := 16);
      port (
        clk        : in  std_logic;
        rst        : in  std_logic;
        dwell_done : in  std_logic;
        pixel_bits : in  std_logic_vector(5 downto 0);
        hub_clk    : out std_logic;
        lat        : out std_logic;
        oe_n       : out std_logic;
        row_addr   : out natural range 0 to ROW_GROUPS - 1;
        rgb        : out std_logic_vector(5 downto 0)
      );
    end entity;
    
    architecture rtl of hub75_row_scanner is
      type state_t is (blank, shift_low, shift_high, latch, set_row, display);
      signal state : state_t := blank;
      signal col   : natural range 0 to COLUMNS - 1 := 0;
      signal row   : natural range 0 to ROW_GROUPS - 1 := 0;
    begin
      process (clk)
      begin
        if rising_edge(clk) then
          if rst = '1' then
            state <= blank;
            col   <= 0;
            row   <= 0;
          else
            case state is
              when blank =>
                col <= 0;
                state <= shift_low;
              when shift_low =>
                state <= shift_high;
              when shift_high =>
                if col = COLUMNS - 1 then
                  state <= latch;
                else
                  col <= col + 1;
                  state <= shift_low;
                end if;
              when latch =>
                state <= set_row;
              when set_row =>
                state <= display;
              when display =>
                if dwell_done = '1' then
                  if row = ROW_GROUPS - 1 then
                    row <= 0;
                  else
                    row <= row + 1;
                  end if;
                  state <= blank;
                end if;
            end case;
          end if;
        end if;
      end process;
    
      hub_clk  <= '1' when state = shift_high else '0';
      lat      <= '1' when state = latch else '0';
      oe_n     <= '0' when state = display else '1';
      row_addr <= row;
      rgb      <= pixel_bits when state = shift_low else (others => '0');
    end architecture;

    What this module intentionally does not solve

    • Pixel memory. pixel_bits is a single input. Add a framebuffer read port or a bitplane scheduler when the transaction itself is proven.
    • Panel geometry. Some panels reverse columns, swap RGB channels, or require an address mapping different from a simple binary row number.
    • Clock constraints. Set the I/O standard, output drive, slew, and maximum clock from the FPGA board and panel combination, not from this generic module.
    • Brightness timing. dwell_done belongs to the PWM or BCM layer. The scanner should only consume a clean boundary pulse.

    Timing budget: where the refresh rate comes from

    For one row group and one bitplane, the scanner spends two controller clocks per column plus the latch and address-settling cycles. If the FPGA clock is Fclk, the approximate shift transaction time is:

    Tshift ≈ (2 × COLUMNS + Tblank + Tlat + Trow) ÷ Fclk

    That is only the row transaction. A complete BCM cycle repeats it once per bitplane and once per row address, with each plane’s visible dwell weighted by its bit significance. The HUB75 timing calculator is useful for the system-level ceiling; measure the actual state-machine overhead here before promising a refresh rate.

    A concrete 64-column example

    With COLUMNS = 64, two clocks per column consume 128 FPGA clocks. Add one blank entry, one latch cycle, and one row-address cycle and the transaction is roughly 131 clocks before the visible dwell. At 20 MHz that is 6.55 microseconds of shift/control time. A 16-row group therefore needs about 104.8 microseconds before any BCM dwell is included. That estimate is intentionally approximate: a production controller may pipeline the fetch, add a multi-cycle blanking window, or use a different panel scan ratio.

    Bring-up checklist: prove the waveform before the panel

    1. Simulate reset. Confirm the scanner starts blank, at column zero, row zero, and with LAT low.
    2. Count columns. For a four-column simulation, see exactly four clock-high phases before LAT. For a 64-column panel, do not rely on visual inspection.
    3. Check the dangerous overlap. Assert that LAT and CLK never occur with OE enabled. This catches the most common ghosting bug directly.
    4. Check address settling. Change the row only while blank and give it a full controller cycle before enabling OE.
    5. Probe the connector. Start with a low clock, a single lit pixel, and a short cable. Increase speed only after the signals have clean edges at the panel.
    6. Add the brightness layer last. Feed a fixed dwell first, then one BCM plane, then a complete bitplane schedule. This separates a scan-order fault from a brightness-budget fault.

    The companion article, How to test a HUB75 row scanner in VHDL, turns the three most important waveform checks into a self-checking GHDL testbench. Once that passes, continue to FPGA LED controller verification for reusable invariants around PWM, BCM, and frame-boundary updates.


    Continue the FPGA LED controller path

    Start at the FPGA LED controller tutorial hub, test this scanner with the self-checking VHDL testbench, then connect it to the double-buffered framebuffer and the CDC frame-swap handshake.

  • LeetCode 212: Word Search II — Python Solution

    LeetCode 212: Word Search II is a Hard trie problem. This Python walkthrough develops a trie-guided board DFS 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.

    DifficultyHard
    TopicTrie
    Reusable patterntrie-guided board DFS
    ComplexityO(mn·4^L) worst-case time with strong trie pruning and O(total word characters) space

    Recognizing the pattern

    A trie shares storage and work across common prefixes, allowing a search to abandon an entire family of words after one failed edge.

    For this problem specifically, 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. The invariant worth writing beside the code is: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.

    Step-by-step algorithm

    1. Identify the input state consumed by findWords(board, words) and initialize the data required by the trie-guided board DFS pattern.
    2. 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.
    3. After each update, verify the page’s central invariant: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
    4. Finish only after the boundary behavior is covered: The same word should be emitted once; restore board cells after backtracking.

    Python solution

    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

    Reading the implementation

    The main entry point is findWords(board, words). The named working state includes root, node, rows, char, word; those variables make the trie-guided board DFS state visible instead of hiding it in incidental control flow.

    The implementation uses 5 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. In concrete terms, 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.

    Correctness argument

    Initialization. The data structure starts with exactly the information known before any input element is processed.

    Preservation. 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. Each update records the current item without invalidating earlier decisions; consequently, every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.

    Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

    Complexity and trade-offs

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

    A hash set is simpler for exact words, but it cannot answer prefix or wildcard traversal without examining many candidates. 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.

    words=Solution().findWords([["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],["oath","pea","eat","rain"]); assert sorted(words)==["eat","oath"]

    Common mistakes and edge cases

    • Problem-specific boundary: The same word should be emitted once; restore board cells after backtracking.
    • Pattern-level pitfall: A prefix node is not necessarily a complete word; terminal markers and wildcard branching need separate handling.
    • Invariant check: after every update, confirm that every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.

    Interview review checklist

    • Explain why trie-guided board DFS matches the structure of this input.
    • State the invariant in one sentence before tracing code: Every DFS path matches the trie prefix represented by its current node and uses each board cell at most once.
    • Derive O(mn·4^L) worst-case time with strong trie pruning and O(total word characters) space from how many times each element or state is visited.
    • Test the boundary explicitly: The same word should be emitted once; restore board cells after backtracking.

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

  • LeetCode 211: Design Add and Search Words Data Structure — Python Solution

    LeetCode 211: Design Add and Search Words Data Structure is a Medium trie problem. This Python walkthrough develops a trie plus wildcard DFS 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.

    DifficultyMedium
    TopicTrie
    Reusable patterntrie plus wildcard DFS
    ComplexityO(L) insert and O(branching^wildcards) worst-case search time

    Recognizing the pattern

    A trie shares storage and work across common prefixes, allowing a search to abandon an entire family of words after one failed edge.

    For this problem specifically, insert normally. During search, a dot branches to every child while a letter follows one matching edge. The invariant worth writing beside the code is: The DFS states represent all trie nodes consistent with the processed pattern prefix.

    Step-by-step algorithm

    1. Identify the input state consumed by addWord(word) and initialize the data required by the trie plus wildcard DFS pattern.
    2. Insert normally. During search, a dot branches to every child while a letter follows one matching edge.
    3. After each update, verify the page’s central invariant: The DFS states represent all trie nodes consistent with the processed pattern prefix.
    4. Finish only after the boundary behavior is covered: A wildcard matches exactly one character, and a match must end at a terminal node.

    Python solution

    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)

    Reading the implementation

    The main entry point is addWord(word). The named working state includes node, char; those variables make the trie plus wildcard DFS state visible instead of hiding it in incidental control flow.

    A single main loop advances the algorithm, which is the key reason the traversal does not revisit already resolved input unnecessarily. Early returns stop as soon as the answer is forced, avoiding work that cannot change the result. In concrete terms, insert normally. During search, a dot branches to every child while a letter follows one matching edge.

    Correctness argument

    Initialization. The data structure starts with exactly the information known before any input element is processed.

    Preservation. Insert normally. During search, a dot branches to every child while a letter follows one matching edge. Each update records the current item without invalidating earlier decisions; consequently, the DFS states represent all trie nodes consistent with the processed pattern prefix.

    Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

    Complexity and trade-offs

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

    A hash set is simpler for exact words, but it cannot answer prefix or wildcard traversal without examining many candidates. 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.

    wd=WordDictionary(); [wd.addWord(word) for word in ["bad","dad","mad"]]; assert wd.search(".ad") and not wd.search("pad")

    Common mistakes and edge cases

    • Problem-specific boundary: A wildcard matches exactly one character, and a match must end at a terminal node.
    • Pattern-level pitfall: A prefix node is not necessarily a complete word; terminal markers and wildcard branching need separate handling.
    • Invariant check: after every update, confirm that the DFS states represent all trie nodes consistent with the processed pattern prefix.

    Interview review checklist

    • Explain why trie plus wildcard DFS matches the structure of this input.
    • State the invariant in one sentence before tracing code: The DFS states represent all trie nodes consistent with the processed pattern prefix.
    • Derive O(L) insert and O(branching^wildcards) worst-case search time from how many times each element or state is visited.
    • Test the boundary explicitly: A wildcard matches exactly one character, and a match must end at a terminal node.

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

  • LeetCode 208: Implement Trie (Prefix Tree) — Python Solution

    LeetCode 208: Implement Trie (Prefix Tree) is a Medium trie problem. This Python walkthrough develops a nested child maps 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.

    DifficultyMedium
    TopicTrie
    Reusable patternnested child maps
    ComplexityO(L) time per operation and O(total inserted characters) space

    Recognizing the pattern

    A trie shares storage and work across common prefixes, allowing a search to abandon an entire family of words after one failed edge.

    For this problem specifically, each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes. The invariant worth writing beside the code is: The node reached after a prefix represents exactly that character sequence.

    Step-by-step algorithm

    1. Identify the input state consumed by insert(word) and initialize the data required by the nested child maps pattern.
    2. Each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes.
    3. After each update, verify the page’s central invariant: The node reached after a prefix represents exactly that character sequence.
    4. Finish only after the boundary behavior is covered: An inserted word can also be a prefix of a longer word.

    Python solution

    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

    Reading the implementation

    The main entry point is insert(word). The named working state includes node; those variables make the nested child maps state visible instead of hiding it in incidental control flow.

    The implementation uses 2 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. Early returns stop as soon as the answer is forced, avoiding work that cannot change the result. In concrete terms, each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes.

    Correctness argument

    Initialization. The data structure starts with exactly the information known before any input element is processed.

    Preservation. Each character follows or creates a child node, and a terminal flag distinguishes complete words from prefixes. Each update records the current item without invalidating earlier decisions; consequently, the node reached after a prefix represents exactly that character sequence.

    Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

    Complexity and trade-offs

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

    A hash set is simpler for exact words, but it cannot answer prefix or wildcard traversal without examining many candidates. 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.

    trie=Trie(); trie.insert("apple"); assert trie.search("apple") and trie.startsWith("app") and not trie.search("app")

    Common mistakes and edge cases

    • Problem-specific boundary: An inserted word can also be a prefix of a longer word.
    • Pattern-level pitfall: A prefix node is not necessarily a complete word; terminal markers and wildcard branching need separate handling.
    • Invariant check: after every update, confirm that the node reached after a prefix represents exactly that character sequence.

    Interview review checklist

    • Explain why nested child maps matches the structure of this input.
    • State the invariant in one sentence before tracing code: The node reached after a prefix represents exactly that character sequence.
    • Derive O(L) time per operation and O(total inserted characters) space from how many times each element or state is visited.
    • Test the boundary explicitly: An inserted word can also be a prefix of a longer word.

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

  • LeetCode 127: Word Ladder — Python Solution

    LeetCode 127: Word Ladder is a Hard graph bfs problem. This Python walkthrough develops a wildcard-neighbor 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.

    DifficultyHard
    TopicGraph BFS
    Reusable patternwildcard-neighbor BFS
    ComplexityO(NL^2) preprocessing and traversal time and O(NL) space

    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, index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern. The invariant worth writing beside the code is: The first BFS layer reaching a word uses the shortest transformation sequence.

    Step-by-step algorithm

    1. Identify the input state consumed by ladderLength(beginWord, endWord, wordList) and initialize the data required by the wildcard-neighbor BFS pattern.
    2. Index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern.
    3. After each update, verify the page’s central invariant: The first BFS layer reaching a word uses the shortest transformation sequence.
    4. Finish only after the boundary behavior is covered: The end word must be in the dictionary; each transformation changes exactly one character.

    Python solution

    from collections import defaultdict, deque
    
    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

    Reading the implementation

    The main entry point is ladderLength(beginWord, endWord, wordList). The named working state includes patterns, width, queue, word, pattern; those variables make the wildcard-neighbor BFS state visible instead of hiding it in incidental control flow.

    The implementation uses 5 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. In concrete terms, index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern.

    Correctness argument

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

    Preservation. Index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern. Because the queue processes earlier layers first, the first BFS layer reaching a word uses the shortest transformation sequence.

    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(NL^2) preprocessing and traversal time and O(NL) 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().ladderLength("hit","cog",["hot","dot","dog","lot","log","cog"])==5

    Common mistakes and edge cases

    • Problem-specific boundary: The end word must be in the dictionary; each transformation changes exactly one character.
    • 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 the first BFS layer reaching a word uses the shortest transformation sequence.

    Interview review checklist

    • Explain why wildcard-neighbor BFS matches the structure of this input.
    • State the invariant in one sentence before tracing code: The first BFS layer reaching a word uses the shortest transformation sequence.
    • Derive O(NL^2) preprocessing and traversal time and O(NL) space from how many times each element or state is visited.
    • Test the boundary explicitly: The end word must be in the dictionary; each transformation changes exactly one character.

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

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

    DifficultyMedium
    TopicGraph BFS
    Reusable patternsingle-character BFS
    ComplexityO(BL) practical time and O(B) space

    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

  • LeetCode 909: Snakes and Ladders — Python Solution

    LeetCode 909: Snakes and Ladders is a Medium graph bfs problem. This Python walkthrough develops a board-index 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.

    DifficultyMedium
    TopicGraph BFS
    Reusable patternboard-index BFS
    ComplexityO(n^2) time and O(n^2) space

    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, map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move. The invariant worth writing beside the code is: The first time BFS reaches a square uses the minimum number of dice throws.

    Step-by-step algorithm

    1. Identify the input state consumed by snakesAndLadders(board) and initialize the data required by the board-index BFS pattern.
    2. Map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move.
    3. After each update, verify the page’s central invariant: The first time BFS reaches a square uses the minimum number of dice throws.
    4. Finish only after the boundary behavior is covered: Do not chain a second jump in the same move; row direction alternates from the bottom.

    Python solution

    from collections import deque
    
    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

    Reading the implementation

    The main entry point is snakesAndLadders(board). The named working state includes n, row_from_bottom, row, col, queue, square; those variables make the board-index BFS state visible instead of hiding it in incidental control flow.

    The implementation uses 2 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. Early returns stop as soon as the answer is forced, avoiding work that cannot change the result. In concrete terms, map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move.

    Correctness argument

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

    Preservation. Map square numbers to boustrophedon coordinates and BFS over dice results, applying at most one snake or ladder per move. Because the queue processes earlier layers first, the first time BFS reaches a square uses the minimum number of dice throws.

    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(n^2) time and O(n^2) 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.

    board=[[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]; assert Solution().snakesAndLadders(board)==4

    Common mistakes and edge cases

    • Problem-specific boundary: Do not chain a second jump in the same move; row direction alternates from the bottom.
    • 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 the first time BFS reaches a square uses the minimum number of dice throws.

    Interview review checklist

    • Explain why board-index BFS matches the structure of this input.
    • State the invariant in one sentence before tracing code: The first time BFS reaches a square uses the minimum number of dice throws.
    • Derive O(n^2) time and O(n^2) space from how many times each element or state is visited.
    • Test the boundary explicitly: Do not chain a second jump in the same move; row direction alternates from the bottom.

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

  • LeetCode 210: Course Schedule II — Python Solution

    LeetCode 210: Course Schedule II is a Medium graph general problem. This Python walkthrough develops a topological ordering 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.

    DifficultyMedium
    TopicGraph General
    Reusable patterntopological ordering
    ComplexityO(V+E) time and O(V+E) space

    Recognizing the pattern

    Graph traversal separates reachability from representation: adjacency describes possible moves, while a visited structure prevents repeated work.

    For this problem specifically, use Kahn’s algorithm and append each removed zero-indegree course to the order; return it only if every course is processed. The invariant worth writing beside the code is: Every appended course has all prerequisites earlier in the output.

    Step-by-step algorithm

    1. Identify the input state consumed by findOrder(numCourses, prerequisites) and initialize the data required by the topological ordering pattern.
    2. Use Kahn’s algorithm and append each removed zero-indegree course to the order; return it only if every course is processed.
    3. After each update, verify the page’s central invariant: Every appended course has all prerequisites earlier in the output.
    4. Finish only after the boundary behavior is covered: A cycle returns an empty list; isolated courses begin with zero indegree.

    Python solution

    from collections import deque
    
    class Solution:
        def findOrder(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)
            order = []
            while queue:
                course = queue.popleft(); order.append(course)
                for following in graph[course]:
                    indegree[following] -= 1
                    if indegree[following] == 0: queue.append(following)
            return order if len(order) == numCourses else []

    Reading the implementation

    The main entry point is findOrder(numCourses, prerequisites). The named working state includes graph, queue, order, course; those variables make the topological ordering 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, use Kahn’s algorithm and append each removed zero-indegree course to the order; return it only if every course is processed.

    Correctness argument

    Initialization. The data structure starts with exactly the information known before any input element is processed.

    Preservation. Use Kahn’s algorithm and append each removed zero-indegree course to the order; return it only if every course is processed. Each update records the current item without invalidating earlier decisions; consequently, every appended course has all prerequisites earlier in the output.

    Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

    Complexity and trade-offs

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

    DFS and BFS often have the same asymptotic cost; choose DFS for recursive structure and BFS when distance or processing order matters. 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().findOrder(2,[[1,0]])==[0,1]

    Common mistakes and edge cases

    • Problem-specific boundary: A cycle returns an empty list; isolated courses begin with zero indegree.
    • Pattern-level pitfall: Mark a state when it is discovered rather than after all of its neighbors are processed, or cycles can enqueue it repeatedly.
    • Invariant check: after every update, confirm that every appended course has all prerequisites earlier in the output.

    Interview review checklist

    • Explain why topological ordering matches the structure of this input.
    • State the invariant in one sentence before tracing code: Every appended course has all prerequisites earlier in the output.
    • Derive O(V+E) time and O(V+E) space from how many times each element or state is visited.
    • Test the boundary explicitly: A cycle returns an empty list; isolated courses begin with zero indegree.

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 207. Course Schedule · Next: 909. Snakes and Ladders

  • LeetCode 207: Course Schedule — Python Solution

    LeetCode 207: Course Schedule is a Medium graph general problem. This Python walkthrough develops a Kahn topological sort 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.

    DifficultyMedium
    TopicGraph General
    Reusable patternKahn topological sort
    ComplexityO(V+E) time and O(V+E) space

    Recognizing the pattern

    Graph traversal separates reachability from representation: adjacency describes possible moves, while a visited structure prevents repeated work.

    For this problem specifically, count prerequisites as indegrees, repeatedly remove zero-indegree courses, and reduce the indegrees of dependent courses. The invariant worth writing beside the code is: The queue contains exactly the currently schedulable courses with no remaining prerequisites.

    Step-by-step algorithm

    1. Identify the input state consumed by canFinish(numCourses, prerequisites) and initialize the data required by the Kahn topological sort pattern.
    2. Count prerequisites as indegrees, repeatedly remove zero-indegree courses, and reduce the indegrees of dependent courses.
    3. After each update, verify the page’s central invariant: The queue contains exactly the currently schedulable courses with no remaining prerequisites.
    4. Finish only after the boundary behavior is covered: Processing fewer than all courses proves a directed cycle.

    Python solution

    from collections import deque
    
    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

    Reading the implementation

    The main entry point is canFinish(numCourses, prerequisites). The named working state includes graph, queue, completed, course; those variables make the Kahn topological sort 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, count prerequisites as indegrees, repeatedly remove zero-indegree courses, and reduce the indegrees of dependent courses.

    Correctness argument

    Initialization. The data structure starts with exactly the information known before any input element is processed.

    Preservation. Count prerequisites as indegrees, repeatedly remove zero-indegree courses, and reduce the indegrees of dependent courses. Each update records the current item without invalidating earlier decisions; consequently, the queue contains exactly the currently schedulable courses with no remaining prerequisites.

    Termination. The traversal consumes a finite input or finite state space. At the end, the invariant covers the complete input, which is precisely the condition required for the returned result.

    Complexity and trade-offs

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

    DFS and BFS often have the same asymptotic cost; choose DFS for recursive structure and BFS when distance or processing order matters. 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().canFinish(2,[[1,0]]) and not Solution().canFinish(2,[[1,0],[0,1]])

    Common mistakes and edge cases

    • Problem-specific boundary: Processing fewer than all courses proves a directed cycle.
    • Pattern-level pitfall: Mark a state when it is discovered rather than after all of its neighbors are processed, or cycles can enqueue it repeatedly.
    • Invariant check: after every update, confirm that the queue contains exactly the currently schedulable courses with no remaining prerequisites.

    Interview review checklist

    • Explain why Kahn topological sort matches the structure of this input.
    • State the invariant in one sentence before tracing code: The queue contains exactly the currently schedulable courses with no remaining prerequisites.
    • Derive O(V+E) time and O(V+E) space from how many times each element or state is visited.
    • Test the boundary explicitly: Processing fewer than all courses proves a directed cycle.

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