4          <- level 0
      /   \
     2     5       <- level 1
    / \
   1   3            <- level 2

BFS visit order: 4 → 2 → 5 → 1 → 3
(visit all nodes on one level before moving to the next)

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # BFS level order: process nodes level by level, 
        # (left -> right) within each level

        # Empty check:
        # Tree is empty, return empty list
        if not root:
            return []
        
        # List of groups by level
        groups = []

        # Iterative queue for BFS:
        # holds nodes to process, starting with root as first level
        # sc: O(n)
        queue = deque([root])  # start with root
        
        # 
        while queue:

            # Number of nodes remaining in deque,
            # which represent the nodes at the current depth level
            depthLevelSize = len(queue)

            # List of nodes at current level
            level = []
            
            # For the number of nodes remaining in deque and this level,
            # pop and process each node in this level
            for _ in range(depthLevelSize):

                # FIFO: pop leftmost node from queue and process
                node = queue.popleft()
                level.append(node.val)
                
                # after processing, enqueue children for next level,
                # to represent the next level of the tree for BFS
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            # Add nodes at current level to 
            groups.append(level)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return groups

    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # DFS pre order: root -> left -> right
        # 1. Create list of groups by depth level
        # 2. Process root and track current depth level during traversal
        #    and add node to corresponding depth group
        
        # Depth level groups
        # sc: O(n)
        groups = []
        
        def dfs(node, depth):

            # Empty check:
            # Reached leaf, return
            if not node:
                return
            
            # Check:
            # if next depth level has been reached, add a new group
            if len(groups) == depth:
                groups.append([])
            
            # For each node we encounter, add its value for pre order
            # to the corresponding depth group
            groups[depth].append(node.val)
            
            # Track current depth level and recurse to children
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
        
        dfs(root, 0)

        # overall: tc O(n)
        # overall: sc O(n)
        return groups

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # BFS pre order: process level : root -> left -> right
        # 1. For each level
        # 2. Process root -> :
        #    grab length of level, if root is last element in group, add to res
        # 3. Process -> left -> right :
        # Result: right most element of each level added
        
        # Empty check:
        # No rightmost to return, return empty list
        if not root:
            return []
        
        # List of the right most element for each level
        res = []
        
        # Iterative BFS queue
        queue = deque([root])
        
        while queue:

            # Number of nodes remaining in deque,
            # which represent the nodes at the current depth level
            depthLevelSize = len(queue)

            # For the number of nodes remaining in deque and this level,
            # pop and process each node in this level
            for i in range(depthLevelSize):

                # Grab the leftmost node from queue and process
                node = queue.popleft()

                # Check:
                # Validate if this node is the right most at this level
                if i == depthLevelSize - 1:
                    res.append(node.val)

                # Queue children for processing later
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        
        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        
        # Note:
        # DFS Modified Pre Order: (root -> right -> left) instead of (root -> left -> right)
        # Modified pre order goes root -> right, which guarantees we explore
        # the farthest right possible, before exploring left, 
        # and with that assumption, every time we reach a new depth,
        # we are guaranteed to be at the right most element for that depth level

        # Tracking right most elements for each level
        # sc: O(n)
        res = []
        
        def dfs(node, depth):

            # Empty check:
            # Reached leaf, return
            if not node:
                return

            # Check:
            # If we have reached a new depth, using our assumption of
            # (root -> right -> left), we can guarantee that we are at the right most node
            # for this level, and can add it to our right most list 
            if depth == len(result):
                res.append(node.val)

            # Modified Pre Order:
            # Explore right subtree first, then left subtree
            dfs(node.right, depth + 1)
            dfs(node.left, depth + 1)
        
        # Init depth tracker at 0
        dfs(root, 0)

        # overall: tc O(n)
        # overall: sc O(n) for skewed trees / O(log(n)) for balanced trees
        return res

    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        
        # Note:
        # BFS level order + zigzag
        # 1. Standard BFS level traversal, always append left -> right (natural order)
        # 2. To create a zig zag effect, 
        #    reverse the completed level list when direction is right -> left

        # Empty check:
        # tree is empty
        if not root:
            return []

        # Iterative BFS Queue
        queue = deque([root])

        # Reverse flag used to determine if we need to flip this iteration
        reverseFlag = True

        # zig zagged groups
        res = []

        while queue:

            # Number of nodes remaining at this depth level
            depthLevelSize = len(queue)

            # Nodes at this depth level
            group = []

            for _ in range(depthLevelSize):
                node = queue.popleft()

                # Always append normally
                group.append(node.val)

                # Normal BFS expansion (unaffected by direction)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # Reverse the queue to apply zigzag effect if reverse flag is on
            res.append(group if reverseFlag else group[::-1])

            # Flip reveres flag for next iteration
            reverseFlag = not reverseFlag

        # overall: tc O(n)
        # overall: sc O(n)
        return res

    def openLock(self, deadends: List[str], target: str) -> int:
        
        # BFS over the lock's state graph

        # Each 4-digit combination is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build, 
        # but instead states are generated on the fly.
        # An edge connects two states if one wheel-turn transforms one into another,
        # as each of the 4 wheels can turn +1 or -1 with wraparound 0 <-> 9
        # BFS explores states level by level, so the first time a 'target' is dequeued,
        # it is guaranteed to be the shortest number of turns
        

        # Dead end states set
        # sc: O(n)
        dead = set(deadends)
        
        # Edge Case:
        # If starting position is a dead end, we cannot move.
        if "0000" in dead:
            return -1
        
        # Iterative BFS Queue:
        # set starting position as "0000" as begin exploring
        queue = deque([("0000", 0)])
        visited = set(["0000"])
        
        while queue:

            # Pop a state from the queue
            state, moves = queue.popleft()
            
            # Check:
            # if target reached, we are guaranteed to have minimum number of moves
            if state == target:
                return moves
            
            # Explore Neighbors:
            # turn all 4 wheels in +/- 1 directions
            for i in range(4):

                # pick 1 of the 4 wheels
                digit = int(state[i])
                
                # Two possible rotations:
                # +1 and -1 (with wraparound)
                for change in (-1, 1):
                    
                    new_digit = (digit + change) % 10
                    
                    # Grab original wheel digits, 
                    # except for the one we just rotated
                    newState = (state[:i] + str(new_digit) + state[i+1:])
                    
                    # Early Pruning:
                    # only queue state if:
                    # - not visited
                    # - not a dead end
                    if newState not in visited and newState not in dead:
                        
                        visited.add(newState)
                        queue.append((newState, moves + 1))

        # Exhausted all possible rotation combinations without finding target

        # overall: tc O(10^4)
        # overall: sc O(10^4)
        return -1

    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        
        # Bidirectional BFS over the gene mutation graph

        # Same implicit graph as single-source BFS: nodes are gene strings, edges
        # connect genes differing by exactly one slot. Instead of searching only
        # forward from startGene, we simultaneously search backward from endGene.
        # We always expand the smaller of the two frontiers first, which keeps
        # the branching factor as small as possible at each step.
        # The two searches are guaranteed to meet at the shortest path's midpoint,
        # since BFS explores level by level from both directions.

        # Turn valid gene list into set
        # sc: O(n)
        bankSet = set(bank)

        # Edge Case:
        # endGene is not reachable
        if endGene not in bankSet:
            return -1

        # All gene slot chars
        gene_chars = ['A', 'C', 'G', 'T']

        # Two Frontiers:
        # each frontier is a dict mapping gene -> mutation count so far
        # start both at 0 mutations
        frontStart = {startGene: 0}
        frontEnd = {endGene: 0}

        # Global visited set shared across both directions,
        # prevents re-expanding a gene already claimed by either search
        visited = set([startGene, endGene])

        while frontStart and frontEnd:

            # Greedy Balancing:
            # always expand the smaller frontier first to minimize
            # the total number of states generated per level
            if len(frontStart) > len(frontEnd):
                frontStart, frontEnd = frontEnd, frontStart

            # Next level's frontier for the side being expanded
            nextFront = {}

            # Explore Neighbors:
            # modify every gene slot to every other possible gene char,
            # for every gene currently in the smaller frontier
            for geneString, mutations in frontStart.items():
                for i in range(len(geneString)):
                    for c in gene_chars:

                        # Skip original gene
                        if c == geneString[i]:
                            continue

                        rotatedGene = geneString[:i] + c + geneString[i + 1:]

                        # Meeting Point:
                        # if the other frontier already contains this gene,
                        # the two searches have met -> shortest path found
                        if rotatedGene in frontEnd:
                            return mutations + frontEnd[rotatedGene] + 1

                        # Early Pruning:
                        # only queue mutations that are valid (in bank)
                        # and not already visited by either direction
                        if rotatedGene in bankSet and rotatedGene not in visited:

                            visited.add(rotatedGene)
                            nextFront[rotatedGene] = mutations + 1

            # Advance the expanded side to its next level
            frontStart = nextFront

        # Exhausted all reachable mutations without the two searches meeting

        # overall: tc O(n), same asymptotic bound as single-source BFS,
        #   but frontiers stay ~sqrt() the size in practice since branching
        #   is cut short by meeting in the middle rather than reaching full depth
        # overall: sc O(n), for the bankSet/visited set storing up to n genes
        return -1

    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        
        # BFS over the gene mutation graph

        # Each gene string combination is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build, 
        # but instead states are generated on the fly.
        # An edge connects two states if one gene slot modification transforms
        # one into another, as there are 4 possible gene letters.
        # BFS explores states level by level, so the first time a 'target' is dequeued,
        # it is guaranteed to be the shortest number of turns
        # as well as guaranteed to have all possible gene combinations
        
        
        # Turn valid gene list into set
        # sc: O(n)
        bankSet = set(bank)

        # Edge Case:
        # endGene is not reachable, no transformation sequence exists
        if endGene not in bankSet:
            return -1

        # All gene slot chars
        gene_chars = ['A', 'C', 'G', 'T']

        # Iterative BFS Queue
        queue = deque([(startGene, 0)])

        # Tracking 
        # sc: O(n^4)
        visited = {startGene}

        while queue:
            geneString, mutations = queue.popleft()

            # Reached target gene:
            # Ensured we have taken the minimum number of steps to get to
            # the final combination, which implies we have all possible previous 
            # combinations in the mutations list
            if geneString == endGene:
                return mutations

            # Modify each gene slot
            for i in range(len(geneString)):

                # Explore Neighbor:
                # Replace each gene slot with all other 3 genes
                for c in gene_chars:

                    # Skip original gene
                    if c == geneString[i]:
                        continue

                    # Grab all original gene slots, 
                    # except for the slot we just modified
                    rotatedGene = geneString[:i] + c + geneString[i + 1:]

                    # Early Pruning:
                    # Only queue mutations that are valid (in bank) and unseen
                    if rotatedGene in bankSet and rotatedGene not in visited:
                        visited.add(rotatedGene)
                        queue.append((rotatedGene, mutations + 1))

        # Exhausted all reachable mutations without finding endGene

        # overall: tc O(n)
        # overall: sc O(n)
        return -1

    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:

        # Bidirectional BFS:
        # Regular BFS explores outward from startGene alone, and in the
        # worst case its frontier can grow to cover almost the entire
        # search space before reaching endGene. Bidirectional BFS
        # instead grows TWO frontiers at once -- one from startGene,
        # one from endGene -- and alternates expanding whichever
        # frontier is smaller. The two searches meet in the middle,
        # which shrinks the total explored space dramatically since
        # each side only needs to cover roughly half the distance.

        # Why swapping to expand the smaller frontier matters:
        # if one side's frontier is much smaller than the other, it's
        # cheaper to expand a full layer of the small side than a full
        # layer of the large side -- this keeps the total work bounded
        # by whichever side is currently "cheapest," rather than always
        # paying the cost of the (potentially huge) start-side frontier.

        bankSet = set(bank)

        # Edge Case:
        # endGene is not reachable, no transformation sequence exists
        if endGene not in bankSet:
            return -1

        # All gene slot chars
        gene_chars = ['A', 'C', 'G', 'T']

        # Two Frontiers:
        # each is a set of gene strings currently reachable in the
        # same number of mutations from their respective origin
        # sc: O(n) per frontier
        startFrontier = {startGene}
        endFrontier = {endGene}

        # Tracking:
        # genes already visited from EITHER direction, so neither
        # search wastes time re-expanding the same state
        # sc: O(n)
        visited = {startGene, endGene}

        mutations = 0

        # tc: O(n) overall, each gene expanded at most once across
        # both frontiers combined
        while startFrontier and endFrontier:

            # Swap to Smaller:
            # always expand whichever frontier currently has fewer
            # states -- keeps each layer's expansion cost minimal
            if len(startFrontier) > len(endFrontier):
                startFrontier, endFrontier = endFrontier, startFrontier

            nextFrontier = set()

            # Expand Frontier:
            # generate every one-mutation neighbor for every gene
            # currently in the smaller frontier
            for geneString in startFrontier:
                for i in range(len(geneString)):
                    for c in gene_chars:

                        # Skip original gene
                        if c == geneString[i]:
                            continue

                        rotatedGene = geneString[:i] + c + geneString[i + 1:]

                        # Meet in the Middle:
                        # if this mutation already exists in the OTHER
                        # frontier, the two searches have connected --
                        # this mutation count plus the other side's
                        # equal-depth mutation count gives the answer
                        if rotatedGene in endFrontier:
                            return mutations + 1

                        # Early Pruning:
                        # only continue expanding through valid,
                        # unseen mutations
                        if rotatedGene in bankSet and rotatedGene not in visited:
                            visited.add(rotatedGene)
                            nextFrontier.add(rotatedGene)

            # Advance:
            # the smaller frontier becomes this newly generated layer,
            # one mutation deeper than before
            startFrontier = nextFrontier
            mutations += 1

        # Exhausted all reachable mutations from both directions
        # without the two searches ever meeting

        # overall: tc O(n), n = number of valid genes in bank,
        #          but with a much smaller effective search space
        #          than single-direction BFS in practice
        # overall: sc O(n), for the two frontiers and visited set
        return -1

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
        # BFS over the word transformation graph

        # Each word is represented as a node in an implicit graph,
        # meaning there is no literal grid/list to build,
        # but instead states are generated on the fly.
        # An edge connects two words if they differ by exactly one letter
        # as each of the L letter slots can be swapper to any of the other 25 letters
        # BFS explores states level by level, so the first time 'endWord' is dequeued,
        # it is guaranteed to be reached via the shortest transformation sequence

        # Valid word list as a set
        # sc: O(V)
        wordSet = set(wordList)

        # Empty Check: 
        # endWord is not reachable, no transformation sequence exists
        # tc: O(1)
        if endWord not in wordSet:
            return 0

        # All possible letters for each slot
        letters = 'abcdefghijklmnopqrstuvwxyz'

        # Iterative BFS Queue:
        # set starting position as beginWord, sequence steps starts at 1
        # (LeetCode counts the beginWord itself as the first word in the sequence)
        queue = deque([(beginWord, 1)])
        visited = set([beginWord])

        while queue:

            # Pop a transformation
            word, steps = queue.popleft()

            # Check:
            # if endWord reached, we are guaranteed to have the minimum sequence steps
            if word == endWord:
                return steps

            # Explore Neighbors:
            # swap every letter slot to every other possible letter
            # tc: O(L)
            for i in range(len(word)):

                # Grab original letter,
                # except for the one we're about to swap
                for c in letters:

                    # Skip original letter
                    if c == word[i]:
                        continue

                    # New transformation
                    newWord = word[:i] + c + word[i + 1:]

                    # Early Pruning:
                    # - not in wordSet, invalid word
                    # - already visited, we reached this via a shorter sequence
                    if newWord in wordSet and newWord not in visited:

                        # queue new valid transformation
                        queue.append((newWord, steps+1))
                        visited.add(newWord)

        # Exhausted all possible transformations without finding endWord

        # overall: tc O(n * L^2), where n = len(wordList), l = len(beginWord)
        #   for each word popped, we try l slots * 26 letters = O(l * 26),
        #   and each candidate word construction/hashing costs O(l)
        # overall: sc O(n * L), for the wordSet/visited set storing up to n words of steps l
        return -1

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        
        # Bidirectional BFS over the word transformation graph

        # Same implicit graph as single-source BFS: nodes are words, edges connect
        # words differing by exactly one letter. Instead of searching only forward
        # from beginWord, we simultaneously search backward from endWord.
        # We always expand the smaller of the two frontiers first, which keeps
        # the branching factor as small as possible at each step.
        # The two searches are guaranteed to meet at the shortest path's midpoint,
        # since BFS explores level by level from both directions.

        # Valid word list as a set
        # sc: O(n)
        wordSet = set(wordList)

        # Edge Case:
        # If endWord is not reachable, no transformation sequence exists
        if endWord not in wordSet:
            return -1

        # All possible letters for each slot
        letters = 'abcdefghijklmnopqrstuvwxyz'

        # Two Frontiers:
        # each frontier is a dict mapping word -> sequence length so far
        # start both at length 1 (beginWord/endWord count as step 1)
        frontBegin = {beginWord: 1}
        frontEnd = {endWord: 1}

        # Global visited set shared across both directions,
        # prevents re-expanding a word already claimed by either search
        visited = set([beginWord, endWord])

        while frontBegin and frontEnd:

            # Greedy Balancing:
            # always expand the smaller frontier first to minimize
            # the total number of states generated per level
            if len(frontBegin) > len(frontEnd):
                frontBegin, frontEnd = frontEnd, frontBegin

            # Next level's frontier for the side being expanded
            nextFront = {}

            # Explore Neighbors:
            # swap every letter slot to every other possible letter,
            # for every word currently in the smaller frontier
            for word, length in frontBegin.items():
                for i in range(len(word)):
                    for c in letters:

                        # Skip original letter
                        if c == word[i]:
                            continue

                        newWord = word[:i] + c + word[i + 1:]

                        # Meeting Point:
                        # if the other frontier already contains this word,
                        # the two searches have met -> shortest path found
                        if newWord in frontEnd:
                            return length + frontEnd[newWord]

                        # Early Pruning:
                        # only queue state if:
                        # - it's a valid word (in wordSet)
                        # - not already visited by either direction
                        if newWord in wordSet and newWord not in visited:

                            visited.add(newWord)
                            nextFront[newWord] = length + 1

            # Advance the expanded side to its next level
            frontBegin = nextFront

        # Exhausted all possible transformations without the two searches meeting

        # overall: tc O(n * l^2), same asymptotic bound as single-source BFS,
        #   but frontiers stay ~sqrt() the size in practice since branching
        #   is cut short by meeting in the middle rather than reaching full depth
        # overall: sc O(n * l), for wordSet/visited storing up to n words of length l
        return -1

    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        
        # BFS over the maze grid

        # Each cell is represented as a node in an implicit graph, the
        # grid itself acts as the adjacency structure, no separate
        # graph needs to be built.
        # An edge connects two cells if they're adjacent (up/down/left/right)
        # and the destination cell is empty ('.').
        # BFS explores cells level by level, so the first time a border
        # cell is dequeued, it is guaranteed to be reached via the
        # shortest number of steps.

        rows, cols = len(maze), len(maze[0])

        # 4 cardinal directions
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # Iterative BFS Queue:
        # start at entrance, 0 steps taken
        entranceRow, entranceCol = entrance
        queue = deque([(entranceRow, entranceCol, 0)])
        visited = set([(entranceRow, entranceCol)])

        while queue:

            # Pop a cell from the queue
            row, col, steps = queue.popleft()

            # Check:
            # if current cell is a border cell and not the entrance,
            # we are guaranteed to have the minimum number of steps
            # (entrance is excluded up front by only checking after the first pop)
            if steps > 0 and (row == 0 or row == rows - 1 or
                               col == 0 or col == cols - 1):
                return steps

            # Explore Neighbors:
            # move to all 4 adjacent cells
            for dr, dc in directions:

                nr, nc = row + dr, col + dc

                # Bounds Check:
                # stay within the grid
                if 0 <= nr < rows and 0 <= nc < cols:

                    # Early Pruning:
                    # only queue cell if:
                    # - not a wall
                    # - not already visited
                    if maze[nr][nc] == '.' and (nr, nc) not in visited:

                        visited.add((nr, nc))
                        queue.append((nr, nc, steps + 1))

        # Exhausted all reachable cells without finding a border exit

        # overall: tc O(m * n), each cell is visited and processed at most once
        # overall: sc O(m * n), for the visited set and queue storing up to every cell in the grid
        return -1

    def minKnightMoves(self, x: int, y: int) -> int:
        
        # BFS over the knight's move graph

        # Each square on the infinite chessboard is represented as a node
        # in an implicit graph, meaning there is no literal grid/list to
        # build, but instead squares are generated on the fly.
        # An edge connects two squares if a single knight move (one of
        # the 8 "L" shaped jumps) transforms one into the other.
        # BFS explores squares level by level, so the first time (x, y)
        # is dequeued, it is guaranteed to be reached via the minimum
        # number of moves.

        # Symmetry Pruning:
        # The knight's movement is symmetric across both axes, a move
        # that reaches (x, y) can be mirrored to reach (-x, y), (x, -y),
        # or (-x, -y) in the same number of moves. So we only ever need
        # to search within the first quadrant (x >= 0, y >= 0), and take
        # the absolute value of the target up front. This roughly
        # quarters the search space compared to searching the full plane.

        # Normalize target into the first quadrant
        x, y = abs(x), abs(y)

        # Edge Case:
        # already at the target
        if x == 0 and y == 0:
            return 0

        # All 8 possible knight moves
        moves = [(-2, 1), (-1, 2), (1, 2), (2, 1),
                 (2, -1), (1, -2), (-1, -2), (-2, -1)]

        # Iterative BFS Queue:
        # start at origin, 0 moves taken
        queue = deque([(0, 0, 0)])
        visited = set([(0, 0)])

        while queue:

            # Pop a position from the queue
            cx, cy, moveCount = queue.popleft()

            # Check:
            # if target reached, we are guaranteed to have the minimum number of moves
            if cx == x and cy == y:
                return moveCount

            # Explore Neighbors:
            # apply all 8 possible knight moves
            for dx, dy in moves:

                nx, ny = cx + dx, cy + dy

                # Pruning Bound:
                # clamp exploration to a small buffer past the first quadrant,
                # since occasionally dipping to -1 or -2 is needed to route
                # around the target efficiently, but going further negative
                # or far beyond the target never helps
                if -2 <= nx <= x + 2 and -2 <= ny <= y + 2:

                    # Early Pruning:
                    # only queue position if not already visited
                    if (nx, ny) not in visited:

                        visited.add((nx, ny))
                        queue.append((nx, ny, moveCount + 1))

        # overall: tc O(max(x, y)^2), bounded search space after symmetry
        #   and pruning keeps the frontier close to the target region
        # overall: sc O(max(x, y)^2), for the visited set storing explored squares
        return -1

    def minKnightMoves(self, x: int, y: int) -> int:
        
        # Bidirectional BFS over the knight's move graph

        # Same implicit graph as single-source BFS: nodes are board
        # squares, edges connect squares one knight move apart. Instead
        # of searching only forward from the origin, we simultaneously
        # search backward from the target. We always expand the smaller
        # of the two frontiers first, which keeps the branching factor
        # as small as possible at each step.
        # The two searches are guaranteed to meet at the shortest path's
        # midpoint, since BFS explores level by level from both directions.

        # Symmetry Pruning:
        # The knight's movement is symmetric across both axes, so we
        # normalize the target into the first quadrant up front, the
        # same way as single-source BFS. This roughly quarters the
        # search space compared to searching the full plane.

        # Normalize target into the first quadrant
        x, y = abs(x), abs(y)

        # Edge Case:
        # already at the target
        if x == 0 and y == 0:
            return 0

        # All 8 possible knight moves
        moves = [(-2, 1), (-1, 2), (1, 2), (2, 1),
                 (2, -1), (1, -2), (-1, -2), (-2, -1)]

        # Two Frontiers:
        # each frontier is a dict mapping position -> move count so far
        # start both at 0 moves
        frontStart = {(0, 0): 0}
        frontEnd = {(x, y): 0}

        # Global visited set shared across both directions,
        # prevents re-expanding a square already claimed by either search
        visited = set([(0, 0), (x, y)])

        while frontStart and frontEnd:

            # Greedy Balancing:
            # always expand the smaller frontier first to minimize
            # the total number of states generated per level
            if len(frontStart) > len(frontEnd):
                frontStart, frontEnd = frontEnd, frontStart

            # Next level's frontier for the side being expanded
            nextFront = {}

            # Explore Neighbors:
            # apply all 8 possible knight moves,
            # for every position currently in the smaller frontier
            for (cx, cy), moveCount in frontStart.items():
                for dx, dy in moves:

                    nx, ny = cx + dx, cy + dy

                    # Meeting Point:
                    # if the other frontier already contains this position,
                    # the two searches have met -> shortest path found
                    if (nx, ny) in frontEnd:
                        return moveCount + frontEnd[(nx, ny)] + 1

                    # Early Pruning:
                    # only queue position if not already visited by either direction
                    if (nx, ny) not in visited:

                        visited.add((nx, ny))
                        nextFront[(nx, ny)] = moveCount + 1

            # Advance the expanded side to its next level
            frontStart = nextFront

        # overall: tc O(max(x, y)^2), same asymptotic bound as single-source
        #   BFS, but frontiers stay ~sqrt() the size in practice since
        #   branching is cut short by meeting in the middle
        # overall: sc O(max(x, y)^2), for the visited set storing explored squares
        return -1