Blind 75 Coding Interview Chapter

Invariant: before processing nums[i], the map contains values from indices less than i. If the complement is already present, the pair is valid and cannot reuse the same index.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    raise ValueError("no solution")

Invariant: after the forward pass, out[i] is the product of values left of i. During the reverse pass, right is the product of values right of i.

def product_except_self(nums):
    out = [1] * len(nums)
    left = 1
    for i, x in enumerate(nums):
        out[i] = left
        left *= x

    right = 1
    for i in range(len(nums) - 1, -1, -1):
        out[i] *= right
        right *= nums[i]
    return out

Invariant: the active window from left to right contains no duplicates after updating left. Never move left backward.

def length_of_longest_substring(s):
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

Invariant: when DFS starts from an unvisited land cell, it marks exactly one island. Mark before pushing neighbors so the same cell cannot be added repeatedly.

def num_islands(grid):
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    islands = 0

    def flood(r, c):
        stack = [(r, c)]
        grid[r][c] = "0"
        while stack:
            x, y = stack.pop()
            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == "1":
                    grid[nx][ny] = "0"
                    stack.append((nx, ny))

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                islands += 1
                flood(r, c)
    return islands

Invariant: after computing dp[a], it stores the fewest coins needed for amount a using any denomination. Greedy fails for many coin systems, so use dynamic programming.

def coin_change(coins, amount):
    inf = amount + 1
    dp = [inf] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return -1 if dp[amount] == inf else dp[amount]

Invariant: the target, if present, is always inside the closed search interval. At least one side of mid is sorted, so use that side to decide which half can be discarded.

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

Invariant: a course with indegree zero has no remaining unmet prerequisites. Removing it can only reduce indegrees of courses that depend on it. If every course is removed, there is no cycle.

from collections import deque


def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, prereq in prerequisites:
        graph[prereq].append(course)
        indegree[course] += 1

    ready = deque(i for i, degree in enumerate(indegree) if degree == 0)
    taken = 0
    while ready:
        prereq = ready.popleft()
        taken += 1
        for course in graph[prereq]:
            indegree[course] -= 1
            if indegree[course] == 0:
                ready.append(course)
    return taken == num_courses

Invariant: the result list is sorted and non-overlapping, and its last interval is the only interval that can overlap the next sorted input interval.

def merge_intervals(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda item: item[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged

Invariant: when formed == required, the current window satisfies all required counts. Shrink from the left until removing a character would break the invariant.

from collections import Counter, defaultdict


def min_window(s, t):
    need = Counter(t)
    window = defaultdict(int)
    required = len(need)
    formed = 0
    best = (float("inf"), 0, 0)
    left = 0

    for right, ch in enumerate(s):
        window[ch] += 1
        if ch in need and window[ch] == need[ch]:
            formed += 1

        while formed == required:
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            drop = s[left]
            window[drop] -= 1
            if drop in need and window[drop] < need[drop]:
                formed -= 1
            left += 1

    if best[0] == float("inf"):
        return ""
    return s[best[1]:best[2] + 1]

Invariant: the low heap stores the smaller half as negatives, the high heap stores the larger half, and their sizes differ by at most one. The median is one heap top or the average of both tops.

import heapq


class MedianFinder:
    def __init__(self):
        self.low = []
        self.high = []

    def add_num(self, num):
        heapq.heappush(self.low, -num)
        heapq.heappush(self.high, -heapq.heappop(self.low))
        if len(self.high) > len(self.low):
            heapq.heappush(self.low, -heapq.heappop(self.high))

    def find_median(self):
        if len(self.low) > len(self.high):
            return float(-self.low[0])
        return (-self.low[0] + self.high[0]) / 2

Invariant: the stack stores the exact closing brackets required for the prefix processed so far. A closing bracket is valid only if it matches the most recent expected closer.

def is_valid_parentheses(s):
    pairs = {"(": ")", "[": "]", "{": "}"}
    stack = []
    for ch in s:
        if ch in pairs:
            stack.append(pairs[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Invariant: dp[i] means the prefix s[:i] can be segmented. To compute it, find any prior cut j where the prefix is valid and s[j:i] is a dictionary word.

def word_break(s, word_dict):
    words = set(word_dict)
    dp = [False] * (len(s) + 1)
    dp[0] = True

    for i in range(1, len(s) + 1):
        for j in range(i):
            if dp[j] and s[j:i] in words:
                dp[i] = True
                break
    return dp[-1]

Invariant: intervals before the merge point are already finalized, the current new interval absorbs every overlap, and intervals after it can be appended unchanged.

def insert_interval(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)

    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)

    result.extend(intervals[i:])
    return result

Invariant: tails[k] is the smallest possible tail value for an increasing subsequence of length k + 1. Smaller tails preserve more future options. The list is not necessarily the final subsequence.

from bisect import bisect_left


def length_of_lis(nums):
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Invariant: after processing position i, prev1 is the number of decodes for the prefix ending at i, and prev2 is the count for the prefix before it. Zeros only work as part of 10 or 20.

def num_decodings(s):
    if not s or s[0] == "0":
        return 0

    prev2, prev1 = 1, 1
    for i in range(1, len(s)):
        current = 0
        if s[i] != "0":
            current += prev1
        two_digit = int(s[i - 1:i + 1])
        if 10 <= two_digit <= 26:
            current += prev2
        prev2, prev1 = prev1, current
    return prev1

Invariant: reverse traversal from an ocean marks every cell that can reach that ocean by non-increasing forward flow. Moving backward, you may only step to equal or higher neighbors.

def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []

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

    def reach(starts):
        seen = set(starts)
        stack = list(starts)
        while stack:
            r, c = stack.pop()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and (nr, nc) not in seen
                    and heights[nr][nc] >= heights[r][c]
                ):
                    seen.add((nr, nc))
                    stack.append((nr, nc))
        return seen

    pacific = [(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)]
    atlantic = [(rows - 1, c) for c in range(cols)] + [
        (r, cols - 1) for r in range(rows)
    ]
    both = reach(pacific) & reach(atlantic)
    return [[r, c] for r, c in sorted(both)]

Invariant: DFS returns the best one-branch gain that can continue upward to the parent. The global answer may use both branches at the current node, but that split path cannot be returned upward.

def max_path_sum(root):
    best = -10**18

    def gain(node):
        nonlocal best
        if not node:
            return 0
        left = max(0, gain(node.left))
        right = max(0, gain(node.right))
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

Invariant: each bucket index represents an exact frequency. After counting, scanning buckets from high to low yields elements in descending frequency without sorting all unique values.

from collections import Counter


def top_k_frequent(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for value, freq in counts.items():
        buckets[freq].append(value)

    result = []
    for freq in range(len(buckets) - 1, 0, -1):
        for value in buckets[freq]:
            result.append(value)
            if len(result) == k:
                return result
    return result

Invariant: after counting both strings, every character must have the same frequency. Length mismatch is an immediate failure because equal counts cannot hold.

from collections import Counter


def is_anagram(s, t):
    if len(s) != len(t):
        return False
    return Counter(s) == Counter(t)

Invariant: every word maps to a canonical key shared by exactly its anagram group. For lowercase English letters, a 26-count tuple is a stable hashable key.

from collections import defaultdict


def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        counts = [0] * 26
        for ch in word:
            counts[ord(ch) - ord("a")] += 1
        groups[tuple(counts)].append(word)
    return list(groups.values())

Invariant: the heap contains end times for meetings currently using rooms. Before adding a meeting, free every room whose end time is less than or equal to the new start.

import heapq


def min_meeting_rooms(intervals):
    intervals.sort(key=lambda item: item[0])
    active = []
    best = 0
    for start, end in intervals:
        while active and active[0] <= start:
            heapq.heappop(active)
        heapq.heappush(active, end)
        best = max(best, len(active))
    return best

Invariant: farthest is the greatest index reachable from any index processed so far. If the current index is beyond it, no later jump can repair the gap.

def can_jump(nums):
    farthest = 0
    for i, jump in enumerate(nums):
        if i > farthest:
            return False
        farthest = max(farthest, i + jump)
        if farthest >= len(nums) - 1:
            return True
    return True

Invariant: before evaluating a sale on day i, min_price is the cheapest valid buy price from an earlier day. The best profit never needs a future buy date.

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for price in prices:
        best = max(best, price - min_price)
        min_price = min(min_price, price)
    return best

Invariant: every character outside the active left..right window has already been matched or ignored. Skip punctuation before comparing normalized characters.

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

Invariant: after sorting by end time, keeping the interval that ends earliest preserves the most room for future intervals. Every overlapping interval skipped counts as one removal.

def erase_overlap_intervals(intervals):
    if not intervals:
        return 0

    intervals.sort(key=lambda item: item[1])
    removals = 0
    last_end = intervals[0][1]
    for start, end in intervals[1:]:
        if start < last_end:
            removals += 1
        else:
            last_end = end
    return removals

Invariant: a valid tree has exactly n - 1 edges and every node is reachable from any starting node. The edge count rules out cycles once connectivity is proven.

from collections import defaultdict


def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False

    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    seen = {0}
    stack = [0]
    while stack:
        node = stack.pop()
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return len(seen) == n

Invariant: before reading nums[i], the set contains exactly the distinct values from earlier indices. If the current value is already present, the duplicate pair uses two different indices. Test [1,2,3,1], [1,2,3,4], [], and repeated negative values.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

Invariant: ending_here is the best subarray sum that must end at the current index. The global best is the best value seen across all endings. Test all-negative arrays, one element, and arrays where the best subarray starts after a large loss.

def max_subarray(nums):
    if not nums:
        raise ValueError("nums must be non-empty")

    ending_here = nums[0]
    best = nums[0]
    for x in nums[1:]:
        ending_here = max(x, ending_here + x)
        best = max(best, ending_here)
    return best

Invariant: hi and lo are the largest and smallest products ending at the current index. The smallest value matters because a negative number can turn it into the largest. Test zeros, all negatives, one element, and two separated positive regions split by zero.

def max_product(nums):
    if not nums:
        raise ValueError("nums must be non-empty")

    hi = lo = best = nums[0]
    for x in nums[1:]:
        if x < 0:
            hi, lo = lo, hi
        hi = max(x, hi * x)
        lo = min(x, lo * x)
        best = max(best, hi)
    return best

Invariant: the minimum is always inside the closed interval left..right. If nums[mid] is greater than the right boundary, the minimum must be to the right; otherwise it is at mid or to the left. Test no rotation, rotation by one, two elements, and a single element.

def find_min_rotated(nums):
    if not nums:
        raise ValueError("nums must be non-empty")

    left, right = 0, len(nums) - 1
    while left < right:
        mid = (left + right) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

Invariant: after sorting and fixing index i, the two-pointer scan explores all pairs to the right of i exactly once. Skip duplicate fixed values and duplicate pointer values only after recording a valid triplet. Test all zeros, duplicates around a valid answer, no answer, and arrays shorter than three.

def three_sum(nums):
    nums.sort()
    out = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, len(nums) - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                out.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return out

Invariant: the current area is limited by the shorter wall. Moving the taller wall inward cannot improve the area for the shorter wall because width only shrinks, so discard the shorter side. Test monotonic heights, equal heights, two elements, and repeated plateaus.

def max_area(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        width = right - left
        best = max(best, width * min(height[left], height[right]))
        if height[left] <= height[right]:
            left += 1
        else:
            right -= 1
    return best

Invariant: every node must be inside the open interval inherited from all ancestors, not only from its immediate parent. Test a violation deep in a subtree, duplicate values, an empty tree, and large negative or positive bounds.

def is_valid_bst(root):
    def valid(node, low, high):
        if node is None:
            return True
        if not low < node.val < high:
            return False
        return valid(node.left, low, node.val) and valid(node.right, node.val, high)

    return valid(root, float("-inf"), float("inf"))

Invariant: the recursive return value is the best one-sided gain that can continue to the parent. The global answer may use both left and right gains at the current node. Test all-negative trees, a best path that does not include the root, and single-node trees.

def max_path_sum(root):
    best = float("-inf")

    def gain(node):
        nonlocal best
        if node is None:
            return 0
        left = max(gain(node.left), 0)
        right = max(gain(node.right), 0)
        best = max(best, node.val + left + right)
        return node.val + max(left, right)

    gain(root)
    return best

Invariant: bucket i contains exactly the values that appeared i times. Scanning buckets from high to low returns values in descending frequency without sorting all pairs. Test ties, k equal to the number of unique values, and negative integers.

from collections import Counter


def top_k_frequent(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for value, freq in counts.items():
        buckets[freq].append(value)

    out = []
    for freq in range(len(buckets) - 1, 0, -1):
        for value in buckets[freq]:
            out.append(value)
            if len(out) == k:
                return out
    return out

Invariant: walking a word follows exactly one child edge per character, and the terminal marker distinguishes a complete word from a prefix. Test searching a prefix before insertion as a full word, inserting overlapping words, and empty-prefix behavior.

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["#"] = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and "#" in node

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, text):
        node = self.root
        for ch in text:
            if ch not in node:
                return None
            node = node[ch]
        return node

Invariant: prev is the reversed prefix and curr is the first node not yet reversed. Save curr.next before rewiring. Test empty, one node, two nodes, and a longer list.

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Invariant: after advancing fast by n nodes, the gap between fast and slow is exactly n. A dummy node makes deleting the head the same as deleting any other node. Test removing the head, tail, only node, and a middle node.

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy

    for _ in range(n):
        fast = fast.next

    while fast.next:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return dummy.next

Invariant: the first row and first column become marker storage for whether each row or column should be zeroed. Separate flags protect their original zero state. Test a zero in the first row, first column, no zeros, and a one-by-one matrix.

def set_zeroes(matrix):
    rows, cols = len(matrix), len(matrix[0])
    first_row_zero = any(matrix[0][c] == 0 for c in range(cols))
    first_col_zero = any(matrix[r][0] == 0 for r in range(rows))

    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][c] == 0:
                matrix[r][0] = 0
                matrix[0][c] = 0

    for r in range(1, rows):
        for c in range(1, cols):
            if matrix[r][0] == 0 or matrix[0][c] == 0:
                matrix[r][c] = 0

    if first_row_zero:
        for c in range(cols):
            matrix[0][c] = 0
    if first_col_zero:
        for r in range(rows):
            matrix[r][0] = 0

Invariant: top, bottom, left, and right bound the unvisited rectangle. After each side is emitted, shrink that side and guard against single-row or single-column double visits. Test one row, one column, square, and rectangular matrices.

def spiral_order(matrix):
    if not matrix or not matrix[0]:
        return []

    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
    out = []

    while top <= bottom and left <= right:
        for c in range(left, right + 1):
            out.append(matrix[top][c])
        top += 1

        for r in range(top, bottom + 1):
            out.append(matrix[r][right])
        right -= 1

        if top <= bottom:
            for c in range(right, left - 1, -1):
                out.append(matrix[bottom][c])
            bottom -= 1

        if left <= right:
            for r in range(bottom, top - 1, -1):
                out.append(matrix[r][left])
            left += 1

    return out

Invariant: every palindrome has either one center or a gap between two centers. Expanding from all centers finds every candidate. Test odd length, even length, all same characters, and no repeated adjacent characters.

def longest_palindrome(s):
    best = (0, 0)

    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

    for i in range(len(s)):
        for left, right in (expand(i, i), expand(i, i + 1)):
            if right - left > best[1] - best[0]:
                best = (left, right)
    return s[best[0]:best[1] + 1]

Invariant: every encoded item carries its exact length before the payload, so the decoder never guesses based on delimiter content. Test empty strings, strings containing the delimiter, repeated strings, and an empty list.

def encode(strings):
    return "".join(f"{len(s)}#{s}" for s in strings)


def decode(blob):
    out = []
    i = 0
    while i < len(blob):
        j = blob.index("#", i)
        size = int(blob[i:j])
        start = j + 1
        out.append(blob[start:start + size])
        i = start + size
    return out

Invariant: preorder traversal with null markers fully determines tree shape. During deserialization, consuming tokens in the same preorder order rebuilds each subtree exactly once. Test empty tree, single node, skewed tree, duplicate values, and negative values.

def serialize(root):
    vals = []

    def walk(node):
        if node is None:
            vals.append("#")
            return
        vals.append(str(node.val))
        walk(node.left)
        walk(node.right)

    walk(root)
    return ",".join(vals)


def deserialize(data):
    vals = iter(data.split(","))

    def build():
        val = next(vals)
        if val == "#":
            return None
        node = TreeNode(int(val))
        node.left = build()
        node.right = build()
        return node

    return build()

Invariant: a normal character follows one trie edge, while a dot branches over all child edges at that depth. The end marker still decides whether the whole pattern is a word. Test dot at the beginning, middle, and end; exact search; prefix-only search; and no-match patterns.

class WordDictionary:
    def __init__(self):
        self.root = {}

    def add_word(self, word):
        node = self.root
        for ch in word:
            node = node.setdefault(ch, {})
        node["#"] = True

    def search(self, pattern):
        def dfs(i, node):
            if i == len(pattern):
                return "#" in node
            ch = pattern[i]
            if ch == ".":
                return any(key != "#" and dfs(i + 1, child)
                           for key, child in node.items())
            return ch in node and dfs(i + 1, node[ch])

        return dfs(0, self.root)