After solved 1000 medium leetcode found these patterns — Binary Search, Trie, Heap

6 min readMar 28, 2022

Following previous posted patterns : DFS , BFS, DP, Backtracking, Mono-stack ,Presum, Greedy , Sliding Window, 2 Pointers, UnionFind, Devide and conquer, Topo sort. In this article, continue share the last few patterns — most problems categary i have been asked during interview — Binary Search, Trie, Heap.

Let’s start .

BinarySearch

Pattern1

Problem #1 Find target 
array.sort()
left, right = 0, len(array)
while left < right:
    mid = left + (right - left) // 2
    if target < array[mid]:
        right = mid
    elif target > array[mid]:
        left = mid + 1
    else:
        return mid
return None
# or (in python )
bisect.bisect_left(arr)

This is standard binary problem, find the target value in sorted array . in python , it is handy to direct use bisect.bisect_left (or bisect_right) to find the index .

Lets see some problems .

33. Search in Rotated Sorted Array

Thought process .Array is sorted , even it is rotated , since it is to find a target number , so still try binary search . the rotated sorted array can consider consists 2 sorted sub-array ,and the 1st sorted array last value is the max, 2nd sorted array first value is min (need find the pivot between 2 arrays, explained below code) ; then apply binary search on either of the array, depends on the index position .

def search(self, nums: List[int], target: int) -> int:
    """
        1. find the pivot index
        2. do binary search either in [0...pivot] or [pivot+1,... n]
        
            pivot
              |
        4 5 6 7 0 1 2
        |       |   |
        0   pivot+1 n
        when target >= nums[0]: search in [0...pivot]
        else                  : search in [pivot+1...n]
    """
    piv = 0
    while piv < len(nums)-1 and nums[piv] < nums[piv+1]:
        piv +=1
    
    if target >= nums[0]:
        x= bisect_left(nums, target, 0, piv)
    else:
        x = bisect_left(nums, target, piv+1, len(nums)-1)
    if x > len(nums) - 1:
        return -1
    return x if nums[x] == target else -1

Another sample .

74. Search a 2D Matrix

Thought Process. Since column and row both sorted. binary search should be come into mind .2 steps, first to find which row the target located; then find the matrix[row][col] . remember to handle different edge cases (explained below).

def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
    """
        do a binary search on the first column values
        Case1 : landed first row
        Case2 : landed last row
        Case3 : matched with some value in first col
        Case4 : land in certain row. do binary search on that row
    """
    row, col = len(matrix), len(matrix[0])
    first_col = [matrix[r][0] for r in range(0, row)]
    
    r = bisect.bisect_left(first_col, target)
    if r == 0:
        return matrix[0][0] == target
    elif r == row:
        r = row - 1
    elif matrix[r][0] == target:
        return True
    elif matrix[r][0] > target:
        r -= 1
        
    c = bisect.bisect_left(matrix[r], target)
    if c == col:
        return target == matrix[r][c-1]
    
    return matrix[r][c] == target

Trie

Core Pattern

class Node:
    def __init__(self, v):
        self.val = v
        self.children = []
        self.end=Falseclass Trie:
    def __init__(self):
        self.root = Node('')    def insert(self, word: str) -> None:
        cur = self.root
        for w in word:
            matched = [c for c in cur.children if c.val == w]
            if not matched:
                cur.children.append(Node(w))
                cur = cur.children[-1]
            else:
                cur = matched[0]
        cur.end=True                    # mark end char of word    def _search(self, word):            # to be reused in search and prefix search
        cur = self.root
        for w in word:
            matched = [c for c in cur.children if c.val == w]
            if matched:
                cur = matched[0]
            else:
                return None
        return cur    def search(self, word: str) -> bool:
        res = self._search(word)
        return False if not res else res.end    def startsWith(self, prefix: str) -> bool:
        res = self._search(prefix)
        return False if not res else True

Similar to UnionFind, Trie itself is a useful data structure create once can be reused everywhere . The idea is to build a “dictionary tree” ,to make the word searching faster ,every char is the leaf node .

Problems

I will not repeat the solution code here . because if you come up with Trie class then should able to solve the problem easily, either insert or searching (full word or prefix )

208. Implement Trie (Prefix Tree)

211. Design Add and Search Words Data Structure

421. Maximum XOR of Two Numbers in an Array

648. Replace Words

Heap

Pattern

arr = []
# heapify
for n in nums:
    heapq.heappush(arr, n)
    if pop_condition(arr, k):
        heapq.heappop(arr)
return result(arr)

The pop_condition usually are top k (or kth) largest or smallest , or closest positions to some coordinate.

Sample Problem 215. Kth Largest Element in an Array

Thought Process. We could sort the whole array and return the kth , which is O(N*LogN) ,since it only asked Kth largest, so we only have to maintein K sorted elements in array. this is very classic usage of heap .

def findKthLargest(self, nums: List[int], k: int) -> int:
    arr = []
    for n in nums:
        heapq.heappush(arr, n)
        if len(arr) > k:
            heapq.heappop(arr)
    return heapq.heappop(arr)

Another one . 347. Top K Frequent Elements

Thought process. instead of use array value as heap key, the frequency of elements should be the first key of heap . so this is still a “top K largest or smallest” problem , the only extra info is to use counter to store every element .

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    wc = collections.Counter(nums)
    arr = [(v,k) for k,v in wc.items()] # sort by frequency,value
    res = []
    for a in arr:
        heapq.heappush(res, a)
        if len(res) > k:
            heapq.heappop(res)
    return [k for v,k in res]

You get the idea. heap is easy to understand, useful to solve any kind of top K problems.

For top K problem, here has a good discussion. quick select also a good option . but need write more code .

Conclusion

Binary Search . I can not remember how many interviewer problems (may be around 4–5) has been asked about binary search, search in rotated array, or matrix, some even as simple as search some target within a sorted array (but yes it’s usually only first round ) ..if you are preparing interview, binary search is a MUST .

Trie. As long as you get the data structure , it is not hard to understand . I have been asked once to implement a Trie during interview with FANG .

Heap. I have been asked in interview 2 times , also used in multiple projects, to maintein a top K ranking. it is useful and in most languages it is already implemented. in case you really interested in build your own heap from 0 , here is a good explaination . the idea is devide and conquer and keep mid index as the smallest value and merge the result.

Last

Leetcoding more than interview preparation, it is like a coding gym for developers to have a break from “CRUD code” day to day work and to have some fun, to keep our DSA foundation strong, also ready and be competitive to new problems in any projects .

Thanks for reading and happy leetcoding !