Leet Code Algorithms Flashcards
Describe the two pointers algorithm with one input where the pointers start at opposite ends
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 ansDescribe the two pointers algorithm with two inputs to exhaust both arrays
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 ansDescribe the sliding window algorithm
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
Time complexity O(n). The inner loop has an amortized time complexity of O(1)
Describe the sliding window algorithm with a fixed window
def fixed_window(arr, k) -> int:
sum = # some data to track
# Build first window
for i in range(k):
# logic to build first window
ans = # answer variable
# Build next windows
for i in range(k, len(nums)):
# add arr[i] to window
# remove arr[i-k] from window
# update answer
return ansDescribe the prefix sum algorithm
def fn(arr):
prefix = [arr[0]]
for i in range(1, len(arr)):
prefix.append(prefix[-1] + arr[i])
return prefix
The sum between index i and j isprefix[j] - prefix[i-1]
orprefix[j] - prefix[i] + nums[i]
Describe an algorithm to efficiently build a string
# arr is a list of characters
def fn(arr):
ans = []
for c in arr:
ans.append(c)
return "".join(ans)Describe an algorithm to find the number of subarrays that fit an exact criteria
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 ansDescribe an algorithm to implement fast and slow pointers in a linked list
def fn(head):
slow = head
fast = head
ans = 0
while fast and fast.next:
# do logic
slow = slow.next
fast = fast.next.next
return ansDescribe an algorithm to return the middle of a linked list
def fn(head):
slow = head
fast = head
while slow and fast.next:
slow = slow.next
fast = fast.next.next
return slow.valDescribe an algorithm to find cycles in a linked list
def fn(head):
slow = head
fast = head
while slow and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseDescribe an algorithm to reverse a linked list
def fn(head):
curr = head
prev = None
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prevDescribe an algorithm to build/maintain a monotonic increasing stack
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 ansDescribe and algorithm to perform a DFS (recursive) on a binary tree
def dfs(root):
if not root:
return
ans = 0
# do logic
dfs(root.left)
dfs(root.right)
return ansDescribe an algorithm to perform a DFS (iterative) on a binary tree
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 ansDescribe and algorithm to perform preorder Depth First Search (DFS) on a binary tree
def preorder_dfs(node):
if node == None:
return
print(node.value)
preorder_dfs(node.left)
preorder_dfs(node.right)
returnDescribe and algorithm to perform inorder Depth First Search (DFS) on a binary tree
def inorder_dfs(node):
if node == None:
return
inorder_dfs(node.left)
print(node.value)
inorder_dfs(node.right)
returnDescribe and algorithm to perform postorder Depth First Search (DFS) on a binary tree
def postorder_dfs(node):
if node == None:
return
postorder_dfs(node.left)
postorder_dfs(node.right)
print(node.value)
returnDescribe an algorithm to perform Breadth First Search (BFS) on a binary tree
from collections import deque
def bfs(root):
queue = deque([root])
while queue:
nodes_in_current_level = len(queue)
# Do some logic on the current level
for _ in range(nodes_in_current_level):
node = queue.popleft()
# Do some logic on the current node
print(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)Describe an algorithm to insert a value into a Binary Search Tree (BST)
def insertIntoBST(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insertInotBST(root.left, val)
else:
root.right = insertInotBST(root.right, val)
return rootDescribe an algorithm to build an adjacency list given an array of directed edges
from collections import defaultdict
def build_graph(edges):
graph = defaultdict(list)
for x, y in edges:
graph[x].append(y)
# uncomment if undirected
#graph[y].append(x)
return graphDescribe an algorithm to build a graph given an adjacency matrix
from collections import defaultdict
def build_graph_from_adjacency_matrix(adj_matrix):
graph = defaultdict(list)
n = len(adj_matrix)
m = len(adj_matrix[0])
for i in range(n):
for j in range(m):
if adj_matrix[i][j] == 1:
graph[i].append(j)
return graphDescribe an algorithm to perform a Depth First Search (DFS) on a graph
# build graph
seen = set()
def dfs(node):
for neighbor in graph[node]:
if neighbor not in seen:
print(neighbor)
seen.add(neighbor)
dfs(neighbor)
for i in range(len(graph)):
if i not in seen:
print(i)
seen.add(i)
dfs(i)Describe and algorithm to perform a Depth First Search (DFS) to find the number of islands given a a binary matrix
def island_count(grid):
m = len(grid)
n = len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
seen = set()
islands = 0
def is_valid(row: int, col: int) -> bool:
return 0 <= row < m and 0 <= col < n and grid[row][col] == 1:
def dfs(row, col):
size = 1
for dx, dy in directions:
next_row, next_col = row + dy, col + dx
if is_valid(next_row, next_col) and (next_row, next_col) not in seen:
seen.add((next_row, next_col))
size += dfs(next_row, next_col)
return size
for row in range(m):
for col in range(n):
if (row, col) not in seen and is_valid(row,col):
islands += 1
seen.add((row,col))
dfs(row,col)
return islandsDescribe an algorithm to perform a Breadth First Search (BFS) to find the shortest path given a a binary matrix
from collections import deque
def shortest_path_binary_matrix(grid):
if grid[0][0] == 1:
return -1
n = len(grid)
m = len(grid[0])
seen = set((0,0))
queue = deque([(0,0,1)]) # right, left, steps
directions = [
(1,0),
(1,1),
(0,1),
(-1,1),
(-1,0),
(-1,-1),
(0,-1),
(1,-1)
]
def is_valid(row, col):
return 0 <= row < m and 0 <= col < n and grid[row][col] == 0
while queue:
row, col, steps = queue.popleft()
if (row, col) == (n-1, m-1):
return steps
for dx, dy in directions:
next_row, next_col = row + dy, col + dx
if is_valid(next_row, next_col) and (next_row, next_col) not in seen:
seen.add((next_row, next_col))
queue.append((next_row, next_col, steps + 1))
return -1Describe the binary search algorithm for a sorted array with no duplicates and give it’s time and space complexity
Time: O(log n)
Space: O(1)
def binary_search(arr, target):
left = 0
right = len(arr) - 1
while left <= right:
mid = (right + left) // 2
print(mid)
if arr[mid] == target:
# Found
return
if arr[mid] > target:
right = mid -1
else:
left = mid + 1
return left
Describe the binary search algorithm for an array that contains duplicates and returns the left-most index. Also give it’s time and space complexity
Time: O(log n)
Space: O(1)
def binary_search_first_pos(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
Describe the binary search algorithm for an array that contains duplicates and returns the right-most insertion point. Also give it’s time and space complexity
Time: O(log n)
Space: O(1)
def binary_search_last_pos(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
Describe the generic backtracking algorithm
def backtrack(curr, OTHER_ARGUMENTS...):
if (BASE_CASE):
# modify the answer
return
ans = 0
for (ITERATE_OVER_INPUT):
# modify the current state
ans += backtrack(curr, OTHER_ARGUMENTS...)
# undo the modification of the current state
return ansDescribe a generic trie algorithm
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
