# Leetcode Coding Interview template for common code patterns python

Mani
Educating everyone with the beauty of programming!!

## Two pointers: one input, opposite ends

``````1
2
3
4
5
6
7
8
9
10
11
12
13
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

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

``````

## Sliding window

``````1
2
3
4
5
6
7
8
9
10
11
12
13
def fn(arr):
left = ans = curr = 0

for right in range(len(arr)):
# do logic here to add arr[right] to curr

while WINDOW_CONDITION_BROKEN:
# remove arr[left] from curr
left += 1

# update ans

return ans
``````

## Build a prefix sum

``````1
2
3
4
5
6
def fn(arr):
prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[-1] + arr[i])

return prefix
``````

## Efficient string building

``````1
2
3
4
5
6
7
# arr is a list of characters
def fn(arr):
ans = []
for c in arr:
ans.append(c)

return "".join(ans)
``````

In JavaScript, benchmarking shows that concatenation with += is faster than using .join().

## Linked list: fast and slow pointer

``````1
2
3
4
5
6
7
8
9
10
11
12
13
ans = 0

while fast and fast.next:
# do logic
slow = slow.next
fast = fast.next.next

return ans
}
``````

``````1
2
3
4
5
6
7
8
9
10
prev = None
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node

return prev
``````

## Find number of subarrays that fit an exact criteria

``````1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import defaultdict

def fn(arr, k):
counts = defaultdict(int)
counts[0] = 1
ans = curr = 0

for num in arr:
# do logic to change curr
ans += counts[curr - k]
counts[curr] += 1

return ans
``````

## Monotonic increasing stack

The same logic can be applied to maintain a monotonic queue.

``````1
2
3
4
5
6
7
8
9
10
11
12
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
``````

## Binary tree: DFS (recursive)

``````1
2
3
4
5
6
7
8
9
10
def dfs(root):
if not root:
return

ans = 0

# do logic
dfs(root.left)
dfs(root.right)
return ans
``````

## Binary tree: DFS (iterative)

``````1
2
3
4
5
6
7
8
9
10
11
12
13
def dfs(root):
stack = [root]
ans = 0

while stack:
node = stack.pop()
# do logic
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)

return ans
``````

## Binary tree: BFS

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import deque

def fn(root):
queue = deque([root])
ans = 0

while queue:
current_length = len(queue)
# do logic for current level

for _ in range(current_length):
node = queue.popleft()
# do logic
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)

return ans
``````

## Graph: DFS (recursive)

For the graph templates, assume the nodes are numbered from 0 to n - 1 and the graph is given as an adjacency list. Depending on the problem, you may need to convert the input into an equivalent adjacency list before using the templates.

``````1
2
3
4
5
6
7
8
9
10
11
12
13
def fn(graph):
def dfs(node):
ans = 0
# do some logic
for neighbor in graph[node]:
if neighbor not in seen:
ans += dfs(neighbor)

return ans

seen = {START_NODE}
return dfs(START_NODE)
``````

## Graph: DFS (iterative)

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fn(graph):
stack = [START_NODE]
seen = {START_NODE}
ans = 0

while stack:
node = stack.pop()
# do some logic
for neighbor in graph[node]:
if neighbor not in seen:
stack.append(neighbor)

return ans
``````

## Graph: BFS

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque

def fn(graph):
queue = deque([START_NODE])
seen = {START_NODE}
ans = 0

while queue:
node = queue.popleft()
# do some logic
for neighbor in graph[node]:
if neighbor not in seen:
queue.append(neighbor)

return ans
``````

## Find top k elements with heap

``````1
2
3
4
5
6
7
8
9
10
11
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]
``````
``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
``````

## Binary search: duplicate elements, left-most insertion point

``````1
2
3
4
5
6
7
8
9
10
11
def fn(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] >= target:
right = mid
else:
left = mid + 1

return left
``````

## Binary search: duplicate elements, right-most insertion point

``````1
2
3
4
5
6
7
8
9
10
11
def fn(arr, target):
left = 0
right = len(arr)
while left < right:
mid = (left + right) // 2
if arr[mid] > target:
right = mid
else:
left = mid + 1

return left
``````

## Binary search: for greedy problems

If looking for a minimum:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def fn(arr):
def check(x):
# this function is implemented depending on the problem
return BOOLEAN

while left <= right:
mid = (left + right) // 2
if check(mid):
right = mid - 1
else:
left = mid + 1

return left
``````

If looking for a maximum:

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def fn(arr):
def check(x):
# this function is implemented depending on the problem
return BOOLEAN

while left <= right:
mid = (left + right) // 2
if check(mid):
left = mid + 1
else:
right = mid - 1

return right
``````

## Backtracking

``````1
2
3
4
5
6
7
8
9
10
11
12
def backtrack(curr, OTHER_ARGUMENTS...):
if (BASE_CASE):
return

ans = 0
for (ITERATE_OVER_INPUT):
# modify the current state
ans += backtrack(curr, OTHER_ARGUMENTS...)
# undo the modification of the current state

return ans
``````

## Dynamic programming: top-down memoization

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
def fn(arr):
def dp(STATE):
if BASE_CASE:
return 0

if STATE in memo:
return memo[STATE]

ans = RECURRENCE_RELATION(STATE)
memo[STATE] = ans
return ans

memo = {}
return dp(STATE_FOR_WHOLE_INPUT)
``````

## Build a trie

``````1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 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
``````

We hope you like this post. If you have any questions or suggestions or need any other additional info, please comment below.

We have started a coding community for most frequently used real world coding tips. You can join us here
TipSeason Discord channel