After solved 1000 medium leetcode found these patterns — Binary Search, Trie, Heap
Following previous posted patterns : DFS , BFS, DP, Backtracking, Monostack ,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 subarray ,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 .
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][c1]
return matrix[r][c] == target
More binary search problems
34. Find First and Last Position of Element in Sorted Array
81. Search in Rotated Sorted Array II
981. Time Based KeyValue Store
Pattern2
Do Conditional Binary Search, find the first index fulfil “condition”
left, right = 0, len(array)1
while left < right:
mid = left + (right  left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return left
These problems goal is to find the “first something” , so it’s kind of greedy thinking used in binary search. if the array[index] can fulfil the condition, next values all can fulfil, find the smallest index value. Strongly recommanded go through this nice summary .
Sample Problems .
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
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 .
More heap related problems
373. Find K Pairs with Smallest Sums
378. Kth Smallest Element in a Sorted Matrix
973. K Closest Points to Origin
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 !