s
Two Pointers - Opposite Ends (Converging)
Approach
Initialize pointers at opposite ends of a sorted/linear structure. Move them toward each other based on problem conditions, comparing or manipulating elements.
Key Insight
Avoids nested loops by leveraging the linear/sorted property. One pointer moves forward, one backward—never reset.
Applicable Data Structures
- Arrays
- Strings
Pseudocode
function twoPointers(arr):
left = 0
right = arr.length - 1
while left < right:
if condition_met(arr[left], arr[right]):
// Do logic
left++
else:
// Do different logic
right--
return resultComplexity
- Time: O(n)
- Space: O(1)
Edge Cases
- Empty array or single element
- All elements satisfy condition
- Pointers meet at same index
Two Pointers - Multiple Arrays/Strings (Parallel)
Approach
Initialize pointers at the start of each array/string. Advance them based on problem conditions, comparing or processing elements from both structures simultaneously. After one is exhausted, process remaining elements from the other.
Key Insight
Efficiently processes two sorted sequences in parallel without nested loops. Each pointer advances independently based on problem logic. Remaining elements are handled separately after one sequence is depleted.
Applicable Data Structures
- Arrays
- Strings
Pseudocode
function fn(arr1, arr2):
i = j = 0
while i < arr1.length AND j < arr2.length:
// Do logic
// Move one or both pointers:
// i++, j++, or both
// Handle remaining elements
while i < arr1.length:
// Do logic
i++
while j < arr2.length:
// Do logic
j++
return resultComplexity
- Time: O(n + m) where n and m are lengths of arr1 and arr2
- Space: O(1)
Edge Cases
- One array/string is empty
- Arrays/strings are different lengths
- All elements processed in first while loop
- Remaining elements after one sequence is exhausted
Sliding Window - Dynamic Window
Approach
Maintain a dynamic window with left and right pointers. Expand the window by moving right, then contract from left when a condition is violated. Track the desired metric (max/min window size, etc.) as you adjust the window.
Key Insight
Avoids recomputing values from scratch for overlapping windows. By maintaining a running calculation (curr) and adjusting incrementally, you process the data in a single pass rather than nested loops.
Applicable Data Structures
- Arrays
- Strings
Pseudocode
function fn(nums, k):
left = 0
curr = 0
answer = 0
for right = 0 to nums.length - 1:
curr += nums[right]
while curr > k:
curr -= nums[left]
left++
answer = max(answer, right - left + 1)
return answerComplexity
- Time: O(n)
- Space: O(1)
Edge Cases
- Empty array
- Single element
- All elements violate condition
- Window size of 1
Sliding Window - Fixed Window
Approach
Initialize a window of fixed size k. Build the first window, then slide it one position at a time by adding the next element and removing the leftmost element. Update the answer as the window slides.
Key Insight
Fixed window size eliminates the need for a shrinking condition. Simply add one element and remove one element per iteration, maintaining constant window size. This is simpler than dynamic sliding window.
Applicable Data Structures
- Arrays
- Strings
Pseudocode
function fn(arr, k):
curr = some data to track the window
// Build first window
for i = 0 to k - 1:
Do something with curr to build first window
ans = curr
// Slide the window
for i = k to arr.length - 1:
Add arr[i] to window
Remove arr[i - k] from window
Update ans
return ansComplexity
- Time: O(n)
- Space: O(1)
Edge Cases
- Array length equals k
- Array length less than k
- All elements are the same
- Window only processes one element
Prefix Sum
Approach
Build an array where each element represents the cumulative sum of all elements up to that index. Each element is the current element plus the previous cumulative sum.
Key Insight
Enables O(1) range sum queries. Instead of recalculating the sum from index i to j, compute prefix[j] - prefix[i-1]. Trades space for speed on repeated sum queries.
Applicable Data Structures
- Arrays
Pseudocode
function buildPrefixSum(nums):
prefix = [nums[0]]
for i = 1 to nums.length - 1:
prefix.append(nums[i] + prefix[i - 1])
return prefix# Retrieve sum between index `i` and `j` `prefix[j] - prefix[i] + nums[i]`
Complexity
Time: O(n)
Space: O(n)
Edge Cases
- Single element array
- Empty array
- Negative numbers
- Array with zeros
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 -1
