What is the key insight for the Two Sum (HashMap) pattern?
For each number, check if (target - number) exists
This approach uses a hashmap to track seen numbers and their indices.
What is the template for the Two Sum (HashMap) pattern?
def twoSum(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
This function returns the indices of the two numbers that add up to the target.
What is the key insight for the Sliding Window (Set) pattern?
Expand window with right pointer, shrink when duplicate found
This technique is useful for finding the longest substring without repeating characters.
What is the template for the Sliding Window (Set) pattern?
def lengthOfLongestSubstring(s):
seen = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in seen:
seen.remove(s[left])
left += 1
seen.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
This function returns the length of the longest substring without repeating characters.
What is the key insight for the Valid Parentheses (Stack) pattern?
Push opening brackets, pop and match closing brackets
This method ensures that all brackets are balanced.
What is the template for the Valid Parentheses (Stack) pattern?
def isValid(s):
stack = []
mapping = {‘)’: ‘(‘, ‘}’: ‘{‘, ‘]’: ‘[’}
for char in s:
if char in mapping:
top = stack.pop() if stack else ‘#’
if mapping[char] != top:
return False
else:
stack.append(char)
return not stack
This function checks if the input string of brackets is valid.
What is the key insight for the Two Pointers (Sorted Array) pattern?
Move left pointer up if sum too small, right pointer down if too large
This approach is efficient for finding pairs in a sorted array.
What is the template for the Two Pointers (Sorted Array) pattern when 1 indexed (as seen in two sum II)?
def twoSum(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
curr_sum = numbers[left] + numbers[right]
if curr_sum == target:
return [left + 1, right + 1]
elif curr_sum < target:
left += 1
else:
right -= 1
This function returns the indices of the two numbers that add up to the target in a sorted array.
What is the key insight for the BFS (Tree Level Order) pattern?
Use queue, process all nodes at current level before next
This method is used for level order traversal of a tree.
What is the template for the BFS (Tree Level Order) pattern?
from collections import deque
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
This function returns the values of the tree nodes level by level.
What is the key insight for the DFS (Tree Recursion) pattern?
Recursive function that processes current node then children
This method is useful for traversing trees and validating properties.
What is the template for the DFS (Tree Recursion) pattern?
def dfs(node):
if not node:
return
result = node.val
left_result = dfs(node.left)
right_result = dfs(node.right)
return result
This function processes each node in a tree recursively.
What is the key insight for Kadane’s Algorithm?
Track current sum, reset to 0 when negative
This algorithm is used to find the maximum sum subarray.
What is the template for Kadane’s Algorithm?
def maxSubArray(nums):
max_sum = nums[0]
current_sum = nums[0]
for i in range(1, len(nums)):
current_sum = max(nums[i], current_sum + nums[i])
max_sum = max(max_sum, current_sum)
return max_sum
This function returns the maximum sum of a contiguous subarray.
What is the key insight for the Merge Intervals pattern?
Sort by start time, merge if current overlaps with last
This approach is effective for merging overlapping intervals.
What is the template for the Merge Intervals pattern?
def merge(intervals):
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for current in intervals[1:]:
last = merged[-1]
if current[0] <= last[1]:
last[1] = max(last[1], current[1])
else:
merged.append(current)
return merged
This function returns a list of merged intervals.
What is the key insight for the Backtracking pattern?
Build solution incrementally, backtrack when needed
This technique is useful for generating combinations, permutations, and subsets.
What is the template for the Backtracking pattern?
def backtrack(result, temp, nums, start):
result.append(temp[:]) # Make a copy
for i in range(start, len(nums)):
temp.append(nums[i])
backtrack(result, temp, nums, i + 1)
temp.pop() # Backtrack
This function generates all combinations of the input list.
What is the key insight for the Binary Search pattern?
Divide search space in half each iteration
This method is efficient for finding a target in a sorted array.
What is the template for the Binary Search pattern?
def binarySearch(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
This function returns the index of the target in the sorted array or -1 if not found.
What is the common import for using a deque in Python?
from collections import deque
Deques are useful for implementing queues and stacks.
How do you convert a string to a list in Python?
chars = list(s)
This operation splits the string into its constituent characters.
How do you join a list to a string in Python?
s = ‘‘.join(chars)
This operation combines the list elements into a single string.
What is the syntax for integer division in Python?
a // b
This operation rounds down the result of the division.
