Two Pointer
Used to find valid subarrays.
Keep two pointers, l and r. Move l or r depending on some condition.
def f(arr):
l, r = 0, len(arr) - 1
while l < r:
if l > r:
l += 1
else:
r -= 1
return l
Popular two pointer problems include 3Sum, Container With Most Water and Trapping Rainwater.
Sliding Window
Used to find valid subarrays.
To find the most [BLANK] of valid subarrays, keep two pointers l and r, the output value, and the curr value. Slide r until condition is broken, and then slide l until condition is not broken.
To find the total number of valid subarrays, fix the value of r. The number of valid windows ending at index r is equal to the size of the window.
There are n(n + 1)/2 subarrays, but a sliding window runs in O(n).
def f(arr):
output, l, curr = 0, 0
for r in range(len(arr)):
curr += arr[r]
while curr > k:
curr -= arr[l]
l += 1
output = max(output, r - l + 1)
return output
Prefix Sum
Used to efficiently calculate the sum of a subarray.
def f(arr):
prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[-1] + arr[i])
return prefix
Binary Search
Used to find an element in a sorted array.
Basic form
Used when search condition can be determined inside of the loop, without comparing to neighbors. Terminate when l > r.
def f(n, arr):
l, r = 0, len(arr) - 1
while l <= r:
m = (l + r) // 2
if arr[m] == n:
return m
elif arr[m] < n:
l = m + 1
else:
r = m - 1
return -1
Popular problems include Search a 2D Matrix.
Neighbor form
Used when neighbors are necessary to decide whether to go left or right. Terminate when l == r. There will be one value left for postprocessing.
def f(n, arr):
l, r = 0, len(arr) - 1
while l < r:
m = (l + r) // 2
if g(arr[m]):
r = mid
else:
l = mid + 1
if g(arr[l]) == n:
return l
return -1
Neighbor II form
Used when neighbors are necessary to decide whether to go left or right. Terminate when l + 1 == r. There will be two values left for postprocessing.
def f(n, arr):
l, r = 0, len(arr) - 1
while l + 1 < r:
m = (l + r) // 2
if g(arr[m]):
r = m
else:
l = m
if g(arr(l)): return l
if g(arr(r)): return r
return -1
Fast and slow pointers
Used to detect cycles in a linked list or to find the middle of a linked list. This works because the distance between slow and fast decreases by 1 every turn.
def hasCycle(head):
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
return True
return False
At the point when slow and fast meet, we have A + B = A + B + C + B. We also know that slow is half the speed of fast, so 2(A + B) = A + B + C + B. Simplifying, we get A = C. This helps us find when the cycle starts.
Topological Sort
This only works on DAGs because there no ordering if there is a cycle.
Kahn's algorithm (based on BFS)
- Keep track of free nodes that have no dependencies
- When removing the node, decrement the degree of neighboring nodes
output, free = [], []
while free:
n = free.pop()
output.append(n)
for node m adjacent to n:
decrement degree of m
if degree of m == 0:
free.append(m)
if len(output) != len(nodes):
return False # graph has at least one cycle
Depth-first search
- Choose a node
- Do a DFS on the unvisited node
- On callback, add current node to the toplogical ordering
output, temp = [], []
def dfs(node n)
if n in output:
return True
if n in temp:
return False # graph has at least one cycle
temp.append(n)
for node m adjacent to n
dfs(m)
temp.remove(n)
output.append(n)
for n in nodes:
dfs(n)
References:
Backtracking
Incrementally build candidates to the solution. Abandon a candidate ("backtrack") as soon as you determine that the candidate cannot lead to a valid solution.
Used for constraint satisfaction problems (CSP) with partial candidate solutions which can be checked relatively quickly.
def f():
output = [] # All possible solutions
partial = [] # Current partial solution
def backtrack():
nonlocal output, partial
# Base case
if is_solution(partial):
output.append(partial[:])
return
# Pruning
if invalid(partial):
return
# Try every candidate
for c in candidates:
partial.append(c) # Add to the partial
backtrack(i + 1)
partial.pop() # Remove from the partial
backtrack()
return output
Popular problems include Permutations and Combinations.
Dynamic Programming
Might be right for problems that involve looking for the optimum value or the number of ways to do something. Most importantly, future decisions depend on earlier decisions.
Top-down
Recursion made efficient by memoization.
memo = {}
def fib(n):
if n == 0 or i == 1:
return n
if n not in memo:
memo[n] = f(n - 1) + f(n - 2)
return memo[n]
Bottom-up
Starts with base cases and iteratively build up to the solution in order.
def fib(n):
if n == 0:
return 0
prev, curr = 0, 1
for i in range(2, n):
prev, curr = curr, prev + curr
return curr
Kadane's Algorithm
Used to find the maximum sum of a subarray within an array.
def f(arr):
curr_sum = 0
best_sum = float('-inf')
for n in arr:
curr_sum = max(n, curr_sum + n)
best_sum = max(best_sum, curr_sum)
return best_sum