Blind 75 Arrays, Intervals, Heaps, And Matrices

Use a set. Invariant: before reading nums[i], the set contains exactly the values seen at earlier indices. Mistake to avoid: sorting changes the cost to O(n log n) and can obscure the simpler expected answer. Test empty, one element, duplicate adjacent, duplicate far apart, and negative values.

Count characters in both strings or add for one string and subtract for the other. Invariant: after processing aligned positions, the counter equals the frequency difference for the prefixes. Mistake to avoid: assuming ASCII only without asking. Test unequal lengths, repeated characters, mixed case if allowed, and Unicode if the interviewer leaves character set open.

Count with a hash map, then use bucket sort for O(n) expected time or a heap for O(n log k). Invariant for the heap version: the heap contains the best k elements among processed frequency pairs. Mistake to avoid: sorting all counts when the follow-up asks for better than O(n log n). Test k = 1, k equals distinct count, ties, and all values equal.

Track both max and min products ending at the current index because a negative value can swap them. Invariant: after processing x, hi and lo are the largest and smallest products of subarrays ending at x. Mistake to avoid: only tracking the max, which fails on two negatives. Test zeros, all negatives, one element, and alternating signs.

def max_product(nums):
    best = hi = lo = 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

Use two pointers. Invariant: after evaluating a pair, moving the shorter side is the only move that can possibly improve area because width always shrinks. Mistake to avoid: moving the taller side and skipping candidates with a higher limiting height. Test strictly increasing heights, strictly decreasing heights, equal heights, and two-element input.

Append intervals before the new interval, merge all overlaps, then append the rest. Invariant: output is sorted and non-overlapping for everything already consumed. Mistake to avoid: treating touching endpoints incorrectly; ask whether [1, 2] and [2, 3] overlap. Test insert before all, after all, merging one, merging many, and exact endpoint contact.

Sort by start, then maintain the last merged interval. Invariant: the merged list covers exactly the processed intervals and has no overlaps. Mistake to avoid: forgetting to update the end with max when a later interval is contained by the active one. Test nested intervals, unsorted input, endpoint contact, and a single interval.

Greedily keep intervals with the earliest end time. Invariant: among processed intervals, the kept set has maximum size and the smallest possible last end for that size. Mistake to avoid: sorting by start and removing the next interval without comparing ends. Test identical intervals, nested intervals, endpoint contact, and no overlaps.

This common follow-up uses a min-heap of meeting end times. Invariant: the heap contains the end time of each room currently in use after processing meetings in start-time order.

import heapq

def min_meeting_rooms(intervals):
    rooms = []
    for start, end in sorted(intervals):
        if rooms and rooms[0] <= start:
            heapq.heappop(rooms)
        heapq.heappush(rooms, end)
    return len(rooms)

Use a max-heap for the lower half and a min-heap for the upper half. Invariant: every value in the lower heap is less than or equal to every value in the upper heap, and heap sizes differ by at most one. Mistake to avoid: balancing sizes without preserving ordering. Test increasing input, decreasing input, duplicates, negatives, and even versus odd counts.

Push each non-empty list head into a heap, pop the smallest node, and push that node's successor. Invariant: the heap contains the smallest unmerged node from each active list. Mistake to avoid: pushing nodes directly in Python without a tie-breaker when values match. Test empty list array, all lists empty, duplicates across lists, and one very long list.

Use the first row and first column as marker storage, plus flags for whether they originally contained zero. Invariant: after the marker pass, matrix[r][0] and matrix[0][c] encode whether row r or column c should be zeroed. Mistake to avoid: overwriting markers before the inner cells are processed. Test one row, one column, zero at [0][0], and multiple zeroes.

Maintain top, bottom, left, and right boundaries. Invariant: after each side traversal, the corresponding boundary moves inward and no visited cell remains inside the active rectangle. Mistake to avoid: traversing bottom or left after the boundaries have crossed. Test square, single row, single column, wide rectangle, and tall rectangle.

Transpose across the main diagonal, then reverse each row. Invariant after transpose: matrix[r][c] has swapped with matrix[c][r] exactly once for c > r. Mistake to avoid: swapping each pair twice. Test 1 x 1, 2 x 2, odd size, and even size.

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

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

    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

Iterate with prev and cur. Invariant: prev is the reversed prefix and cur is the head of the unreversed suffix. Mistake to avoid: losing cur.next before saving it. Test empty list, one node, two nodes, and longer list.

Use Floyd's slow and fast pointers. Invariant: if a cycle exists, the fast pointer gains one node per step on the slow pointer modulo the cycle length, so they eventually meet. Mistake to avoid: dereferencing fast.next without checking it. Test empty, no cycle, cycle at head, and cycle in the middle.

Use a dummy node and move fast ahead by n steps, then move slow and fast together. Invariant: the gap between pointers is n, so when fast reaches the end, slow.next is the node to remove. Mistake to avoid: failing when removing the head. Test one node, remove head, remove tail, and middle removal.

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