Blind 75 Data Structures & Algorithms Problems with Python Solutions

Question 1

Contains Duplicate

Given an integer sequence, return whether any value appears at least twice; the sequence may be empty.

Accepted Answer

from collections.abc import Sequence

def contains_duplicate(nums: Sequence[int]) -> bool:
    return len(set(nums)) != len(nums)

Time: O(n) expected.

Auxiliary space: O(n).

Question 2

Valid Anagram

Given two lowercase English strings, return whether one is a permutation of the other with exactly the same character counts.

Accepted Answer

def is_anagram(first: str, second: str) -> bool:
    if len(first) != len(second):
        return False

counts = [0] * 26
    for character in first:
        counts[ord(character) - ord("a")] += 1
    for character in second:
        index = ord(character) - ord("a")
        counts[index] -= 1
        if counts[index] < 0:
            return False
    return True

Time: O(n + m).

Auxiliary space: O(1) because the alphabet is fixed.

Question 3

Two Sum

Given an integer array and a target, return the indices of the two distinct elements whose sum is the target; exactly one solution exists.

Accepted Answer

from collections.abc import Sequence

def two_sum(nums: Sequence[int], target: int) -> tuple[int, int]:
    index_by_value: dict[int, int] = {}
    for index, value in enumerate(nums):
        complement = target - value
        if complement in index_by_value:
            return index_by_value[complement], index
        index_by_value[value] = index
    raise ValueError("The input does not contain the promised pair")

Time: O(n) expected.

Auxiliary space: O(n).

Question 4

Valid Parentheses

Given a string containing only (), [], and {}, return whether every opening bracket is closed by the matching type in the correct order.

Accepted Answer

def has_valid_parentheses(text: str) -> bool:
    opening_for: dict[str, str] = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for character in text:
        if character in opening_for:
            if not stack or stack.pop() != opening_for[character]:
                return False
        else:
            stack.append(character)
    return not stack

Time: O(n).

Auxiliary space: O(n).

Question 5

Best Time to Buy and Sell Stock

Given a nonempty sequence of daily stock prices, return the greatest profit from buying once and selling on a later day, or 0 if no profitable transaction exists.

Accepted Answer

from collections.abc import Sequence

def max_stock_profit(prices: Sequence[int]) -> int:
    minimum_price = prices[0]
    best_profit = 0
    for index in range(1, len(prices)):
        price = prices[index]
        # minimum_price covers only earlier days, so this sale follows its buy.
        best_profit = max(best_profit, price - minimum_price)
        minimum_price = min(minimum_price, price)
    return best_profit

Time: O(n).

Auxiliary space: O(1).

Question 6

Reverse Linked List

Given the head of a singly linked list, return a list with the same values in reverse order without changing the input nodes. Assume ListNode(val, next) with val and next attributes.

Accepted Answer

from __future__ import annotations

from typing import Optional

def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    reversed_head: Optional[ListNode] = None
    current = head
    while current is not None:
        reversed_head = ListNode(current.val, reversed_head)
        current = current.next
    return reversed_head

Time: O(n).

Auxiliary space: O(1), excluding the returned list.

Question 7

Maximum Depth of Binary Tree

Given a binary-tree root, return the number of nodes on its longest root-to-leaf path; an empty tree has depth 0. Assume TreeNode with left and right attributes.

Accepted Answer

from __future__ import annotations

from typing import Optional

def max_depth(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0

deepest = 0
    stack: list[tuple[TreeNode, int]] = [(root, 1)]
    while stack:
        node, depth = stack.pop()
        deepest = max(deepest, depth)
        if node.left is not None:
            stack.append((node.left, depth + 1))
        if node.right is not None:
            stack.append((node.right, depth + 1))
    return deepest

Time: O(n).

Auxiliary space: O(h), where h is tree height.

Question 8

Number of 1 Bits

Given a nonnegative 32-bit integer, return the number of set bits in its binary representation.

Accepted Answer

def hamming_weight(value: int) -> int:
    count = 0
    while value:
        # value - 1 flips through the lowest 1, so AND clears exactly that bit.
        value &= value - 1
        count += 1
    return count

Time: O(k), where k is the number of set bits (at most 32).

Auxiliary space: O(1).

Question 9

Climbing Stairs

A staircase has n >= 1 steps and each move climbs one or two steps; return the number of distinct ways to reach step n.

Accepted Answer

def count_stair_ways(step_count: int) -> int:
    fibonacci_index = step_count + 1
    previous = 0
    current = 1
    # For the processed bit prefix k, this pair is (F(k), F(k + 1)).
    for bit_index in range(fibonacci_index.bit_length() - 1, -1, -1):
        # The doubling identities produce F(2k) and F(2k + 1).
        doubled_previous = previous * (2 * current - previous)
        doubled_current = previous * previous + current * current
        if (fibonacci_index >> bit_index) & 1:
            previous = doubled_current
            current = doubled_previous + doubled_current
        else:
            previous = doubled_previous
            current = doubled_current
    return previous

Time: O(log n) arithmetic operations.

Auxiliary space: O(1).

Question 10

Number of Islands

Given a nonempty rectangular grid of "1" land and "0" water cells, return the number of four-directionally connected land components without changing the grid.

Accepted Answer

from collections import deque
from collections.abc import Sequence

def count_islands(grid: Sequence[Sequence[str]]) -> int:
    row_count = len(grid)
    column_count = len(grid[0])
    visited: set[tuple[int, int]] = set()
    islands = 0

for row in range(row_count):
        for column in range(column_count):
            if grid[row][column] != "1" or (row, column) in visited:
                continue
            islands += 1
            visited.add((row, column))
            queue: deque[tuple[int, int]] = deque([(row, column)])
            while queue:
                current_row, current_column = queue.popleft()
                for row_delta, column_delta in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    next_row = current_row + row_delta
                    next_column = current_column + column_delta
                    if (
                        0 <= next_row < row_count
                        and 0 <= next_column < column_count
                        and grid[next_row][next_column] == "1"
                        and (next_row, next_column) not in visited
                    ):
                        visited.add((next_row, next_column))
                        queue.append((next_row, next_column))
    return islands

Time: O(rows * columns).

Auxiliary space: O(rows * columns).

Question 11

Product of Array Except Self

Given an integer array of length at least two, return an array whose element i is the product of every input element except nums[i], without division.

Accepted Answer

from collections.abc import Sequence

def product_except_self(nums: Sequence[int]) -> list[int]:
    # Store each left-prefix product in the output, then multiply its right suffix.
    products = [1] * len(nums)
    prefix = 1
    for index, value in enumerate(nums):
        products[index] = prefix
        prefix *= value

suffix = 1
    for index in range(len(nums) - 1, -1, -1):
        products[index] *= suffix
        suffix *= nums[index]
    return products

Time: O(n).

Auxiliary space: O(1), excluding the returned array.

Question 12

Valid Palindrome

Given an ASCII string, return whether its letters and digits read the same forward and backward after ignoring case and non-alphanumeric characters.

Accepted Answer

def is_palindrome(text: str) -> bool:
    left = 0
    right = len(text) - 1
    while left < right:
        while left < right and not text[left].isalnum():
            left += 1
        while left < right and not text[right].isalnum():
            right -= 1
        if text[left].lower() != text[right].lower():
            return False
        left += 1
        right -= 1
    return True

Time: O(n).

Auxiliary space: O(1).

Question 13

Merge Two Sorted Lists

Given two ascending singly linked lists, return a newly allocated ascending list containing all their values without changing either input. Assume ListNode(val, next).

Accepted Answer

from __future__ import annotations

from typing import Optional

def merge_two_lists(
    first: Optional[ListNode],
    second: Optional[ListNode],
) -> Optional[ListNode]:
    sentinel = ListNode(0, None)
    tail = sentinel
    left = first
    right = second

while left is not None or right is not None:
        if right is None or (left is not None and left.val <= right.val):
            tail.next = ListNode(left.val, None)
            left = left.next
        else:
            tail.next = ListNode(right.val, None)
            right = right.next
        tail = tail.next
    return sentinel.next

Time: O(n + m).

Auxiliary space: O(1), excluding the returned list.

Question 14

Same Tree

Given two binary-tree roots, return whether the trees have identical structure and equal values at corresponding nodes. Assume TreeNode with val, left, and right attributes.

Accepted Answer

from __future__ import annotations

from typing import Optional

def is_same_tree(first: Optional[TreeNode], second: Optional[TreeNode]) -> bool:
    stack: list[tuple[Optional[TreeNode], Optional[TreeNode]]] = [(first, second)]
    while stack:
        left, right = stack.pop()
        if left is None or right is None:
            if left is not right:
                return False
            continue
        if left.val != right.val:
            return False
        stack.append((left.left, right.left))
        stack.append((left.right, right.right))
    return True

Time: O(n), where n is the number of compared node positions.

Auxiliary space: O(h), where h is tree height.

Question 15

Missing Number

An array contains n distinct values drawn from 0 through n with one value missing; return the missing value.

Accepted Answer

from collections.abc import Sequence

def missing_number(nums: Sequence[int]) -> int:
    # XORing 0..n with all present values cancels every pair but the missing one.
    missing = len(nums)
    for index, value in enumerate(nums):
        missing ^= index ^ value
    return missing

Time: O(n).

Auxiliary space: O(1).

Question 16

Coin Change

Given positive coin denominations and a nonnegative amount, return the fewest coins needed to total the amount, or -1 when it is impossible; each denomination may be reused.

Accepted Answer

from collections.abc import Sequence

def minimum_coin_count(coins: Sequence[int], amount: int) -> int:
    unreachable = amount + 1
    best = [unreachable] * (amount + 1)
    best[0] = 0
    for subtotal in range(1, amount + 1):
        for coin in coins:
            if coin <= subtotal:
                # An optimal subtotal ending with coin extends its optimal remainder.
                best[subtotal] = min(best[subtotal], best[subtotal - coin] + 1)
    return -1 if best[amount] == unreachable else best[amount]

Time: O(amount * c), where c is the number of denominations.

Auxiliary space: O(amount).

Question 17

Clone Graph

Given a node in a connected undirected graph, return a deep copy of the graph, or None for an empty input. Assume Node(val) with a mutable neighbors list and identity-based hashing.

Accepted Answer

from __future__ import annotations

from collections import deque
from typing import Optional

def clone_graph(node: Optional[Node]) -> Optional[Node]:
    if node is None:
        return None

clone_by_node: dict[Node, Node] = {node: Node(node.val)}
    queue: deque[Node] = deque([node])
    while queue:
        original = queue.popleft()
        for neighbor in original.neighbors:
            if neighbor not in clone_by_node:
                clone_by_node[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            clone_by_node[original].neighbors.append(clone_by_node[neighbor])
    return clone_by_node[node]

Time: O(V + E).

Auxiliary space: O(V), excluding the cloned graph.

Question 18

Merge Intervals

Given closed intervals [start, end], return new sorted intervals covering the same points with every overlap merged; do not change the input.

Accepted Answer

from collections.abc import Sequence

def merge_intervals(intervals: Sequence[Sequence[int]]) -> list[list[int]]:
    if not intervals:
        return []
    ordered = sorted((interval[0], interval[1]) for interval in intervals)
    merged: list[list[int]] = [[ordered[0][0], ordered[0][1]]]
    for start, end in ordered[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

Time: O(n log n).

Auxiliary space: O(n).

Question 19

Longest Substring Without Repeating Characters

Given a string, return the maximum length of a contiguous substring containing no repeated character.

Accepted Answer

def longest_unique_substring_length(text: str) -> int:
    window: set[str] = set()
    left = 0
    best = 0
    for right, character in enumerate(text):
        while character in window:
            window.remove(text[left])
            left += 1
        window.add(character)
        best = max(best, right - left + 1)
    return best

Time: O(n) expected.

Auxiliary space: O(min(n, alphabet size)).

Question 20

Invert Binary Tree

Given a binary-tree root, return a newly allocated mirror image in which every node's left and right subtrees are exchanged; do not change the input tree. Assume TreeNode(val, left, right).

Accepted Answer

from __future__ import annotations

from typing import Optional

def inverted_tree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if root is None:
        return None

mirrored_root = TreeNode(root.val, None, None)
    stack: list[tuple[TreeNode, TreeNode]] = [(root, mirrored_root)]
    while stack:
        original, mirrored = stack.pop()
        if original.right is not None:
            mirrored_left = TreeNode(original.right.val, None, None)
            mirrored.left = mirrored_left
            stack.append((original.right, mirrored_left))
        if original.left is not None:
            mirrored_right = TreeNode(original.left.val, None, None)
            mirrored.right = mirrored_right
            stack.append((original.left, mirrored_right))
    return mirrored_root

Time: O(n).

Auxiliary space: O(h), excluding the returned tree, where h is tree height.

Question 21

Counting Bits

Given n >= 0, return an array where result[i] is the number of set bits in i for every integer from 0 through n.

Accepted Answer

def count_bits(limit: int) -> list[int]:
    counts = [0] * (limit + 1)
    for value in range(1, limit + 1):
        # Shifting drops the low bit; add it to the known smaller count.
        counts[value] = counts[value >> 1] + (value & 1)
    return counts

Time: O(n).

Auxiliary space: O(1), excluding the returned array.

Question 22

House Robber

Given nonnegative money in houses along one street, return the largest total obtainable without taking from adjacent houses.

Accepted Answer

from collections.abc import Sequence

def max_robbery(nums: Sequence[int]) -> int:
    # These are the best totals through the houses two back and one back.
    two_back = 0
    one_back = 0
    for amount in nums:
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

Time: O(n).

Auxiliary space: O(1).

Question 23

Course Schedule

Given num_courses courses labeled from 0 through num_courses - 1 and prerequisite pairs [course, prerequisite], return whether every course can be completed; a directed cycle makes completion impossible.

Accepted Answer

from collections import deque
from collections.abc import Sequence

def can_finish_courses(
    num_courses: int,
    prerequisites: Sequence[Sequence[int]],
) -> bool:
    next_courses: list[list[int]] = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, prerequisite in prerequisites:
        next_courses[prerequisite].append(course)
        indegree[course] += 1

# Only zero-indegree courses are currently available; a cycle leaves some
    # courses permanently unavailable, so completed will stay below the total.
    queue: deque[int] = deque(
        course for course, degree in enumerate(indegree) if degree == 0
    )
    completed = 0
    while queue:
        prerequisite = queue.popleft()
        completed += 1
        for course in next_courses[prerequisite]:
            indegree[course] -= 1
            if indegree[course] == 0:
                queue.append(course)
    return completed == num_courses

Time: O(V + E).

Auxiliary space: O(V + E).

Question 24

Insert Interval

Given disjoint closed intervals sorted by start and one new interval, return a new sorted disjoint list after inserting and merging all overlaps; do not change the inputs.

Accepted Answer

from collections.abc import Sequence

def insert_interval(
    intervals: Sequence[Sequence[int]],
    new_interval: Sequence[int],
) -> list[list[int]]:
    start = new_interval[0]
    end = new_interval[1]
    result: list[list[int]] = []
    index = 0

while index < len(intervals) and intervals[index][1] < start:
        result.append([intervals[index][0], intervals[index][1]])
        index += 1
    while index < len(intervals) and intervals[index][0] <= end:
        start = min(start, intervals[index][0])
        end = max(end, intervals[index][1])
        index += 1
    result.append([start, end])
    while index < len(intervals):
        result.append([intervals[index][0], intervals[index][1]])
        index += 1
    return result

Time: O(n).

Auxiliary space: O(1), excluding the returned list.

Question 25

Find Minimum in Rotated Sorted Array

A nonempty strictly increasing array of distinct integers may have been rotated at an unknown pivot; return its minimum value in O(log n) time.

Accepted Answer

from collections.abc import Sequence

def find_rotated_minimum(nums: Sequence[int]) -> int:
    left = 0
    right = len(nums) - 1
    while left < right:
        middle = (left + right) // 2
        # If middle exceeds right, the pivot is strictly to the right;
        # otherwise middle may be the minimum and stays in the interval.
        if nums[middle] > nums[right]:
            left = middle + 1
        else:
            right = middle
    return nums[left]

Time: O(log n).

Auxiliary space: O(1).

Question 26

Linked List Cycle

Given the head of a singly linked list, return whether following next pointers eventually revisits a node. Assume ListNode with a next attribute.

Accepted Answer

from __future__ import annotations

from typing import Optional

def has_cycle(head: Optional[ListNode]) -> bool:
    # Inside a cycle, the fast pointer gains one node per step on the slow one.
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Time: O(n).

Auxiliary space: O(1).

Question 27

Binary Tree Level Order Traversal

Given a binary-tree root, return its node values grouped by depth from the root, ordered left to right within each level. Assume TreeNode with val, left, and right attributes.

Accepted Answer

from __future__ import annotations

from collections import deque
from typing import Optional

def level_order(root: Optional[TreeNode]) -> list[list[int]]:
    if root is None:
        return []
    levels: list[list[int]] = []
    queue: deque[TreeNode] = deque([root])
    while queue:
        level: list[int] = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        levels.append(level)
    return levels

Time: O(n).

Auxiliary space: O(w), excluding the returned lists, where w is maximum tree width.

Question 28

Sum of Two Integers

Given two signed 32-bit integers whose sum fits in that range, return their sum without using + or -.

Accepted Answer

def add_without_arithmetic(first: int, second: int) -> int:
    mask = 0xFFFFFFFF
    sign_bit = 0x80000000
    left = first & mask
    right = second & mask
    while right:
        # XOR adds without carries; shifted AND carries into the next bit.
        sum_without_carries = (left ^ right) & mask
        carries = ((left & right) << 1) & mask
        left, right = sum_without_carries, carries
    # Restore a negative result from its unsigned 32-bit representation.
    return left if left < sign_bit else ~(left ^ mask)

Time: O(1) for 32-bit integers.

Auxiliary space: O(1).

Question 29

Unique Paths

In a rows-by-columns grid with positive dimensions, a robot starts at the top-left and moves only right or down; return the number of paths to the bottom-right.

Accepted Answer

def unique_paths(rows: int, columns: int) -> int:
    total_moves = rows + columns - 2
    chosen_moves = min(rows - 1, columns - 1)
    paths = 1
    for move in range(1, chosen_moves + 1):
        # This exact binomial recurrence builds C(total_moves, chosen_moves).
        paths = paths * (total_moves - chosen_moves + move) // move
    return paths

Time: O(min(rows, columns)) arithmetic operations.

Auxiliary space: O(1).

Question 30

Graph Valid Tree

Given n >= 1 vertices labeled from 0 through n - 1 and undirected edges, return whether the graph is one connected acyclic tree.

Accepted Answer

from collections import deque
from collections.abc import Sequence

def is_valid_tree(node_count: int, edges: Sequence[Sequence[int]]) -> bool:
    # An undirected graph is a tree exactly when it has n - 1 edges and is connected.
    if len(edges) != node_count - 1:
        return False
    neighbors: list[list[int]] = [[] for _ in range(node_count)]
    for first, second in edges:
        neighbors[first].append(second)
        neighbors[second].append(first)

visited = {0}
    queue: deque[int] = deque([0])
    while queue:
        node = queue.popleft()
        for neighbor in neighbors[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return len(visited) == node_count

Time: O(V + E).

Auxiliary space: O(V + E).

Question 31

Container With Most Water

Given at least two nonnegative vertical-line heights at unit-spaced indices, choose two lines and return the greatest water area they can contain with the x-axis.

Accepted Answer

from collections.abc import Sequence

def max_container_area(heights: Sequence[int]) -> int:
    left = 0
    right = len(heights) - 1
    best = 0
    while left < right:
        best = max(best, (right - left) * min(heights[left], heights[right]))
        # With a smaller width, keeping the shorter line cannot improve area.
        if heights[left] <= heights[right]:
            left += 1
        else:
            right -= 1
    return best

Time: O(n).

Auxiliary space: O(1).

Question 32

Group Anagrams

Given lowercase English words, group together words that contain the same letters with the same multiplicities; group order is unrestricted.

Accepted Answer

from collections.abc import Sequence

def group_anagrams(words: Sequence[str]) -> list[list[str]]:
    groups: dict[tuple[int, ...], list[str]] = {}
    for word in words:
        counts = [0] * 26
        for character in word:
            counts[ord(character) - ord("a")] += 1
        key = tuple(counts)
        groups.setdefault(key, []).append(word)
    return list(groups.values())

Time: O(n + S), for n words containing S total characters.

Auxiliary space: O(n + S), including the returned groups.

Question 33

Remove Nth Node From End of List

Given a singly linked list and a valid one-based position n from its end, return a newly allocated copy without that node; do not change the input. Assume ListNode(val, next).

Accepted Answer

from __future__ import annotations

from typing import Optional

def remove_nth_from_end(
    head: Optional[ListNode],
    position_from_end: int,
) -> Optional[ListNode]:
    length = 0
    current = head
    while current is not None:
        length += 1
        current = current.next
    removed_index = length - position_from_end

sentinel = ListNode(0, None)
    tail = sentinel
    current = head
    index = 0
    while current is not None:
        if index != removed_index:
            tail.next = ListNode(current.val, None)
            tail = tail.next
        current = current.next
        index += 1
    return sentinel.next

Time: O(n).

Auxiliary space: O(1), excluding the returned list.

Question 34

Validate Binary Search Tree

Given a binary tree, return whether every node is strictly greater than all values in its left subtree and strictly less than all values in its right subtree. Assume TreeNode with integer val, left, and right.

Accepted Answer

from __future__ import annotations

from typing import Optional

def is_valid_bst(root: Optional[TreeNode]) -> bool:
    if root is None:
        return True

stack: list[tuple[TreeNode, Optional[int], Optional[int]]] = [
        (root, None, None)
    ]
    while stack:
        node, lower, upper = stack.pop()
        if (lower is not None and node.val <= lower) or (
            upper is not None and node.val >= upper
        ):
            return False
        if node.left is not None:
            stack.append((node.left, lower, node.val))
        if node.right is not None:
            stack.append((node.right, node.val, upper))
    return True

Time: O(n).

Auxiliary space: O(h), where h is tree height.

Question 35

Reverse Bits

Given an unsigned 32-bit integer, return the integer represented by its bits in reverse order.

Accepted Answer

def reverse_bits(value: int) -> int: reversed_value = 0 for _ in range(32): reversed_value = (reversed_value << 1) | (value & 1) value >>= 1 return reversed_value Time: O(1) for 32 bits. Auxiliary space: O(1).

Question 36

Word Break

Given a string and reusable nonempty dictionary words, return whether the entire string can be segmented into a sequence of dictionary words.

Accepted Answer

from collections.abc import Collection

def can_segment(text: str, dictionary: Collection[str]) -> bool:
    if not text:
        return True
    if not dictionary:
        return False

children: list[dict[str, int]] = [{}]
    terminal_nodes: set[int] = set()
    maximum_word_length = 0
    for word in dictionary:
        node_index = 0
        maximum_word_length = max(maximum_word_length, len(word))
        for character in word:
            child_index = children[node_index].get(character)
            if child_index is None:
                child_index = len(children)
                children[node_index][character] = child_index
                children.append({})
            node_index = child_index
        terminal_nodes.add(node_index)

# reachable[i] means text[:i] is segmentable; trie walks from each true
    # boundary share dictionary prefixes and mark every terminal boundary.
    reachable = [False] * (len(text) + 1)
    reachable[0] = True
    for start in range(len(text)):
        if not reachable[start]:
            continue
        node_index = 0
        end_limit = min(len(text), start + maximum_word_length)
        for end in range(start, end_limit):
            child_index = children[node_index].get(text[end])
            if child_index is None:
                break
            node_index = child_index
            if node_index in terminal_nodes:
                reachable[end + 1] = True
                if end + 1 == len(text):
                    return True
    return False

Time: O(D + n * L) expected, where D is the total number of dictionary characters and L is the longest word length.

Auxiliary space: O(D + n).

Question 37

Number of Connected Components in an Undirected Graph

Given n vertices labeled from 0 through n - 1 and undirected edges, return the number of connected components, including isolated vertices.

Accepted Answer

from collections import deque
from collections.abc import Sequence

def count_components(node_count: int, edges: Sequence[Sequence[int]]) -> int:
    neighbors: list[list[int]] = [[] for _ in range(node_count)]
    for first, second in edges:
        neighbors[first].append(second)
        neighbors[second].append(first)

visited: set[int] = set()
    component_count = 0
    for start in range(node_count):
        if start in visited:
            continue
        component_count += 1
        visited.add(start)
        queue: deque[int] = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in neighbors[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
    return component_count

Time: O(V + E).

Auxiliary space: O(V + E).

Question 38

Non-overlapping Intervals

Given intervals [start, end] with start < end, under the convention that one may start when another ends, return the minimum number to remove so the remainder do not overlap; do not change the input.

Accepted Answer

from collections.abc import Sequence

def minimum_interval_removals(intervals: Sequence[Sequence[int]]) -> int:
    # Keeping the earliest-finishing compatible interval leaves maximal room later.
    ordered = sorted(intervals, key=lambda interval: interval[1])
    removals = 0
    previous_end: int | None = None
    for start, end in ordered:
        if previous_end is not None and start < previous_end:
            removals += 1
        else:
            previous_end = end
    return removals

Time: O(n log n).

Auxiliary space: O(n) for the sorted copy.

Question 39

Search in Rotated Sorted Array

A strictly increasing array of distinct integers may have been rotated at an unknown pivot; return the target's index, or -1 if absent, in O(log n) time.

Accepted Answer

from collections.abc import Sequence

def search_rotated(nums: Sequence[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:
        middle = (left + right) // 2
        if nums[middle] == target:
            return middle
        # Distinct values make at least one half sorted; keep it only if it
        # contains the target, otherwise search the opposite half.
        if nums[left] <= nums[middle]:
            if nums[left] <= target < nums[middle]:
                right = middle - 1
            else:
                left = middle + 1
        elif nums[middle] < target <= nums[right]:
            left = middle + 1
        else:
            right = middle - 1
    return -1

Time: O(log n).

Auxiliary space: O(1).

Question 40

Longest Repeating Character Replacement

Given an uppercase English string and k >= 0, change at most k characters and return the greatest length of a substring that can be made all one character.

Accepted Answer

def longest_repeating_after_replacements(text: str, replacements: int) -> int:
    counts: dict[str, int] = {}
    left = 0
    highest_count = 0
    best = 0
    for right, character in enumerate(text):
        counts[character] = counts.get(character, 0) + 1
        # This maximum never decreases; if stale, it only delays shrinking to
        # a length that was already feasible, so it cannot inflate the answer.
        highest_count = max(highest_count, counts[character])
        while right - left + 1 - highest_count > replacements:
            counts[text[left]] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Time: O(n).

Auxiliary space: O(1) because the alphabet is fixed.

Question 41

Reorder List

Given a singly linked list L0 -> L1 -> ... -> Ln, modify it in place to L0 -> Ln -> L1 -> Ln-1 -> ... without changing node values. Assume ListNode with a mutable next attribute.

Accepted Answer

from __future__ import annotations

from typing import Optional

def reorder_list(head: Optional[ListNode]) -> None:
    if head is None or head.next is None:
        return

slow = head
    fast = head
    while fast.next is not None and fast.next.next is not None:
        slow = slow.next
        fast = fast.next.next

second = slow.next
    slow.next = None
    reversed_head: Optional[ListNode] = None
    while second is not None:
        next_node = second.next
        second.next = reversed_head
        reversed_head = second
        second = next_node

first = head
    second = reversed_head
    while second is not None:
        next_first = first.next
        next_second = second.next
        first.next = second
        second.next = next_first
        first = next_first
        second = next_second

Time: O(n).

Auxiliary space: O(1).

Question 42

Kth Smallest Element in a BST

Given a binary search tree and valid one-based k, return the kth smallest node value. Assume TreeNode with val, left, and right attributes.

Accepted Answer

from __future__ import annotations

def kth_smallest(root: TreeNode, k: int) -> int:
    # Inorder visits BST values in ascending order; the stack simulates recursion.
    stack: list[TreeNode] = []
    current: TreeNode | None = root
    remaining = k
    while current is not None or stack:
        while current is not None:
            stack.append(current)
            current = current.left
        current = stack.pop()
        remaining -= 1
        if remaining == 0:
            return current.val
        current = current.right
    raise ValueError("k exceeds the number of tree nodes")

Time: O(h + k).

Auxiliary space: O(h).

Question 43

Longest Consecutive Sequence

Given an unsorted integer array, return the length of the longest set of values that form consecutive integers, in expected linear time.

Accepted Answer

from collections.abc import Sequence

def longest_consecutive(nums: Sequence[int]) -> int:
    values = set(nums)
    best = 0
    for value in values:
        # Start only at a run's first value, so every value is scanned once.
        if value - 1 in values:
            continue
        length = 1
        while value + length in values:
            length += 1
        best = max(best, length)
    return best

Time: O(n) expected.

Auxiliary space: O(n).

Question 44

Maximum Subarray

Given a nonempty integer array, return the greatest sum of any contiguous nonempty subarray.

Accepted Answer

from collections.abc import Sequence

def maximum_subarray_sum(nums: Sequence[int]) -> int:
    # The best subarray ending here either starts here or extends the prior one.
    best_ending_here = nums[0]
    best = nums[0]
    for index in range(1, len(nums)):
        value = nums[index]
        best_ending_here = max(value, best_ending_here + value)
        best = max(best, best_ending_here)
    return best

Time: O(n).

Auxiliary space: O(1).

Question 45

House Robber II

Given nonnegative money in houses arranged in a circle, return the largest total obtainable without taking from adjacent houses; the first and last houses are adjacent.

Accepted Answer

from collections.abc import Sequence

def max_circular_robbery(nums: Sequence[int]) -> int:
    def rob_range(start: int, end: int) -> int:
        # Best totals through the positions two back and one back.
        two_back = 0
        one_back = 0
        for index in range(start, end):
            two_back, one_back = one_back, max(one_back, two_back + nums[index])
        return one_back

if len(nums) == 1:
        return nums[0]
    # Any valid circular choice excludes either the first or the last house.
    return max(rob_range(0, len(nums) - 1), rob_range(1, len(nums)))

Time: O(n).

Auxiliary space: O(1).

Question 46

Pacific Atlantic Water Flow

Given a nonempty rectangular height grid, return [row, column] for every cell from which water can flow four-directionally to both the top/left ocean borders and the bottom/right ocean borders, moving only to cells of equal or lower height; any output order is accepted and the grid must remain unchanged.

Accepted Answer

from collections import deque
from collections.abc import Iterable, Sequence


def pacific_atlantic(heights: Sequence[Sequence[int]]) -> list[list[int]]:
    rows = len(heights)
    columns = len(heights[0])

    def reachable_from(starts: Iterable[tuple[int, int]]) -> set[tuple[int, int]]:
        # Reverse water flow from an ocean, moving only to equal or higher cells.
        reached = set(starts)
        queue: deque[tuple[int, int]] = deque(reached)
        while queue:
            row, column = queue.popleft()
            for row_delta, column_delta in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                next_row = row + row_delta
                next_column = column + column_delta
                if (
                    0 <= next_row < rows
                    and 0 <= next_column < columns
                    and (next_row, next_column) not in reached
                    and heights[next_row][next_column] >= heights[row][column]
                ):
                    reached.add((next_row, next_column))
                    queue.append((next_row, next_column))
        return reached

    pacific = reachable_from(
        [(row, 0) for row in range(rows)]
        + [(0, column) for column in range(columns)]
    )
    atlantic = reachable_from(
        [(row, columns - 1) for row in range(rows)]
        + [(rows - 1, column) for column in range(columns)]
    )
    return [
        [row, column]
        for row in range(rows)
        for column in range(columns)
        if (row, column) in pacific and (row, column) in atlantic
    ]

Time: O(rows * columns).

Auxiliary space: O(rows * columns).

Question 47

Meeting Rooms

Given meeting half-open intervals [start, end) with start < end, return whether one person can attend all meetings without any overlap; do not change the input.

Accepted Answer

from collections.abc import Sequence

def can_attend_all_meetings(intervals: Sequence[Sequence[int]]) -> bool:
    ordered = sorted(intervals, key=lambda interval: interval[0])
    return all(
        ordered[index - 1][1] <= ordered[index][0]
        for index in range(1, len(ordered))
    )

Time: O(n log n).

Auxiliary space: O(n) for the sorted copy.

Question 48

3Sum

Given an integer array, return every distinct value triplet whose sum is zero; result order is unrestricted and the input must remain unchanged.

Accepted Answer

from collections.abc import Sequence


def three_sum(nums: Sequence[int]) -> list[list[int]]:
    values = sorted(nums)
    triplets: list[list[int]] = []
    for index, first in enumerate(values):
        if index > 0 and first == values[index - 1]:
            continue
        left = index + 1
        right = len(values) - 1
        while left < right:
            total = first + values[left] + values[right]
            # Sorting makes each pointer move monotonic toward the needed sum.
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                triplets.append([first, values[left], values[right]])
                left += 1
                right -= 1
                while left < right and values[left] == values[left - 1]:
                    left += 1
    return triplets

Time: O(n^2).

Auxiliary space: O(n), excluding the returned triplets.

Question 49

Encode and Decode Strings

Design reversible functions that encode any list of strings, including empty strings and delimiter characters, into one string and decode it exactly.

Accepted Answer

from collections.abc import Sequence

def encode_strings(values: Sequence[str]) -> str:
    parts: list[str] = []
    for value in values:
        parts.append(f"{len(value)}#{value}")
    return "".join(parts)

def decode_strings(encoded: str) -> list[str]:
    values: list[str] = []
    index = 0
    while index < len(encoded):
        separator = encoded.index("#", index)
        length = int(encoded[index:separator])
        start = separator + 1
        end = start + length
        values.append(encoded[start:end])
        index = end
    return values

Time: O(S), where S is the encoded character count.

Auxiliary space: O(S) for construction and returned values.

Question 50

Implement Trie (Prefix Tree)

Implement a trie for nonempty lowercase English words with insert(word), search(word), and starts_with(prefix); search matches only a complete inserted word, while starts_with reports whether any inserted word begins with the nonempty prefix.

Accepted Answer

from __future__ import annotations

class TrieNode:
    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.is_word = False

class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()

def insert(self, word: str) -> None:
        node = self.root
        for character in word:
            if character not in node.children:
                node.children[character] = TrieNode()
            node = node.children[character]
        node.is_word = True

def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_word

def starts_with(self, prefix: str) -> bool:
        return self._find(prefix) is not None

def _find(self, text: str) -> TrieNode | None:
        node = self.root
        for character in text:
            if character not in node.children:
                return None
            node = node.children[character]
        return node

Time: O(L) per operation, where L is the word or prefix length.

Auxiliary space: O(T) total for T inserted characters.

Question 51

Subtree of Another Tree

Given roots root and sub_root, return whether some subtree of root has exactly the same structure and values as sub_root; an empty sub_root matches. Assume TreeNode with integer val, left, and right.

Accepted Answer

from __future__ import annotations

from typing import Optional

def is_subtree(root: Optional[TreeNode], sub_root: Optional[TreeNode]) -> bool:
    if sub_root is None:
        return True

# Both trees share this table, so equal (value, left ID, right ID)
    # signatures receive the same exact structural identifier.
    identifier_by_signature: dict[tuple[int, int, int], int] = {}

def identify_tree(
        tree: Optional[TreeNode],
        target_identifier: Optional[int],
    ) -> tuple[int, bool]:
        if tree is None:
            return 0, target_identifier == 0

identifier_by_node: dict[int, int] = {}
        stack: list[tuple[TreeNode, bool]] = [(tree, False)]
        found = False
        while stack:
            node, expanded = stack.pop()
            if not expanded:
                stack.append((node, True))
                if node.right is not None:
                    stack.append((node.right, False))
                if node.left is not None:
                    stack.append((node.left, False))
                continue

left_identifier = (
                0 if node.left is None else identifier_by_node[id(node.left)]
            )
            right_identifier = (
                0 if node.right is None else identifier_by_node[id(node.right)]
            )
            signature = (node.val, left_identifier, right_identifier)
            identifier = identifier_by_signature.get(signature)
            if identifier is None:
                identifier = len(identifier_by_signature) + 1
                identifier_by_signature[signature] = identifier
            identifier_by_node[id(node)] = identifier
            if identifier == target_identifier:
                found = True

return identifier_by_node[id(tree)], found

target_identifier, _ = identify_tree(sub_root, None)
    _, found = identify_tree(root, target_identifier)
    return found

Time: O(n + m) expected for trees with n and m nodes.

Auxiliary space: O(n + m).

Question 52

Maximum Product Subarray

Given a nonempty integer array, return the greatest product of any contiguous nonempty subarray.

Accepted Answer

from collections.abc import Sequence

def maximum_subarray_product(nums: Sequence[int]) -> int:
    # Track both extremes because a negative value can turn the minimum into maximum.
    maximum_ending = nums[0]
    minimum_ending = nums[0]
    best = nums[0]
    for index in range(1, len(nums)):
        value = nums[index]
        candidates = (value, value * maximum_ending, value * minimum_ending)
        maximum_ending = max(candidates)
        minimum_ending = min(candidates)
        best = max(best, maximum_ending)
    return best

Time: O(n).

Auxiliary space: O(1).

Question 53

Decode Ways

Digits map 1 through 26 to letters; given a nonempty digit string, return the number of complete decodings, treating a leading zero or invalid zero placement as undecodable.

Accepted Answer

def count_decodings(digits: str) -> int:
    # These count decodings through the prefixes ending two back and one back.
    two_back = 1
    one_back = 0 if digits[0] == "0" else 1
    for index in range(1, len(digits)):
        current = 0
        if digits[index] != "0":
            current += one_back
        if 10 <= int(digits[index - 1 : index + 1]) <= 26:
            current += two_back
        two_back, one_back = one_back, current
    return one_back

Time: O(n).

Auxiliary space: O(1).

Question 54

Alien Dictionary

Given unique words sorted by an unknown alphabet, return any character order consistent with the list, or an empty string if the ordering is invalid or cyclic; all characters in the words must appear.

Accepted Answer

from collections import deque
from collections.abc import Sequence

def alien_order(words: Sequence[str]) -> str:
    neighbors: dict[str, set[str]] = {
        character: set() for word in words for character in word
    }
    indegree: dict[str, int] = {character: 0 for character in neighbors}

for word_index in range(1, len(words)):
        first = words[word_index - 1]
        second = words[word_index]
        common_length = min(len(first), len(second))
        # Only the first mismatch determines precedence; with no mismatch, a
        # longer word before its own prefix makes the ordering impossible.
        for character_index in range(common_length):
            left = first[character_index]
            right = second[character_index]
            if left == right:
                continue
            if right not in neighbors[left]:
                neighbors[left].add(right)
                indegree[right] += 1
            break
        else:
            if len(first) > len(second):
                return ""

queue: deque[str] = deque(
        character for character in neighbors if indegree[character] == 0
    )
    order: list[str] = []
    while queue:
        character = queue.popleft()
        order.append(character)
        for neighbor in neighbors[character]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return "".join(order) if len(order) == len(neighbors) else ""

Time: O(C + E), where C is total input characters and E is precedence edges.

Auxiliary space: O(U + E), where U is the number of distinct characters.

Question 55

Meeting Rooms II

Given meeting half-open intervals [start, end) with start < end, return the minimum number of rooms needed so every meeting can occur.

Accepted Answer

from collections.abc import Sequence

def minimum_meeting_rooms(intervals: Sequence[Sequence[int]]) -> int:
    if not intervals:
        return 0
    starts = sorted(interval[0] for interval in intervals)
    ends = sorted(interval[1] for interval in intervals)
    start_index = 0
    end_index = 0
    rooms_in_use = 0
    best = 0

while start_index < len(starts):
        # On equal times, process the end first because intervals are half-open.
        if starts[start_index] < ends[end_index]:
            rooms_in_use += 1
            best = max(best, rooms_in_use)
            start_index += 1
        else:
            rooms_in_use -= 1
            end_index += 1
    return best

Time: O(n log n).

Auxiliary space: O(n).

Question 56

Set Matrix Zeroes

Given a nonempty mutable matrix, set an entire row and column to zero whenever any original cell in either is zero; modify the matrix in place with constant extra space.

Accepted Answer

def set_matrix_zeroes(matrix: list[list[int]]) -> None:
    rows = len(matrix)
    columns = len(matrix[0])
    # Save the first row/column state before reusing them as marker storage.
    first_row_has_zero = any(matrix[0][column] == 0 for column in range(columns))
    first_column_has_zero = any(matrix[row][0] == 0 for row in range(rows))

for row in range(1, rows):
        for column in range(1, columns):
            if matrix[row][column] == 0:
                matrix[row][0] = 0
                matrix[0][column] = 0

for row in range(1, rows):
        for column in range(1, columns):
            if matrix[row][0] == 0 or matrix[0][column] == 0:
                matrix[row][column] = 0

if first_row_has_zero:
        for column in range(columns):
            matrix[0][column] = 0
    if first_column_has_zero:
        for row in range(rows):
            matrix[row][0] = 0

Time: O(rows * columns).

Auxiliary space: O(1).

Question 57

Longest Palindromic Substring

Given a nonempty string, return one longest contiguous substring that reads the same forward and backward.

Accepted Answer

def longest_palindrome(text: str) -> str: length = len(text) # odd_radii[c] = r means text[c - r + 1:c + r] is a palindrome. # [left, right] is the rightmost palindrome window found so far. odd_radii = [0] * length left = 0 right = -1 for center in range(length): # Reuse the mirror's radius inside the window, capped at right. radius = ( 1 if center > right else min(odd_radii[left + right - center], right - center + 1) ) while ( center - radius >= 0 and center + radius < length and text[center - radius] == text[center + radius] ): radius += 1 odd_radii[center] = radius if center + radius - 1 > right: left = center - radius + 1 right = center + radius - 1 # even_radii[c] = r means text[c - r:c + r] is a palindrome. # The maintained window and capped mirror radius have the same meaning. even_radii = [0] * length left = 0 right = -1 for center in range(length): radius = ( 0 if center > right else min(even_radii[left + right - center + 1], right - center + 1) ) while ( center - radius - 1 >= 0 and center + radius < length and text[center - radius - 1] == text[center + radius] ): radius += 1 even_radii[center] = radius if center + radius - 1 > right: left = center - radius right = center + radius - 1 best_start = 0 best_length = 1 for center in range(length): odd_length = 2 * odd_radii[center] - 1 if odd_length > best_length: best_start = center - odd_radii[center] + 1 best_length = odd_length even_length = 2 * even_radii[center] if even_length > best_length: best_start = center - even_radii[center] best_length = even_length return text[best_start : best_start + best_length] Time: O(n). Auxiliary space: O(n), excluding the returned substring.

Question 58

Merge K Sorted Lists

Given k ascending singly linked lists, return a newly allocated ascending list containing every value without changing the inputs. Assume ListNode(val, next).

Accepted Answer

from __future__ import annotations

import heapq
from collections.abc import Sequence
from typing import Optional

def merge_k_lists(lists: Sequence[Optional[ListNode]]) -> Optional[ListNode]:
    # A list index breaks equal-value ties without comparing ListNode objects.
    heap: list[tuple[int, int, ListNode]] = []
    for list_index, node in enumerate(lists):
        if node is not None:
            heapq.heappush(heap, (node.val, list_index, node))

sentinel = ListNode(0, None)
    tail = sentinel
    while heap:
        value, list_index, node = heapq.heappop(heap)
        tail.next = ListNode(value, None)
        tail = tail.next
        if node.next is not None:
            heapq.heappush(heap, (node.next.val, list_index, node.next))
    return sentinel.next

Time: O(k + N log(k + 1)) for k input lists and N total nodes.

Auxiliary space: O(k), excluding the returned list.

Question 59

Word Search

Given a character grid with 1 to 6 rows and 1 to 6 columns and a word of length 1 to 15, return whether the word can be traced through horizontally or vertically adjacent cells without reusing a cell; do not change the board.

Accepted Answer

from collections.abc import Sequence


def insert_interval(
    intervals: Sequence[Sequence[int]],
    new_interval: Sequence[int],
) -> list[list[int]]:
    start = new_interval[0]
    end = new_interval[1]
    result: list[list[int]] = []
    index = 0

    while index < len(intervals) and intervals[index][1] < start:
        result.append([intervals[index][0], intervals[index][1]])
        index += 1
    while index < len(intervals) and intervals[index][0] <= end:
        start = min(start, intervals[index][0])
        end = max(end, intervals[index][1])
        index += 1
    result.append([start, end])
    while index < len(intervals):
        result.append([intervals[index][0], intervals[index][1]])
        index += 1
    return result

Time: O(n).

Auxiliary space: O(1), excluding the returned list.

Question 60

Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversals of a binary tree with distinct values, reconstruct and return the tree. Assume TreeNode(val, left, right).

Accepted Answer

from __future__ import annotations

from collections.abc import Sequence
from typing import Optional

def build_tree(
    preorder: Sequence[int],
    inorder: Sequence[int],
) -> Optional[TreeNode]:
    if not preorder:
        return None

root = TreeNode(preorder[0], None, None)
    # The stack is the unfinished root-to-node path; inorder_index marks
    # the next node whose left subtree has been completed.
    stack: list[TreeNode] = [root]
    inorder_index = 0
    for preorder_index in range(1, len(preorder)):
        value = preorder[preorder_index]
        node = stack[-1]
        if node.val != inorder[inorder_index]:
            child = TreeNode(value, None, None)
            node.left = child
            stack.append(child)
            continue

# Pop every completed ancestor, then attach the next value to the
        # right of the last ancestor completed by inorder traversal.
        while stack and stack[-1].val == inorder[inorder_index]:
            node = stack.pop()
            inorder_index += 1
        child = TreeNode(value, None, None)
        node.right = child
        stack.append(child)
    return root

Time: O(n).

Auxiliary space: O(h), excluding the returned tree, where h is tree height.

Question 61

Longest Increasing Subsequence

Given an integer array, return the length of its longest strictly increasing subsequence; selected values need not be contiguous.

Accepted Answer

from bisect import bisect_left
from collections.abc import Sequence

def longest_increasing_subsequence_length(nums: Sequence[int]) -> int:
    # smallest_tail[i] is the least tail of any increasing subsequence of
    # length i + 1; replacing it preserves length and improves extendability.
    smallest_tail: list[int] = []
    for value in nums:
        index = bisect_left(smallest_tail, value)
        if index == len(smallest_tail):
            smallest_tail.append(value)
        else:
            smallest_tail[index] = value
    return len(smallest_tail)

Time: O(n log n).

Auxiliary space: O(n).

Question 62

Jump Game

Each value in a nonempty array of nonnegative integers is the maximum forward jump from that index; return whether the last index is reachable from the first.

Accepted Answer

from collections.abc import Sequence

def can_reach_end(nums: Sequence[int]) -> bool:
    # Every index through farthest is reachable, so only those jumps may extend it.
    farthest = 0
    for index, jump in enumerate(nums):
        if index > farthest:
            return False
        farthest = max(farthest, index + jump)
        if farthest >= len(nums) - 1:
            return True
    return True

Time: O(n).

Auxiliary space: O(1).

Question 63

Design Add and Search Words Data Structure

Implement a word dictionary with add_word(word) and search(pattern), where every added word and search pattern has length 1 to 25 and each dot matches any one lowercase letter.

Accepted Answer

from __future__ import annotations

class WordNode:
    def __init__(self) -> None:
        self.children: dict[str, WordNode] = {}
        self.is_word = False

class WordDictionary:
    def __init__(self) -> None:
        self.root = WordNode()

def add_word(self, word: str) -> None:
        node = self.root
        for character in word:
            if character not in node.children:
                node.children[character] = WordNode()
            node = node.children[character]
        node.is_word = True

def search(self, pattern: str) -> bool:
        def matches(index: int, node: WordNode) -> bool:
            if index == len(pattern):
                return node.is_word
            character = pattern[index]
            if character == ".":
                return any(matches(index + 1, child) for child in node.children.values())
            child = node.children.get(character)
            return child is not None and matches(index + 1, child)

return matches(0, self.root)

Time: add_word is O(L); search is O(L) without dots and O(26^L) in the worst all-dot case.

Auxiliary space: O(T + L), for T stored characters and the search stack.

Question 64

Spiral Matrix

Given a nonempty rectangular matrix, return all values in clockwise spiral order without changing the matrix.

Accepted Answer

from collections.abc import Sequence

def spiral_order(matrix: Sequence[Sequence[int]]) -> list[int]:
    top = 0
    bottom = len(matrix) - 1
    left = 0
    right = len(matrix[0]) - 1
    result: list[int] = []

while top <= bottom and left <= right:
        for column in range(left, right + 1):
            result.append(matrix[top][column])
        top += 1
        for row in range(top, bottom + 1):
            result.append(matrix[row][right])
        right -= 1
        if top <= bottom:
            for column in range(right, left - 1, -1):
                result.append(matrix[bottom][column])
            bottom -= 1
        if left <= right:
            for row in range(bottom, top - 1, -1):
                result.append(matrix[row][left])
            left += 1
    return result

Time: O(rows * columns).

Auxiliary space: O(1), excluding the returned list.

About this deck

Cards in this deck

Card 1

Card 2

Card 3

Card 4

Card 5

Card 6

Card 7

Card 8

Card 9

Card 10

Card 11

Card 12

Card 13

Card 14

Card 15

Card 16

Card 17

Card 18

Card 19

Card 20

Card 21

Card 22

Card 23

Card 24

Card 25

Card 26

Card 27

Card 28

Card 29

Card 30

Card 31

Card 32

Card 33

Card 34

Card 35

Card 36

Card 37

Card 38

Card 39

Card 40

Card 41

Card 42

Card 43

Card 44

Card 45

Card 46

Card 47

Card 48

Card 49

Card 50

Card 51

Card 52

Card 53

Card 54

Card 55

Card 56

Card 57

Card 58

Card 59

Card 60

Card 61

Card 62

Card 63

Card 64

Card 65

Card 66

Card 67

Card 68

Card 69

Card 70

Card 71

Card 72

Card 73

Card 74

Card 75

Blind 75 Data Structures & Algorithms Problems with Python Solutions