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

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 midreturn 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: 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:        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)    first_col = [matrix[r] for r in range(0, row)]        r = bisect.bisect_left(first_col, target)    if r == 0:        return matrix == target    elif r == row:        r = row - 1    elif matrix[r] == target:        return True    elif matrix[r] > 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)-1while left < right:    mid = left + (right - left) // 2    if condition(mid):        right = mid    else:        left = mid + 1return 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 .

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=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        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            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 = []# heapifyfor 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 !