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

LORY
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

More binary search problems

34. Find First and Last Position of Element in Sorted Array

81. Search in Rotated Sorted Array II

240. Search a 2D Matrix II

611. Valid Triangle Number

981. Time Based Key-Value 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 .

278 First Bad Version

875. Koko Eating Bananas

1011 Can ship within days

Trie

Core Pattern

class Node:
def __init__(self, v):
self.val = v
self.children = []
self.end=False
class 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 .

More heap related problems

355. Design Twitter

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 !

--

--

LORY

A channel which focusing on developer growth and self improvement