**Two pointers: one input, opposite ends**
```python
def fn(arr):
left = ans = 0
right = len(arr) - 1
while left < right:
# do some logic here with left and right
if CONDITION:
left += 1
else:
right -= 1
return ans
```
**Two pointers: two inputs, exhaust both**
```python
def fn(arr1, arr2):
i = j = ans = 0
while i < len(arr1) and j < len(arr2):
# do some logic here
if CONDITION:
i += 1
else:
j += 1
while i < len(arr1):
# do logic
i += 1
while j < len(arr2):
# do logic
j += 1
return ans
```
**Build a prefix sum**
```python
def fn(arr):
prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[-1] + arr[i])
return prefix
```
**Reversing a linked list**
```python
def fn(head):
curr = head
prev = None
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
```
**Monotonic increasing stack**
```python
def fn(arr):
stack = []
ans = 0
for num in arr:
# for monotonic decreasing, just flip the > to <
while stack and stack[-1] > num:
# do logic
stack.pop()
stack.append(num)
return ans
```
**Find top k elements with heap**
```python
import heapq
def fn(arr, k):
heap = []
for num in arr:
# do some logic to push onto heap according to problem's criteria
heapq.heappush(heap, (CRITERIA, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for num in heap]
```
**Binary search**
```python
def fn(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
# do something
return
if arr[mid] > target:
right = mid - 1
else:
left = mid + 1
# left is the insertion point
return left
```
**Build a trie**
```python
# note: using a class is only necessary if you want to store data at each node.
# otherwise, you can implement a trie using only hash maps.
class TrieNode:
def __init__(self):
# you can store data at nodes if you wish
self.data = None
self.children = {}
def fn(words):
root = TrieNode()
for word in words:
curr = root
for c in word:
if c not in curr.children:
curr.children[c] = TrieNode()
curr = curr.children[c]
# at this point, you have a full word at curr
# you can perform more logic here to give curr an attribute if you want
return root
```