min_heap 的应用，特别之处在于借助 index 对元素进行 track。

This pattern helps us solve problems that involve a list of sorted arrays.

Whenever we are given “K” sorted arrays, we can use a min heap to efficiently perform a sorted traversal of all the elements of all arrays. We can push the smallest (first) element of each sorted array in a min heap to get the overall minimum. While inserting elements to the min heap we keep track of which array the element came from. We can, then, remove the top element from the heap to get the smallest element and push the next element from the same array, to which this smallest element belonged, to the heap. We can repeat this process to make a sorted traversal of all elements.

Snippets

1
2
3
4
5
6
7
8
9
10
11

min_heap = []
for row in matrix:
    heappush(min_heap, (row[0], 0, row))  # keep track by index

n = len(matrix)
for _ in range(k - 1):
    _, idx, row = heappop(min_heap)
    if idx + 1 < n:
        heappush(min_heap, (row[idx+1], idx + 1, row))

return min_heap[0][0]

LeetCode

23. Merge k Sorted Lists
4. Median of Two Sorted Arrays
378. Kth Smallest Element in a Sorted Matrix
632. Smallest Range Covering Elements from K Lists
373. Find K Pairs with Smallest Sums

heapq 的大型应用现场，常与 freq 配合使用。借助 index 可以实现对复杂 object 的比较，也可以通过 total_ordering 定义数据类。有时需要用队列暂存 heappop 的元素。

Any problem that asks us to find the Top K Elements among a given set falls under this pattern.

The best data structure that comes to mind to keep track of “K” elements is heap. This pattern will make use of the heap to solve multiple problems dealing with “K” elements at a time from a set of given elements.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

freq = dict()
for char in s:
    freq[char] = freq.get(char, 0) + 1

max_heap = []
for char in freq:
    heappush(max_heap, (-freq[char], char))

ans = ""
while max_heap:
    queue, k = [], 2  # store pop-up items
    while max_heap and k > 0:
        count, char = heappop(max_heap)
        ans += char

        if -count - 1 > 0:
            queue.append((count + 1, char))
        
        k -= 1
    
    if k > 0 and queue:
        return ""
    
    for item in queue:
        heappush(max_heap, item)  # push back

return ans

LeetCode

692. Top K Frequent Words
215. Kth Largest Element in an Array
973. K Closest Points to Origin
1167. Minimum Cost to Connect Sticks
347. Top K Frequent Elements
451. Sort Characters By Frequency
703. Kth Largest Element in a Stream
658. Find K Closest Elements
1481. Least Number of Unique Integers after K Removals
1508. Range Sum of Sorted Subarray Sums
767. Reorganize String
358. Rearrange String k Distance Apart
621. Task Scheduler
895. Maximum Frequency Stack

四两拨千斤的位运算，比如：剥离最右边的 1、将最右边的 1 置 0 等等。更多技巧可以参考 Low Level Bit Hacks。

Bitwise XOR returns 0 (false) if both bits are the same and returns 1 (true) otherwise. In other words, it only returns 1 if exactly one bit is set to 1 out of the two bits in comparison:

It is surprising to know the approaches that the XOR operator enables us to solve certain problems. For example, let’s take a look at the following problem:

Given an array of n-1 integers in the range from 1 to n, find the one number that is missing from the array.

Example:

1
2

Input: 1, 5, 2, 6, 4
Answer: 3

A straight forward approach to solve this problem can be:

1. Find the sum of all integers from 1 to n; let’s call it: s1.
2. Subtract all the numbers in the input array from s1; this will give us the missing number.

无处不在的二分思想。往往通过外部变量 track 中间结果，元素不是 distinct 时需要单独处理。有时仅为解法的一小步，bisect_left 第一个大于等于；bisect_right 第一个大于。

As we know, whenever we are given a sorted array or linked list or matrix, and we are asked to find a certain element, the best algorithm we can use is binary search.

This pattern describes an efficient way to handle all problems involving Binary Search. We will go through a set of problems that will help us build an understanding of this pattern so that we can apply this technique to other problems we might come across in the interviews.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12

lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = lo + ((hi - lo) >> 1)
    if nums[mid] >= target:
        if mid == 0 or nums[mid-1] < target:  # find leftmost element
            return mid
        
        hi = mid - 1
    else:
        lo = mid + 1

return len(nums)  # all less

LeetCode

704. Binary Search
35. Search Insert Position
744. Find Smallest Letter Greater Than Target
34. Find First and Last Position of Element in Sorted Array
702. Search in a Sorted Array of Unknown Size
270. Closest Binary Search Tree Value
852. Peak Index in a Mountain Array
1095. Find in Mountain Array
33. Search in Rotated Sorted Array
153. Find Minimum in Rotated Sorted Array

使用 BFS 解决一系列排列、组合问题。基本上对 queue 进行迭代就可以了（需要 popleft 时选择 deque），但有时需要用到递归。

A huge number of coding interview problems involve dealing with Permutations and Combinations of a given set of elements. This pattern describes an efficient breadth-first search approach to handle all these problems.

Snippets

1
2
3
4
5
6
7
8
9
10
11
12

"""Iteration"""
queue = deque([[]])
for num in sorted(nums):  # handle duplicates
    for _ in range(len(queue)):
        item = queue.popleft()
        cand = item + [num]
        if cand not in queue:
            queue.append(cand)
        
        queue.append(item)

return queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

"""Recursion"""
@cache
def build(start, end):
    if start > end:
        return [None]

    trees = []
    for val in range(start, end + 1):
        # divide & conquer
        l = build(start, val - 1)
        r = build(val + 1, end)

        for x in l:
            for y in r:
                root = TreeNode(val)
                root.left = x
                root.right = y
                trees.append(root)

    return trees

return build(1, n)

LeetCode

78. Subsets
90. Subsets II
46. Permutations
784. Letter Case Permutation
22. Generate Parentheses
320. Generalized Abbreviation
241. Different Ways to Add Parentheses
95. Unique Binary Search Trees II
96. Unique Binary Search Trees