Daniel P. Gleason

Category: LeetCode Solutions

  • LeetCode 100: Same Tree — Python Solution

    Solve LeetCode 100: Same Tree in Python with a paired recursion approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyEasy
    TopicBinary Tree General
    Reusable patternpaired recursion
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    Two nodes match when both are absent, or both exist with equal values and matching left and right subtrees.

    Algorithm

    1. Two nodes match when both are absent, or both exist with equal values and matching left and right subtrees.
    2. Maintain this invariant: Every recursive pair represents corresponding positions in the two trees.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def isSameTree(self, p, q):
        if not p or not q:
            return p is q
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

    Why this is correct

    The proof follows the maintained state: Every recursive pair represents corresponding positions in the two trees. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    One missing node immediately distinguishes the structures.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 104. Maximum Depth of Binary Tree · Next: 226. Invert Binary Tree

  • LeetCode 226: Invert Binary Tree — Python Solution

    Solve LeetCode 226: Invert Binary Tree in Python with a recursive swap approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyEasy
    TopicBinary Tree General
    Reusable patternrecursive swap
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    Swap each node’s children and recursively invert the two resulting subtrees.

    Algorithm

    1. Swap each node’s children and recursively invert the two resulting subtrees.
    2. Maintain this invariant: Every returned subtree is the mirror image of its original subtree.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def invertTree(self, root):
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

    Why this is correct

    The proof follows the maintained state: Every returned subtree is the mirror image of its original subtree. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    An empty tree remains empty.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 100. Same Tree · Next: 101. Symmetric Tree

  • LeetCode 101: Symmetric Tree — Python Solution

    Solve LeetCode 101: Symmetric Tree in Python with a mirror recursion approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyEasy
    TopicBinary Tree General
    Reusable patternmirror recursion
    ComplexityO(n) time and O(h) recursion space

    What the problem is testing

    Compare the outer and inner children of paired nodes: left with right and right with left.

    Algorithm

    1. Compare the outer and inner children of paired nodes: left with right and right with left.
    2. Maintain this invariant: Each recursive pair must occupy mirrored positions around the root.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def isSymmetric(self, root):
        def mirror(left, right):
            if not left or not right:
                return left is right
            return left.val == right.val and mirror(left.left, right.right) and mirror(left.right, right.left)
        return mirror(root.left, root.right) if root else True

    Why this is correct

    The proof follows the maintained state: Each recursive pair must occupy mirrored positions around the root. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    Two missing mirrored nodes match; exactly one missing node fails.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 226. Invert Binary Tree · Next: 105. Construct Binary Tree from Preorder and Inorder Traversal

  • LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal — Python Solution

    Solve LeetCode 105: Construct Binary Tree from Preorder and Inorder Traversal in Python with a indexed recursive partition approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyMedium
    TopicBinary Tree General
    Reusable patternindexed recursive partition
    ComplexityO(n) time and O(n) space

    What the problem is testing

    Take roots from preorder in order and use an inorder index map to split each subtree into left and right ranges.

    Algorithm

    1. Take roots from preorder in order and use an inorder index map to split each subtree into left and right ranges.
    2. Maintain this invariant: The preorder cursor always identifies the root of the current inorder range.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def buildTree(self, preorder, inorder):
        position = {value: i for i, value in enumerate(inorder)}
        pre_index = 0
        def build(left, right):
            nonlocal pre_index
            if left > right:
                return None
            value = preorder[pre_index]
            pre_index += 1
            root = TreeNode(value)
            split = position[value]
            root.left = build(left, split - 1)
            root.right = build(split + 1, right)
            return root
        return build(0, len(inorder) - 1)

    Why this is correct

    The proof follows the maintained state: The preorder cursor always identifies the root of the current inorder range. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    Values are unique; empty inorder ranges return no node.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 101. Symmetric Tree · Next: 106. Construct Binary Tree from Inorder and Postorder Traversal

  • LeetCode 25: Reverse Nodes in k-Group — Python Solution

    Solve LeetCode 25: Reverse Nodes in k-Group in Python with a group boundary reversal approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyHard
    TopicLinked List
    Reusable patterngroup boundary reversal
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Find the kth node from the previous group tail. If it exists, reverse exactly that closed group and reconnect both ends.

    Algorithm

    1. Find the kth node from the previous group tail. If it exists, reverse exactly that closed group and reconnect both ends.
    2. Maintain this invariant: Every completed group is reversed and connected, while nodes after the next boundary remain untouched.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def reverseKGroup(self, head, k):
        dummy = ListNode(0, head)
        group_prev = dummy
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if not kth:
                    return dummy.next
            group_next = kth.next
            prev, current = group_next, group_prev.next
            while current is not group_next:
                following = current.next
                current.next = prev
                prev, current = current, following
            old_start = group_prev.next
            group_prev.next = kth
            group_prev = old_start

    Why this is correct

    The proof follows the maintained state: Every completed group is reversed and connected, while nodes after the next boundary remain untouched. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    A final group shorter than k remains in original order.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 92. Reverse Linked List II · Next: 19. Remove Nth Node From End of List

  • LeetCode 19: Remove Nth Node From End of List — Python Solution

    Solve LeetCode 19: Remove Nth Node From End of List in Python with a fixed-gap pointers approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyMedium
    TopicLinked List
    Reusable patternfixed-gap pointers
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Advance fast n steps from a dummy node, then move fast and slow together until fast reaches the end; slow precedes the target.

    Algorithm

    1. Advance fast n steps from a dummy node, then move fast and slow together until fast reaches the end; slow precedes the target.
    2. Maintain this invariant: The pointers remain n nodes apart, so the slow pointer stops immediately before the nth node from the end.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def removeNthFromEnd(self, head, n):
        dummy = ListNode(0, head)
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            fast, slow = fast.next, slow.next
        slow.next = slow.next.next
        return dummy.next

    Why this is correct

    The proof follows the maintained state: The pointers remain n nodes apart, so the slow pointer stops immediately before the nth node from the end. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    The dummy node handles removing the original head.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 25. Reverse Nodes in k-Group · Next: 82. Remove Duplicates from Sorted List II

  • LeetCode 82: Remove Duplicates from Sorted List II — Python Solution

    Solve LeetCode 82: Remove Duplicates from Sorted List II in Python with a run skipping approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyMedium
    TopicLinked List
    Reusable patternrun skipping
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Use a dummy predecessor. When equal adjacent values begin a duplicate run, skip the entire run; otherwise advance normally.

    Algorithm

    1. Use a dummy predecessor. When equal adjacent values begin a duplicate run, skip the entire run; otherwise advance normally.
    2. Maintain this invariant: The list before prev contains only values that appeared exactly once in processed input.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(0, head)
        previous = dummy
        while head:
            if head.next and head.val == head.next.val:
                duplicate = head.val
                while head and head.val == duplicate:
                    head = head.next
                previous.next = head
            else:
                previous, head = head, head.next
        return dummy.next

    Why this is correct

    The proof follows the maintained state: The list before prev contains only values that appeared exactly once in processed input. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    Duplicate runs may appear at the head or tail.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 19. Remove Nth Node From End of List · Next: 61. Rotate List

  • LeetCode 61: Rotate List — Python Solution

    Solve LeetCode 61: Rotate List in Python with a cycle then cut approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyMedium
    TopicLinked List
    Reusable patterncycle then cut
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Measure the length, connect tail to head to form a cycle, then cut after length minus k modulo length steps.

    Algorithm

    1. Measure the length, connect tail to head to form a cycle, then cut after length minus k modulo length steps.
    2. Maintain this invariant: The temporary cycle preserves order, and the cut selects the node whose predecessor becomes the new tail.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def rotateRight(self, head, k):
        if not head or not head.next or k == 0:
            return head
        length, tail = 1, head
        while tail.next:
            tail = tail.next
            length += 1
        k %= length
        if k == 0:
            return head
        tail.next = head
        new_tail = head
        for _ in range(length - k - 1):
            new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None
        return new_head

    Why this is correct

    The proof follows the maintained state: The temporary cycle preserves order, and the cut selects the node whose predecessor becomes the new tail. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    Normalize k; empty and one-node lists need no rotation.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 82. Remove Duplicates from Sorted List II · Next: 86. Partition List

  • LeetCode 86: Partition List — Python Solution

    Solve LeetCode 86: Partition List in Python with a stable dual lists approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyMedium
    TopicLinked List
    Reusable patternstable dual lists
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Append nodes to separate less-than and greater-or-equal chains, then connect the chains and terminate the second tail.

    Algorithm

    1. Append nodes to separate less-than and greater-or-equal chains, then connect the chains and terminate the second tail.
    2. Maintain this invariant: Each chain preserves the original relative order of its processed nodes.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def partition(self, head, x):
        low_dummy = low = ListNode()
        high_dummy = high = ListNode()
        while head:
            following = head.next
            if head.val < x:
                low.next = head; low = low.next
            else:
                high.next = head; high = high.next
            head = following
        high.next = None
        low.next = high_dummy.next
        return low_dummy.next

    Why this is correct

    The proof follows the maintained state: Each chain preserves the original relative order of its processed nodes. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    One partition may remain empty; terminate the reused tail to avoid a cycle.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 61. Rotate List · Next: 146. LRU Cache

  • LeetCode 141: Linked List Cycle — Python Solution

    Solve LeetCode 141: Linked List Cycle in Python with a Floyd cycle detection approach. The key is to make the state invariant explicit, so the implementation and complexity follow naturally.

    Open the official problem on LeetCode

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

    DifficultyEasy
    TopicLinked List
    Reusable patternFloyd cycle detection
    ComplexityO(n) time and O(1) extra space

    What the problem is testing

    Advance one pointer by one node and another by two. They meet exactly when the reachable list contains a cycle.

    Algorithm

    1. Advance one pointer by one node and another by two. They meet exactly when the reachable list contains a cycle.
    2. Maintain this invariant: After k steps the fast pointer has moved twice as far as the slow pointer modulo any cycle.
    3. Continue until every input item or reachable state has been resolved, then return the accumulated result.

    Python solution

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

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

class Solution:
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

    Why this is correct

    The proof follows the maintained state: After k steps the fast pointer has moved twice as far as the slow pointer modulo any cycle. Each iteration preserves that claim while permanently resolving at least one position, node, interval, or search state. When the loop or recursion ends, every candidate required by the problem has therefore been included or ruled out, so the returned value is correct.

    Complexity

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

    Edge cases

    An empty list or one node without a self-loop has no cycle.

    Tested reference code

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

    Download all 100 tested solutions

    Browse the searchable 100 LeetCode Python Solutions hub. Previous: 224. Basic Calculator · Next: 2. Add Two Numbers