# Blind 75 Data Structures & Algorithms Problems with Python Solutions

![Abstract arrays, linked nodes, a binary tree, a graph, and a heap connected by glowing paths on a dark background\.](<https://d2bq3tvt7zf1kf.cloudfront.net/catalog/media/23e5bbad637bda6b4df1ae3d0327c1201559bad61a6c4636e7cf8d53b76d851c>)

Review all 75 Blind 75 coding interview problems with original front\-side descriptions, interview\-readable Python 3 solutions, and time and space complexity\.

作成者 [Flashcards Open Source App](<https://nibomo.com/ja/catalog/authors/flashcards-open-source-app/>)

[このデッキを無料で学習](<https://app.nibomo.com/catalog/import/500bb8d1-70a5-5386-86ad-19440d1266b8>)

Nibomo が開き、すぐに学習を始められます。

## デッキの詳細

- カード: 75枚のカード
- バージョン: 2
- 公開日: 2026年8月16日
- 最終更新: 2026年9月10日
- ライセンス: CC0\-1\.0
- 対象ユーザーの言語: [en](<https://nibomo.com/ja/catalog/languages/en/>)
- 科目: Computer science
- タグ: blind\-75\-python

## このデッキについて

Review the canonical Blind 75 coding-interview problems and retrieve concise optimal Python solutions. Each card supports one useful retrieval direction: canonical title plus an original concise problem restatement on the front → exactly one interview-readable Python 3 solution and verified time and auxiliary-space complexity on the back. Reverse solution → title cards are excluded because that is not a useful retrieval direction.

This is the original Blind 75 inventory—not LeetCode 75 or a variable Grind 75 result—organized as one deterministic progressive sequence. Foundations come first, then arrays, strings, linked lists, trees, graphs, heaps, intervals, bit manipulation, and dynamic programming are interleaved. Near-identical patterns are deliberately separated so the preceding solution does not reveal the next.

Exact sequence:

1. Contains Duplicate
2. Valid Anagram
3. Two Sum
4. Valid Parentheses
5. Best Time to Buy and Sell Stock
6. Reverse Linked List
7. Maximum Depth of Binary Tree
8. Number of 1 Bits
9. Climbing Stairs
10. Number of Islands
11. Product of Array Except Self
12. Valid Palindrome
13. Merge Two Sorted Lists
14. Same Tree
15. Missing Number
16. Coin Change
17. Clone Graph
18. Merge Intervals
19. Longest Substring Without Repeating Characters
20. Invert Binary Tree
21. Counting Bits
22. House Robber
23. Course Schedule
24. Insert Interval
25. Find Minimum in Rotated Sorted Array
26. Linked List Cycle
27. Binary Tree Level Order Traversal
28. Sum of Two Integers
29. Unique Paths
30. Graph Valid Tree
31. Container With Most Water
32. Group Anagrams
33. Remove Nth Node From End of List
34. Validate Binary Search Tree
35. Reverse Bits
36. Word Break
37. Number of Connected Components in an Undirected Graph
38. Non-overlapping Intervals
39. Search in Rotated Sorted Array
40. Longest Repeating Character Replacement
41. Reorder List
42. Kth Smallest Element in a BST
43. Longest Consecutive Sequence
44. Maximum Subarray
45. House Robber II
46. Pacific Atlantic Water Flow
47. Meeting Rooms
48. 3Sum
49. Encode and Decode Strings
50. Implement Trie (Prefix Tree)
51. Subtree of Another Tree
52. Maximum Product Subarray
53. Decode Ways
54. Alien Dictionary
55. Meeting Rooms II
56. Set Matrix Zeroes
57. Longest Palindromic Substring
58. Merge K Sorted Lists
59. Word Search
60. Construct Binary Tree from Preorder and Inorder Traversal
61. Longest Increasing Subsequence
62. Jump Game
63. Design Add and Search Words Data Structure
64. Spiral Matrix
65. Palindromic Substrings
66. Top K Frequent Elements
67. Binary Tree Maximum Path Sum
68. Longest Common Subsequence
69. Combination Sum
70. Rotate Image
71. Minimum Window Substring
72. Find Median from Data Stream
73. Lowest Common Ancestor of a Binary Search Tree
74. Serialize and Deserialize Binary Tree
75. Word Search II

Excluded: LeetCode 75 substitutions, variable Grind 75 selections, reverse cards, copied problem statements or examples, multiple-language variants, multiple verbose approaches, editorials, and proprietary explanations or code. For study technique, see [how to use flashcards for coding interviews](/ja/blog/how-to-use-flashcards-for-coding-interviews/) and [how interleaving works with flashcards](/ja/blog/how-to-use-interleaving-with-flashcards/). The related guides to [system-design interview flashcards](/ja/blog/how-to-use-flashcards-for-system-design-interviews/) and [learning terminal commands with flashcards](/ja/blog/how-to-learn-terminal-commands-with-flashcards/) extend the same retrieval-practice approach.

Source concepts and canonical titles are acknowledged. The original descriptions, Python solutions, organization, metadata, and cover are dedicated under CC0-1.0. This independent deck is not affiliated with or endorsed by LeetCode, Blind, GreatFrontEnd, or any employer.

## 類似のデッキ

- [Coding Interview Patterns Flashcards: Signals, Invariants &amp; Complexity](<https://nibomo.com/ja/catalog/packages/coding-interview-patterns-flashcards/>)
- [Functional Group Flashcards: Names &amp; Structures](<https://nibomo.com/ja/catalog/packages/organic-chemistry-functional-groups-flashcards/>)
- [Cell Organelle Flashcards: 24 Structures &amp; Functions in Both Directions](<https://nibomo.com/ja/catalog/packages/cell-organelles-functions/>)
- [GMAT Flashcards: Quant, Verbal &amp; Data Insights Decisions](<https://nibomo.com/ja/catalog/packages/gmat-quant-verbal-data-insights-flashcards/>)
- [Amino Acid Flashcards: 20 Side\-Chain Structures &amp; Codes](<https://nibomo.com/ja/catalog/packages/amino-acid-flashcards/>)
- [AWS Solutions Architect Associate SAA\-C03 Flashcards: Architecture Decisions &amp; Trade\-Offs](<https://nibomo.com/ja/catalog/packages/aws-solutions-architect-associate-saa-c03-flashcards/>)

## このデッキのカード

### カード 1

**質問**

Contains Duplicate

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

**回答**

```python
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).

### カード 2

**質問**

Valid Anagram

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

**回答**

```python

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.

### カード 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.

**回答**

```python
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).

### カード 4

**質問**

Valid Parentheses

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

**回答**

```python

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

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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.

### カード 8

**質問**

Number of 1 Bits

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

**回答**

```python

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

### カード 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.

**回答**

```python

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

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python

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

### カード 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).

**回答**

```python
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.

### カード 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.

**回答**

```python
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.

### カード 15

**質問**

Missing Number

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

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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).

### カード 19

**質問**

Longest Substring Without Repeating Characters

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

**回答**

```python

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

### カード 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).

**回答**

```python
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.

### カード 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.

**回答**

```python

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.

### カード 22

**質問**

House Robber

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

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 28

**質問**

Sum of Two Integers

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

**回答**

```python

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

### カード 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.

**回答**

```python

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

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 32

**質問**

Group Anagrams

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

**回答**

```python
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.

### カード 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).

**回答**

```python
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.

### カード 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.

**回答**

```python
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.

### カード 35

**質問**

Reverse Bits

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

**回答**

```python

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

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python

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.

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 44

**質問**

Maximum Subarray

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

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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).

### カード 52

**質問**

Maximum Product Subarray

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

**回答**

```python
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).

### カード 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.

**回答**

```python

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

### カード 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.

**回答**

```python
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.

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python

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

### カード 57

**質問**

Longest Palindromic Substring

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

**回答**

```python

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.

### カード 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).

**回答**

```python
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.

### カード 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.

**回答**

```python
from collections.abc import Sequence


def word_exists(board: Sequence[Sequence[str]], word: str) -> bool:
    rows = len(board)
    columns = len(board[0])
    visited: set[tuple[int, int]] = set()

    def search(row: int, column: int, index: int) -> bool:
        if index == len(word):
            return True
        if (
            row < 0
            or row >= rows
            or column < 0
            or column >= columns
            or (row, column) in visited
            or board[row][column] != word[index]
        ):
            return False
        visited.add((row, column))
        found = (
            search(row + 1, column, index + 1)
            or search(row - 1, column, index + 1)
            or search(row, column + 1, index + 1)
            or search(row, column - 1, index + 1)
        )
        visited.remove((row, column))
        return found

    return any(
        search(row, column, 0)
        for row in range(rows)
        for column in range(columns)
    )
```

Time: O(rows \* columns \* 4^L) in the worst case for word length L.

Auxiliary space: O(L).

### カード 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).

**回答**

```python
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.

### カード 61

**質問**

Longest Increasing Subsequence

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

**回答**

```python
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).

### カード 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.

**回答**

```python
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).

### カード 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.

**回答**

```python
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.

### カード 64

**質問**

Spiral Matrix

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

**回答**

```python
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.

### カード 65

**質問**

Palindromic Substrings

Given a string, count all contiguous palindromic substrings; equal text at different positions counts separately.

**回答**

```python

def count_palindromic_substrings(text: str) -> int:
    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

    return sum(odd_radii) + sum(even_radii)
```

Time: O(n).

Auxiliary space: O(n).

### カード 66

**質問**

Top K Frequent Elements

Given a nonempty integer array and valid k, return exactly k values with the highest frequencies; any order is accepted when ties permit multiple answers.

**回答**

```python
from collections import Counter
from collections.abc import Sequence


def top_k_frequent(nums: Sequence[int], k: int) -> list[int]:
    counts = Counter(nums)
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for value, frequency in counts.items():
        buckets[frequency].append(value)

    result: list[int] = []
    for frequency in range(len(buckets) - 1, 0, -1):
        for value in buckets[frequency]:
            result.append(value)
            if len(result) == k:
                return result
    raise ValueError("k exceeds the number of distinct values")
```

Time: O(n).

Auxiliary space: O(n).

### カード 67

**質問**

Binary Tree Maximum Path Sum

Given a nonempty binary tree, return the greatest sum of values along any nonempty simple path; the path may start and end at any nodes. Assume TreeNode with integer val, left, and right.

**回答**

```python
from __future__ import annotations


def maximum_path_sum(root: TreeNode) -> int:
    best = root.val
    gain_by_node: dict[int, int] = {}
    stack: list[tuple[TreeNode, bool]] = [(root, 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

        # Postorder makes both downward gains ready. Negative gains cannot help,
        # and pop frees each child gain after its parent's only use.
        left_gain = (
            0
            if node.left is None
            else max(0, gain_by_node.pop(id(node.left)))
        )
        right_gain = (
            0
            if node.right is None
            else max(0, gain_by_node.pop(id(node.right)))
        )
        best = max(best, node.val + left_gain + right_gain)
        gain_by_node[id(node)] = node.val + max(left_gain, right_gain)
    return best
```

Time: O(n).

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

### カード 68

**質問**

Longest Common Subsequence

Given two strings, return the length of their longest common subsequence; chosen characters keep order but need not be contiguous.

**回答**

```python

def longest_common_subsequence_length(first: str, second: str) -> int:
    shorter, longer = (first, second) if len(first) <= len(second) else (second, first)
    lengths = [0] * (len(shorter) + 1)
    for longer_character in longer:
        # diagonal is the previous row's value one column left; lengths[index]
        # is saved before overwrite while lengths[index - 1] is the current row.
        diagonal = 0
        for index, shorter_character in enumerate(shorter, start=1):
            previous = lengths[index]
            if longer_character == shorter_character:
                lengths[index] = diagonal + 1
            else:
                lengths[index] = max(lengths[index], lengths[index - 1])
            diagonal = previous
    return lengths[-1]
```

Time: O(n \* m).

Auxiliary space: O(min(n, m)).

### カード 69

**質問**

Combination Sum

Given a nonempty set of distinct positive candidates and a target from 1 to 40, return every distinct combination summing to the target; each candidate may be reused and combination order does not matter.

**回答**

```python
from collections.abc import Sequence


def combination_sum(candidates: Sequence[int], target: int) -> list[list[int]]:
    ordered = sorted(candidates)
    combinations: list[list[int]] = []
    current: list[int] = []

    def search(start: int, remaining: int) -> None:
        if remaining == 0:
            combinations.append(current.copy())
            return
        # Reusing index allows repetition; never moving backward keeps choices
        # nondecreasing, avoiding permutations. Sorting makes overshoot final.
        for index in range(start, len(ordered)):
            value = ordered[index]
            if value > remaining:
                break
            current.append(value)
            search(index, remaining - value)
            current.pop()

    search(0, target)
    return combinations
```

Time: O(n log(n + 1) + B + R), where B is the total candidate-loop iterations across all explored search calls and R is the total number of elements copied into returned combinations.

Auxiliary space: O(n + d), where d = floor(target / m) for minimum candidate m, for the sorted copy and search stack/path, excluding returned combinations.

### カード 70

**質問**

Rotate Image

Given an n-by-n mutable matrix, rotate it 90 degrees clockwise in place without allocating another matrix.

**回答**

```python

def rotate_image(matrix: list[list[int]]) -> None:
    size = len(matrix)
    # Transposing then reversing each row maps (r, c) to (c, n - 1 - r).
    for row in range(size):
        for column in range(row + 1, size):
            matrix[row][column], matrix[column][row] = (
                matrix[column][row],
                matrix[row][column],
            )
    for row in matrix:
        row.reverse()
```

Time: O(n^2).

Auxiliary space: O(1).

### カード 71

**質問**

Minimum Window Substring

Given strings source and nonempty target, return the shortest source substring containing every target character with its required multiplicity, or an empty string if none exists.

**回答**

```python
from collections import Counter


def minimum_window(source: str, target: str) -> str:
    # needed[c] is the remaining deficit (negative means surplus); missing is
    # the total number of required character instances still absent.
    needed = Counter(target)
    missing = len(target)
    left = 0
    best_start = 0
    best_length = len(source) + 1

    for right, character in enumerate(source):
        if needed[character] > 0:
            missing -= 1
        needed[character] -= 1

        while missing == 0:
            window_length = right - left + 1
            if window_length < best_length:
                best_start = left
                best_length = window_length
            left_character = source[left]
            needed[left_character] += 1
            if needed[left_character] > 0:
                missing += 1
            left += 1

    if best_length > len(source):
        return ""
    return source[best_start : best_start + best_length]
```

Time: O(n + m).

Auxiliary space: O(u), where u is the number of distinct characters across source and target.

### カード 72

**質問**

Find Median from Data Stream

Implement a structure that accepts integers one at a time and returns the median of all values seen; find_median is called only after at least one insertion.

**回答**

```python
import heapq


class MedianFinder:
    def __init__(self) -> None:
        # lower is a negated max-heap and may hold one extra value; every
        # value in lower is at most every value in the upper min-heap.
        self.lower: list[int] = []
        self.upper: list[int] = []

    def add_num(self, value: int) -> None:
        # Moving lower's maximum to upper restores ordering; the final move
        # restores the size invariant without changing that partition.
        heapq.heappush(self.lower, -value)
        heapq.heappush(self.upper, -heapq.heappop(self.lower))
        if len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))

    def find_median(self) -> float:
        if len(self.lower) > len(self.upper):
            return float(-self.lower[0])
        return (-self.lower[0] + self.upper[0]) / 2.0
```

Time: O(log n) per insertion and O(1) per median query.

Auxiliary space: O(n).

### カード 73

**質問**

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree and two nodes present in it, return their lowest common ancestor. Assume distinct values and TreeNode with val, left, and right.

**回答**

```python
from __future__ import annotations


def lowest_common_ancestor(root: TreeNode, first: TreeNode, second: TreeNode) -> TreeNode:
    low = min(first.val, second.val)
    high = max(first.val, second.val)
    current = root
    while True:
        # Outside [low, high], both nodes share one child side; inside it,
        # current is one target or the first point where their paths split.
        if current.val < low:
            current = current.right
        elif current.val > high:
            current = current.left
        else:
            return current
```

Time: O(h).

Auxiliary space: O(1).

### カード 74

**質問**

Serialize and Deserialize Binary Tree

Design functions that serialize any binary tree to a string and reconstruct an equivalent tree, preserving structure and integer values. Assume TreeNode(val, left, right).

**回答**

```python
from __future__ import annotations

from typing import Optional


def serialize_tree(root: Optional[TreeNode]) -> str:
    tokens: list[str] = []
    stack: list[Optional[TreeNode]] = [root]
    while stack:
        node = stack.pop()
        if node is None:
            tokens.append("#")
            continue
        tokens.append(str(node.val))
        stack.append(node.right)
        stack.append(node.left)
    return ",".join(tokens)


def deserialize_tree(data: str) -> Optional[TreeNode]:
    tokens = data.split(",")
    if tokens[0] == "#":
        if len(tokens) != 1:
            raise ValueError("Serialized empty tree contains extra tokens")
        return None

    root = TreeNode(int(tokens[0]), None, None)
    # Each stack entry is a node's next open slot: False for left, True for
    # right. A child is processed before the saved right slot, matching preorder.
    stack: list[tuple[TreeNode, bool]] = [(root, False)]
    for token in tokens[1:]:
        if not stack:
            raise ValueError("Serialized tree contains extra tokens")
        parent, left_is_filled = stack.pop()
        child = None if token == "#" else TreeNode(int(token), None, None)
        if left_is_filled:
            parent.right = child
        else:
            parent.left = child
            stack.append((parent, True))
        if child is not None:
            stack.append((child, False))

    if stack:
        raise ValueError("Serialized tree ended before all child slots were filled")
    return root
```

Time: O(n) for either operation.

Auxiliary space: O(n) for tokens plus O(h) for the stack; the returned tree is excluded.

### カード 75

**質問**

Word Search II

Given a lowercase character board with 1 to 12 rows and 1 to 12 columns and unique lowercase words of length 1 to 10, return every input word traceable through horizontal or vertical neighbors without reusing a cell within one word, in any order; do not change the board.

**回答**

```python
from __future__ import annotations

from collections.abc import Sequence


class SearchTrieNode:
    def __init__(self) -> None:
        self.children: dict[str, SearchTrieNode] = {}
        self.word: str | None = None


def find_words(
    board: Sequence[Sequence[str]],
    words: Sequence[str],
) -> list[str]:
    root = SearchTrieNode()
    for word in words:
        node = root
        for character in word:
            if character not in node.children:
                node.children[character] = SearchTrieNode()
            node = node.children[character]
        node.word = word

    rows = len(board)
    columns = len(board[0])
    visited: set[tuple[int, int]] = set()
    found: list[str] = []

    def search(row: int, column: int, node: SearchTrieNode) -> None:
        character = board[row][column]
        child = node.children.get(character)
        if child is None:
            return
        if child.word is not None:
            found.append(child.word)
            # Remove the terminal so another board path cannot emit it again.
            child.word = None

        visited.add((row, column))
        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 visited
            ):
                search(next_row, next_column, child)
        visited.remove((row, column))

        # No unfound word can use an empty, nonterminal prefix branch.
        if child.word is None and not child.children:
            del node.children[character]

    for row in range(rows):
        for column in range(columns):
            search(row, column, root)
    return found
```

Time: O(W + rows \* columns \* 4^L) in the worst case, for W dictionary characters and maximum word length L.

Auxiliary space: O(W + L), excluding returned words.

---
*[このページのスタイル付き HTML 版を見る](<https://nibomo.com/ja/catalog/packages/blind-75-python-solutions/>)*

*AI エージェントは `GET https://api.nibomo.com/v1/` から開始して、このサービスでユーザーアカウントを作成できます。設定後は、`https://mcp.nibomo.com/mcp` の MCP 経由で接続することもできます。*

*ヒント: https://nibomo.com の任意の URL に `.md` を付けると、ページのクリーンな Markdown 版を取得できます。*