DSA Placement Preparation Notes

Table of Contents
• Arrays
• Strings
• Linked Lists
• Stacks and Queues
• Hash Tables
• Bit Manipulation
• Two Pointers
• Sliding Window
• Binary Search
• Heap and Priority Queue
• Graphs
• Trees
• Tries
• Dynamic Programming
• Backtracking

Arrays
Arrays are collections of elements stored in contiguous memory locations. This allows O(1) random access
by index and efficient iteration. Arrays are foundational for many algorithmic techniques (e.g., prefix sums,
sliding windows) and often serve as the base structure for dynamic programming table computations. They
are suitable for problems requiring fast lookups and iterations, though insertions/deletions can be costly
due to shifting elements.

Common uses/patterns: - Constant time access by index, easy iteration over elements
- Implementing sliding window and prefix sum computations
- Serving as backing storage for other structures (heaps, hash table buckets, DP states)

Move Zeroes (Easy)

def moveZeroes(nums):
last_non_zero = 0
for i in range(len(nums)):
if nums[i] != 0:
# Swap the current element with the last found non-zero
nums[last_non_zero], nums[i] = nums[i], nums[last_non_zero]
last_non_zero += 1

1
Majority Element (Easy)

def majorityElement(nums):
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
return candidate

Remove Duplicates from Sorted Array (Easy)

def removeDuplicates(nums):
if not nums:
return 0
write_index = 1
for i in range(1, len(nums)):
if nums[i] != nums[i - 1]:
nums[write_index] = nums[i]
write_index += 1
return write_index

Best Time to Buy and Sell Stock (Easy)

def maxProfit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price
elif price - min_price > max_profit:
max_profit = price - min_price
return max_profit

Rotate Array (Medium)

Explanation: To rotate an array by k steps, we can take the last k elements and bring them to the front. One
efficient method is to use Python slicing: first compute k %= n to handle cases where k is larger than the
array length, then set nums[:] = nums[-k:] + nums[:-k] . This operation rotates the array in O(n)
time and uses O(n) space (or in-place with careful reversal techniques).

2
 def rotate(nums, k):
n = len(nums)
k %= n
# Place the last k elements in front and the rest afterwards
nums[:] = nums[-k:] + nums[:-k]

Product of Array Except Self (Medium)

Explanation: We can compute the product of all elements except self by using a prefix and suffix
multiplication approach. First, accumulate a running product from the left, storing results in an output
array. Then accumulate from the right, multiplying into the output array. This yields the final product for
each index without ever multiplying that index’s value by itself (and without using division). The time
complexity is O(n) and space complexity O(n) (or O(1) extra if output array is not counted).

def productExceptSelf(nums):
n = len(nums)
res = [1] * n
# Calculate prefix products for each index
left_prod = 1
for i in range(n):
res[i] = left_prod
left_prod *= nums[i]
# Multiply with suffix products
right_prod = 1
for i in range(n - 1, -1, -1):
res[i] *= right_prod
right_prod *= nums[i]
return res

Best Time to Buy and Sell Stock II (Medium)

Explanation: In the unlimited transactions version of the stock profit problem, the optimal strategy is to sum
up all increasing price differences. This greedy approach simply accumulates
prices[i] - prices[i-1] for every pair where a profit can be made (i.e., price[i] > price[i-1]). This
yields the maximum profit in O(n) time by effectively buying before every rise and selling at every peak.

def maxProfit(prices):
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profit

Number of Zero-Filled Subarrays (Medium)

Explanation: Count the number of subarrays consisting only of 0s by iterating through the array and

3
counting consecutive zeros. Each time we encounter a zero, increment a counter; for a run of m consecutive
zeros, it contributes subarrays of lengths 1 through m. We can accumulate in a single pass: every time we
see a zero, count += 1 and add that to a result accumulator (because a streak of length m adds m new
subarrays ending at the current position). Reset the count when a non-zero is encountered.

def zeroFilledSubarray(nums):
total = 0
consecutive_zeros = 0
for num in nums:
if num == 0:
consecutive_zeros += 1
total += consecutive_zeros
else:
consecutive_zeros = 0
return total

Increasing Triplet Subsequence (Medium)

Explanation: This problem asks if there exists an increasing sequence of length 3 in the array. We can solve it
greedily by tracking the smallest and second smallest values seen so far. Iterate through the numbers,
update the smallest ( first ) if current number is smaller, else if it’s bigger than first but smaller than
the second smallest ( second ), update second . If we find a number larger than both first and
second , then first < second < current forms an increasing triplet, and we return True.

def increasingTriplet(nums):
first = second = float('inf')
for num in nums:
if num <= first:
first = num
elif num <= second:
second = num
else:
# num is greater than first and second, triplet found
return True
return False

First Missing Positive (Hard)

Explanation: To find the smallest missing positive integer, we can use the array indices as a hash. The
approach is to place each number in its “correct” index position (i.e., value v should ideally be at index
v-1 ) by swapping elements in-place. We iterate over the array and swap elements until every eligible
number is either out of range or in the correct position. Then, we scan again to find the first index i where
nums[i] != i+1 – that index+1 is the smallest missing positive. If all positions are correct, the answer is
length+1. This works in O(n) time and O(1) space.

4
 def firstMissingPositive(nums):
n = len(nums)
# Place each number in its correct index if possible
for i in range(n):
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# Swap nums[i] with the element at its target position
target_idx = nums[i] - 1
nums[i], nums[target_idx] = nums[target_idx], nums[i]
# Find the first position that is incorrect
for i in range(n):
if nums[i] != i + 1:
return i + 1
return n + 1

Strings
Strings are sequences of characters, typically used to represent text. Common string operations include
concatenation, slicing, searching for substrings, and parsing. String problems often involve techniques such
as two-pointer scans for palindrome checks, hash maps for frequency counting (e.g., anagrams), or
dynamic programming for subsequence/substring problems. Pattern recognition (like identifying
palindromes or repeating patterns) is key in many string challenges.

Common uses/patterns: - Text processing (reversal, concatenation, splitting, pattern matching)

- Character frequency counting for anagrams or comparisons
- Two-pointer techniques for palindrome checking or substring searches
- Dynamic programming for substrings/subsequences (especially when optimal substructure is present)

Valid Anagram (Easy)

def isAnagram(s, t):

if len(s) != len(t):
return False
# Count frequency of each character in s
freq = {}
for ch in s:
freq[ch] = freq.get(ch, 0) + 1
# Decrement frequencies using characters in t
for ch in t:
if ch not in freq or freq[ch] == 0:
return False
freq[ch] -= 1
return True

Valid Palindrome (Easy)

5
 def isPalindrome(s):
i, j = 0, len(s) - 1
while i < j:
# Move i and j to skip non-alphanumeric characters
if not s[i].isalnum():
i += 1
continue
if not s[j].isalnum():
j -= 1
continue
if s[i].lower() != s[j].lower():
return False
i += 1
j -= 1
return True

Longest Common Prefix (Easy)

def longestCommonPrefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs[1:]:
# Shorten the prefix until it matches the start of s
while not s.startswith(prefix):
prefix = prefix[:-1]
if prefix == "":
return ""
return prefix

Reverse Words in a String (Medium)

Explanation: To reverse the order of words in a string (separated by spaces), we can split the string by spaces
to get the words, filter out any empty words (to handle multiple spaces), and then join them in reverse
order. This straightforward approach runs in O(n) time. In-place reversal is also possible by trimming spaces
and reversing the entire string and then each word, but the split/join method is simplest in Python.

def reverseWords(s):
words = s.split()
# Filter out any empty strings (split takes care of trimming by default)
return " ".join(reversed(words))

Longest Palindromic Substring (Medium)

Explanation: We can find the longest palindromic substring by expanding around each possible center. For

6
each index (and each pair between indices for even-length palindromes), expand outward while the
characters match. Track the longest palindrome found. This approach is O(n^2) in the worst case but is
sufficient for typical input sizes. Dynamic programming could also be used (filling a table for substrings),
but the center-expanding method is more space-efficient.

def longestPalindrome(s):
res = ""
for center in range(len(s)):
# odd length palindrome
l, r = center, center
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1
r += 1
# even length palindrome
l, r = center, center + 1
while l >= 0 and r < len(s) and s[l] == s[r]:
if r - l + 1 > len(res):
res = s[l:r+1]
l -= 1
r += 1
return res

Group Anagrams (Medium)

Explanation: To group anagrams, we can use a hash map where the key is a canonical representation of the
anagram group and the value is a list of words in that group. A simple canonical key is the sorted string of
characters – all anagrams will result in the same sorted key. We iterate over each word, sort its letters to
form the key, then append the word to the list for that key. Finally, return all the grouped lists. This runs in
O(n * m log m) where m is word length (from sorting each word).

def groupAnagrams(strs):
anagram_map = {}
for word in strs:
key = "".join(sorted(word))
if key not in anagram_map:
anagram_map[key] = []
anagram_map[key].append(word)
return list(anagram_map.values())

Linked Lists
A linked list is a linear data structure where elements (nodes) contain a value and a pointer/reference to the
next node. Unlike arrays, linked lists allow efficient insertions or deletions from the middle of the list if you

7
have a pointer to the node (O(1) for pointer manipulations), but they do not allow constant-time random
access. Common patterns include two-pointer techniques (slow/fast pointers) for cycle detection or finding
the middle, and careful pointer manipulation for list reversal or merging.

Common uses/patterns: - Efficient insertion and deletion when only node references are needed (no
shifting like arrays)
- Two-pointer techniques (fast/slow pointers) for finding midpoint or loops
- Stack-like behavior using recursion or reversal due to pointer structure
- Implementing abstract data types like stacks, queues, or adjacency lists for graphs

Reverse Linked List (Easy)

def reverseList(head):
prev = None
curr = head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev

Merge Two Sorted Lists (Easy)

def mergeTwoLists(l1, l2):

dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val < l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
# Attach any remaining nodes
tail.next = l1 if l1 else l2
return dummy.next

Linked List Cycle (Easy)

def hasCycle(head):
slow, fast = head, head

8
 while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False

Remove Nth Node from End of List (Medium)

Explanation: To remove the k-th node from the end, we can use two pointers spaced k apart. First, advance a
fast pointer k steps. Then move both slow and fast together until fast reaches the end. The
slow pointer will then be right before the node to remove. We adjust pointers to skip the target node.
Using a dummy head simplifies edge cases (like removing the first node). This approach runs in O(n) time
with O(1) extra space.

def removeNthFromEnd(head, n):

dummy = ListNode(0)
dummy.next = head
slow, fast = dummy, dummy
# Move fast n+1 steps to get the gap between slow and fast
for _ in range(n + 1):
fast = fast.next
while fast:
slow = slow.next
fast = fast.next
# Now slow.next is the node to remove
slow.next = slow.next.next
return dummy.next

Reorder List (Medium)

Explanation: Reordering a list in the required [L0, L_n, L1, L_{n-1}, ...] pattern can be done in three steps: find
the middle of the list, reverse the second half, then merge the two halves alternately. Finding the middle is
done via slow/fast pointers. Reversing uses the standard method. Merging is done by weaving nodes from
the two halves one by one. This in-place algorithm runs in O(n) time.

def reorderList(head):
if not head or not head.next:
return
# Find middle (end of first half)
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
second_half = slow.next
slow.next = None # split the list into two halves

9
 # Reverse second half
prev = None
curr = second_half
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
second_half = prev
# Merge two halves
first, second = head, second_half
while second:
tmp1 = first.next
tmp2 = second.next
first.next = second
second.next = tmp1
first = tmp1
second = tmp2

Palindrome Linked List (Easy)

def isPalindrome(head):
# Find middle
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Reverse second half
prev = None
curr = slow
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
# Compare first half and reversed second half
p1, p2 = head, prev
while p2:
if p1.val != p2.val:
return False
p1 = p1.next
p2 = p2.next
return True

Intersection of Two Linked Lists (Easy)

10
 def getIntersectionNode(headA, headB):
if not headA or not headB:
return None
pA, pB = headA, headB
# Traverse both lists; when one ends, switch to the other head.
# They will meet at intersection or at end (None).
while pA is not pB:
pA = pA.next if pA else headB
pB = pB.next if pB else headA
return pA # either the intersection node or None

Linked List Cycle II (Medium)

Explanation: To find the starting node of a cycle (if one exists), first detect the cycle using slow/fast pointers.
When a cycle is detected (slow == fast), reset one pointer to the head and then move both slow and fast one
step at a time. They will meet at the cycle start. This works because the distance from head to cycle start
equals the distance from meeting point to cycle start given the mathematics of cycle lengths. The algorithm
runs in O(n) time and uses O(1) space.

def detectCycle(head):
slow, fast = head, head
# Detect if a cycle exists
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# Cycle detected, find the start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None

Add Two Numbers (Medium)

Explanation: Given two numbers represented by linked lists (each node is a digit, and the digits are in
reverse order), we add them digit by digit simulating the grade-school addition with a carry. We traverse
both lists simultaneously, summing corresponding digits and a carry from the previous step. A new node is
created for each sum result digit. If a carry remains at the end, we add a new node for it. This runs in
O(max(m, n)) time for lists of length m and n.

def addTwoNumbers(l1, l2):

dummy = ListNode(0)
current = dummy

11
 carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
total = val1 + val2 + carry
carry = total // 10
current.next = ListNode(total % 10)
current = current.next
if l1: l1 = l1.next
if l2: l2 = l2.next
return dummy.next

Stacks and Queues

Stacks and queues are abstract data types that store elements in specific orders. A stack follows Last-In-
First-Out (LIFO) ordering, where elements are added and removed from the top. Common stack operations
are push, pop, and peek. A queue follows First-In-First-Out (FIFO) ordering, with operations to enqueue
(add to back) and dequeue (remove from front). These structures are often used to solve problems involving
recent elements (stack for balanced symbols or recursion simulation) or breadth-first traversal (queue for
BFS in trees/graphs). Monotonic stacks/queues are used to maintain a structure that only keeps elements in
increasing or decreasing order, which is useful for certain range problems.

Common uses/patterns: - Stacks: Parsing and evaluating expressions, backtracking recursion stack, undo
operations, checking balanced parentheses, monotonic stack for next greater/smaller element problems
- Queues: BFS traversal in trees/graphs, scheduling tasks, buffering data streams, implementing caches
(with deque), sliding window (with deque to maintain max/min)
- Double-ended queues (deque): Supports adding/removing from both ends, used in problems like sliding
window maximum or designing LRU cache (with queue behavior)

Valid Parentheses (Easy)

def isValid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
stack.append(ch)
else:
# If it's a closing bracket, stack must not be empty and top must
match
if not stack or stack[-1] != pairs.get(ch):
return False
stack.pop()
return len(stack) == 0

12
Min Stack (Easy)

class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # keep track of current minimum

def push(self, x: int) -> None:

self.stack.append(x)
# If new element is smaller or equal to current min, push it onto
min_stack
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)

def pop(self) -> None:

val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()

def top(self) -> int:

return self.stack[-1]

def getMin(self) -> int:

return self.min_stack[-1]

Implement Queue using Stacks (Easy)

class MyQueue:
def __init__(self):
self.in_stack = []
self.out_stack = []

def push(self, x: int) -> None:

self.in_stack.append(x)

def pop(self) -> int:

self.peek() # Ensure out_stack has the current elements
return self.out_stack.pop()

def peek(self) -> int:

if not self.out_stack:
while self.in_stack:
self.out_stack.append(self.in_stack.pop())
return self.out_stack[-1]

13
 def empty(self) -> bool:
return not self.in_stack and not self.out_stack

Next Greater Element I (Easy)

def nextGreaterElement(nums1, nums2):

# Find next greater for each element in nums2 using a stack
next_greater = {}
stack = []
for x in nums2:
while stack and x > stack[-1]:
val = stack.pop()
next_greater[val] = x
stack.append(x)
# For those elements with no greater element, they remain missing in map
return [next_greater.get(x, -1) for x in nums1]

Daily Temperatures (Medium)

Explanation: This problem asks for the next day with a warmer temperature for each day. A monotonic
decreasing stack of indices can be used: traverse the temperatures, and maintain a stack of indices of days
with decreasing temperatures. When a new day’s temperature is higher than the temperature at the top of
the stack, pop from the stack and calculate the difference in indices (that gives the wait days for that
popped day). Push each day index onto the stack. This yields an O(n) solution.

def dailyTemperatures(T):
n = len(T)
result = [0] * n
stack = [] # stores indices of days
for i, temp in enumerate(T):
while stack and T[stack[-1]] < temp:
prev_i = stack.pop()
result[prev_i] = i - prev_i
stack.append(i)
return result

Evaluate Reverse Polish Notation (Medium)

Explanation: In Reverse Polish Notation (postfix expression), operators come after their operands. We can
use a stack: traverse tokens, push numbers onto the stack, and when an operator is encountered, pop the
top two numbers, apply the operator, and push the result back. Continue until the expression ends; the
result will be the lone number on the stack.

def evalRPN(tokens):
stack = []

14
 for token in tokens:
if token not in ["+", "-", "*", "/"]:
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
# Python's int() truncates toward 0 for negative values as
required
stack.append(int(a / b))
return stack[0]

Largest Rectangle in Histogram (Hard)

Explanation: To find the largest rectangle in a histogram, we use a stack to keep track of indices of bars in
increasing height order. As we scan through heights, when we encounter a bar that is lower than the stack’s
top, it means the height at the top can’t extend further right. We pop the top index and calculate the area of
the rectangle with height = height[top] and width = current_index - new_stack_top_index - 1 (if stack is
empty after pop, use current_index as width). We do this until the stack is either empty or has a smaller
height at top than the current bar, then push current index. After processing all bars, we pop any remaining
bars and calculate area similarly using full length as right boundary. This algorithm runs in O(n) time.

def largestRectangleArea(heights):
stack = []
max_area = 0
for i, h in enumerate(heights):
# If current bar is lower than stack's top bar, pop and calculate area
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
# Width is either i (if stack empty) or i - stack[-1] - 1
left_index = stack[-1] if stack else -1
width = i - left_index - 1
max_area = max(max_area, height * width)
stack.append(i)
# Clear remaining bars
n = len(heights)
while stack:
height = heights[stack.pop()]
left_index = stack[-1] if stack else -1
width = n - left_index - 1

15
 max_area = max(max_area, height * width)
return max_area

Hash Tables
A hash table (or dictionary/map) stores key-value pairs with average O(1) insertion, deletion, and lookup.
Hash tables are very useful for counting frequencies, caching results, or detecting duplicates, among other
uses. In interview problems, hash maps often help to reduce time complexity by trading space for speed,
such as checking if a complement or remainder has been seen before, grouping items by computed keys, or
memoization in DP/backtracking.

Common uses/patterns: - Counting occurrences or frequencies of elements (e.g., anagram checks,

majority vote)
- Quick existence checks (e.g., two-sum complements, seen elements in cycles)
- Caching computed results (memoization for expensive function calls or DP)
- Grouping or indexing by computed key (e.g., grouping anagrams by sorted key, bucketizing values)

Two Sum (Easy)

def twoSum(nums, target):

seen = {} # maps number -> index
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i

Contains Duplicate (Easy)

def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False

Valid Sudoku (Medium)

Explanation: Use hash sets to keep track of seen numbers in each row, each column, and each 3x3 subgrid
of a Sudoku board. Iterate through every cell; for a filled cell, construct keys like (num in row r) ,
(num in col c) , (num in subgrid g) . If any key is seen twice, the Sudoku is invalid. If no conflicts
are found, it’s valid. This approach checks all 81 cells and uses O(1) average insert/check in sets, yielding
O(81) ~ O(1) time in practice, with additional space for the sets.

16
 def isValidSudoku(board):
seen = set()
for r in range(9):
for c in range(9):
val = board[r][c]
if val == ".":
continue
# Compose keys for row, col and subgrid
row_key = (r, val)
col_key = (c, val)
box_key = (r//3, c//3, val)
if row_key in seen or col_key in seen or box_key in seen:
return False
seen.add(row_key)
seen.add(col_key)
seen.add(box_key)
return True

Longest Consecutive Sequence (Medium)

Explanation: Given an unsorted array, to find the length of the longest consecutive integer sequence, we can
use a hash set of all numbers for O(1) lookups. For each number, only start counting if it’s the beginning of a
sequence (i.e., num-1 is not in the set). Then count how long the sequence goes ( num, num+1,
num+2, ... ). Track the maximum length found. This approach is O(n) time since each sequence is
counted once and each lookup is O(1).

def longestConsecutive(nums):
num_set = set(nums)
longest = 0
for num in num_set:
if num - 1 not in num_set:
# only start counting if num is the start of a sequence
length = 1
curr = num
while curr + 1 in num_set:
curr += 1
length += 1
longest = max(longest, length)
return longest

Subarray Sum Equals K (Medium)

Explanation: Use a running prefix sum and hash map to count how often a particular prefix sum occurs. As
we iterate through the array computing the cumulative sum, at each index the number of subarrays ending
at that index with sum = K can be found by checking if (current_sum - K) has appeared as a prefix sum
before. We maintain a map of prefix sums to counts. Initialize with {0:1} to handle subarrays starting from

17
index 0. This yields an O(n) solution.

def subarraySum(nums, k):

prefix_counts = {0: 1}
curr_sum = 0
count = 0
for num in nums:
curr_sum += num
# If there was a prefix sum that is curr_sum - k, then subarray between
that prefix and current index sums to k
if curr_sum - k in prefix_counts:
count += prefix_counts[curr_sum - k]
# Update the count of current prefix sum
prefix_counts[curr_sum] = prefix_counts.get(curr_sum, 0) + 1
return count

Happy Number (Easy)

Explanation: A number is "happy" if repeatedly replacing it by the sum of the squares of its digits eventually
leads to 1. To detect loops (unhappy numbers cycle forever), use a set to store seen numbers. At each step,
compute the next number. If it becomes 1, return True. If it repeats a previous number (especially 4 is
known to appear in the cycle of unhappy numbers), return False.

def isHappy(n):
def next_number(x):
total = 0
while x:
x, digit = divmod(x, 10)
total += digit * digit
return total
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = next_number(n)
return n == 1

Bit Manipulation
Bit manipulation techniques use operations on binary representations of numbers (using bitwise AND, OR,
XOR, shifts, etc.). These techniques are powerful for optimizing certain calculations, toggling flags, or
solving problems involving binary data or subsets. Common patterns include using XOR to cancel out
paired values, using bit masks to represent subsets or states, and shifting bits for multiplication/division by
powers of two.

18
Common uses/patterns: - XOR for finding unique elements (because x ^ x = 0 and x ^ 0 = x)
- Bit masks for subset generation or representing a set of boolean values in an integer
- Checking or setting specific bits (using shifts and AND/OR)
- Efficient multiplication/division by 2 using left/right shifts
- Bit DP for problems like Traveling Salesman (using an integer to represent visited set)

Single Number (Easy)

def singleNumber(nums):
result = 0
for num in nums:
result ^= num # XOR will cancel out all paired numbers
return result

Missing Number (Easy)

def missingNumber(nums):
n = len(nums)
total_xor = 0
for i in range(n + 1):
total_xor ^= i
for num in nums:
total_xor ^= num
return total_xor

(The above uses XOR to cancel out all present numbers from the complete range [0..n], leaving the missing
number. Alternatively, summation formula or Gauss formula could be used.)

Number of 1 Bits (Easy)

def hammingWeight(n):
count = 0
while n:
count += n & 1 # add the least significant bit
n >>= 1 # shift right
return count

Counting Bits (Easy)

def countBits(n):
# DP approach: use the relation bits[i] = bits[i>>1] + (i & 1)
bits = [0] * (n + 1)

19
 for i in range(1, n + 1):
bits[i] = bits[i >> 1] + (i & 1)
return bits

Reverse Bits (Easy)

def reverseBits(n):
result = 0
for _ in range(32): # assuming 32-bit integer
result <<= 1
result |= (n & 1)
n >>= 1
return result

Single Number II (Medium)

Explanation: In an array where every element appears three times except one appears once, we can use bit
counting. One approach is to maintain two bitmask variables that accumulate bits appearing mod 3 (using
bitwise operations to simulate a finite state machine for each bit position). A simpler conceptual approach:
count the number of 1s in each bit position across all numbers, and take each count mod 3. The remainder
is the bit of the unique number. This results in O(n) time and fixed O(1) space (just 32 counters).

def singleNumber(nums):
result = 0
for bit in range(32): # for each bit position
bit_count = 0
for num in nums:
# mask out everything but this bit and add
bit_count += (num >> bit) & 1
bit_count %= 3
if bit_count:
# set the bit in result
result |= (1 << bit)
# Handle Python's infinite int sign bit issues:
if result >= 2**31:
result -= 2**32
return result

Sum of Two Integers (Medium)

Explanation: To add two integers without using + , we can use bit operations. The idea is: XOR of two bits
gives the sum without carry, AND gives the carry. We iteratively apply these: compute carry = (a & b)
<< 1 and a = a ^ b . Then set b = carry and repeat until carry is 0. In Python, because integers are
unbounded, we need to mask to 32 bits to avoid infinite loops for negative results, and adjust for two's
complement at the end.

20
 def getSum(a, b):
# Mask to get last 32 bits (simulate 32-bit int)
mask = 0xFFFFFFFF
while b != 0:
carry = (a & b) << 1
a = (a ^ b) & mask
b = carry & mask
# if a is negative in 32-bit, convert to Python negative
return a if a < 0x80000000 else ~(a ^ mask)

Bitwise AND of Numbers Range (Medium)

Explanation: To find the bitwise AND of all numbers in a range [m, n], notice that as numbers increment,
lower bits will cycle through 0 and 1. The common prefix of m and n in binary will remain, while all lower
differing bits will eventually zero out. One solution is to shift m and n right until they are equal, counting
shifts. That common portion (shifted left back to place) is the result. This effectively zeroes out any bit that
changes across the range.

def rangeBitwiseAnd(m, n):

shift = 0
# Find the common prefix
while m != n:
m >>= 1
n >>= 1
shift += 1
return m << shift

Two Pointers
The two-pointer technique involves using two indices to traverse a data structure (usually an array or string)
from either end or with one faster than the other. It is useful for searching pairs/triplets that meet certain
criteria in sorted arrays, partitioning arrays, or finding palindromic strings. Common patterns include the
"opposite end" two-pointer for sorted arrays and the "fast-slow" pointer for cycle detection or finding a
middle element.

Common uses/patterns: - Opposite-end two pointers: Start one pointer at the beginning and one at the
end of a sorted array and move inward to find pairs that meet a condition (like two-sum in a sorted array,
finding pair sums, container with most water etc.)
- Same-direction two pointers: One pointer lags behind another (fast/slow) for tasks like removing
duplicates in-place, or sliding window boundaries (though sliding window is its own category)
- Fast-slow (Floyd’s cycle): One moves twice as fast to detect cycles or to split lists
- Sorting-based k-sum problems (2-sum, 3-sum, 4-sum) often use two pointers after sorting the list

Two Sum II - Input Array is Sorted (Easy)

21
 def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed positions as per problem
elif s < target:
left += 1
else:
right -= 1
return [] # not found

Valid Palindrome II (Easy)

def validPalindrome(s):
def is_palindrome(subs):
return subs == subs[::-1]
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
# Skip either left or right character and check
return is_palindrome(s[left+1:right+1]) or
is_palindrome(s[left:right])
left += 1
right -= 1
return True

3Sum (Medium)
Explanation: To find all unique triplets that sum to zero, sort the array first. Then iterate through each
number as a potential first element of the triplet. For each such number, use two pointers ( lo and hi )
starting at both ends of the remaining list to find pairs that sum to the negative of the first number. Move
the pointers inward based on the sum. Skip duplicate values to avoid repeating triplets. Sorting is O(n log n)
and the two-pointer scan is O(n) for each of n elements, so overall O(n^2).

def threeSum(nums):
nums.sort()
res = []
n = len(nums)
for i in range(n - 2):
if i > 0 and nums[i] == nums[i-1]:
continue # skip duplicates for the first element
target = -nums[i]
lo, hi = i + 1, n - 1

22
 while lo < hi:
total = nums[lo] + nums[hi]
if total == target:
res.append([nums[i], nums[lo], nums[hi]])
# Skip duplicates for lo and hi
while lo < hi and nums[lo] == nums[lo+1]:
lo += 1
while lo < hi and nums[hi] == nums[hi-1]:
hi -= 1
lo += 1
hi -= 1
elif total < target:
lo += 1
else:
hi -= 1
return res

4Sum (Medium)
Explanation: Similar to 3Sum, but we fix two numbers and then use two pointers for the remaining two.
After sorting, use four nested loops effectively: two outer loops for the first two numbers (with skipping
duplicates), then two-pointer for the rest. To reduce complexity, one can also use recursion or hash-based
pruning. The overall complexity is O(n^3) for four sum.

def fourSum(nums, target):

nums.sort()
res = []
n = len(nums)
for a in range(n - 3):
if a > 0 and nums[a] == nums[a-1]:
continue
for b in range(a + 1, n - 2):
if b > a + 1 and nums[b] == nums[b-1]:
continue
lo, hi = b + 1, n - 1
while lo < hi:
total = nums[a] + nums[b] + nums[lo] + nums[hi]
if total == target:
res.append([nums[a], nums[b], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]:
lo += 1
while lo < hi and nums[hi] == nums[hi-1]:
hi -= 1
lo += 1
hi -= 1
elif total < target:
lo += 1

23
 else:
hi -= 1
return res

Remove Duplicates from Sorted Array II (Medium)

Explanation: In an array sorted in non-decreasing order, allow at most two occurrences of each element. We
use two pointers: one (write_index) to build the result in place, and one (read_index) to iterate. We also
maintain a count of the current number’s occurrences. If the next number is the same and count is less
than 2, we keep it. If it’s new, we reset count. This way, each element appears at most twice. The resulting
length of the modified array is returned (and the array is modified in-place up to that length).

def removeDuplicatesII(nums):
if len(nums) <= 2:
return len(nums)
write_index = 1
count = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
count += 1
else:
count = 1
if count <= 2:
nums[write_index] = nums[i]
write_index += 1
return write_index

Container With Most Water (Medium)

Explanation: Given heights of vertical lines on an x-axis, to find the max water container, use two pointers at
both ends. Compute area = min(height[left], height[right]) * (right - left). Then, move the pointer which has
the smaller height inward, because moving the larger-height pointer inward could only decrease area as
width shrinks and the limiting height might not increase. By moving the smaller height, we hope to find a
taller line that could increase area. Continue until the pointers meet. This greedy approach finds the
maximum area in O(n) time.

def maxArea(height):
left, right = 0, len(height) - 1
max_area = 0
while left < right:
h = min(height[left], height[right])
width = right - left
max_area = max(max_area, h * width)
# Move the pointer at the shorter line inward
if height[left] < height[right]:
left += 1

24
 else:
right -= 1
return max_area

Trapping Rain Water (Hard)

Explanation: Use two pointers to compute trapped water. We maintain left_max and right_max – the
highest walls seen so far from the left and from the right. Start pointers at both ends and move inward. At
each step, update left_max or right_max. Water at a position is determined by the smaller of left_max and
right_max minus the height at that position (if positive). By always moving the side with the smaller height,
we ensure that we have a boundary on that side. This yields O(n) time and O(1) space.

def trap(height):
left, right = 0, len(height) - 1
left_max = right_max = 0
trapped = 0
while left < right:
if height[left] < height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
trapped += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
trapped += right_max - height[right]
right -= 1
return trapped

Sort Colors (Medium)

Explanation: This is the Dutch National Flag problem. We need to sort an array of colors (0, 1, 2) in-place. Use
three pointers: low for next position of 0, high for next position of 2 (from end), and i to iterate. If we
see a 0, swap it to low index and increment both low and i . If we see a 2, swap it with high index
and decrement high (do not increment i in this case, because the swapped in element at i needs to be
processed). If we see a 1, just move i. This one-pass partitioning results in sorted order.

def sortColors(nums):
low, i, high = 0, 0, len(nums) - 1
while i <= high:
if nums[i] == 0:
nums[i], nums[low] = nums[low], nums[i]
low += 1
i += 1

25
 elif nums[i] == 2:
nums[i], nums[high] = nums[high], nums[i]
high -= 1
# do not increment i here
else: # nums[i] == 1
i += 1

Sliding Window
The sliding window technique is used for problems dealing with subarrays or substrings within arrays/
strings, especially when looking for a substructure that satisfies a certain condition. The idea is to maintain
a “window” (a contiguous segment of the array/string) and adjust its boundaries (usually moving one end at
a time) to find the optimal solution (max/min length or a count that satisfies a condition). This technique is
often combined with two-pointer approach and sometimes hashing (for variable-length windows with
conditions like unique characters).

Common uses/patterns: - Fixed-length window problems (e.g., maximum sum of subarray of size k) –
straightforward summation.
- Variable-length window problems (expand and contract the window boundaries to meet conditions like “at
most K distinct characters”, or “sum <= X”). Use a moving right pointer to expand and a left pointer to shrink
when a condition is violated.
- Often involves hash maps or counters to track frequency of elements within the window (for problems like
anagrams, substring with unique chars, etc.)
- In general, useful when the problem involves contiguous segments and an optimal subsegment needs to
be found under some constraints.

Longest Substring Without Repeating Characters (Medium)

Explanation: Use a sliding window with two pointers left and right . Move right pointer to expand
the window, and use a hash map (or array of size 128/256 for ASCII) to record the last seen index of each
character. If a character is encountered that is already in the current window (repeat), move the left
pointer to one position right of the last seen index of that character to shrink the window and remove the
repetition. Track the maximum window size seen.

def lengthOfLongestSubstring(s):
last_index = {}
longest = 0
left = 0
for right, ch in enumerate(s):
if ch in last_index and last_index[ch] >= left:
# Move left pointer right past the last occurrence of ch
left = last_index[ch] + 1
last_index[ch] = right
longest = max(longest, right - left + 1)
return longest

26
Longest Repeating Character Replacement (Medium)
Explanation: We maintain a sliding window and keep track of the count of the most frequent character in the
window. We expand the window with right pointer. If the window size minus the count of the most
frequent char is greater than k (meaning we need to replace more than k chars to make all same), then we
shrink the window from the left. The length of the window at any point where it's valid (<= k replacements
needed) could be a candidate for result. This works in O(n) by using the fact that we only shrink when
necessary and maintain the max frequency count.

def characterReplacement(s, k):

count = {}
max_freq = 0
left = 0
res = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
max_freq = max(max_freq, count[ch])
# If more than k chars need replacement, shrink window
while (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
res = max(res, right - left + 1)
return res

Permutation in String (Medium)

Explanation: Check if s1 ’s permutation is a substring of s2 . This can be done by using a fixed-size window
of length len(s1) sliding over s2 and checking if the frequency distribution of that window matches s1’s
frequency distribution. We maintain a count of characters in the current window of s2 and compare it to the
target count (using an array of length 26 for letters). Instead of comparing full arrays each time, we can
keep track of how many character counts are currently matching. Slide one character at a time, update
counts and match status.

def checkInclusion(s1, s2):

from collections import Counter
n1, n2 = len(s1), len(s2)
if n1 > n2:
return False
target = Counter(s1)
window = Counter(s2[:n1])
if window == target:
return True
# Slide the window
for i in range(n1, n2):
window[s2[i]] += 1
window[s2[i - n1]] -= 1
if window[s2[i - n1]] == 0:

27
 del window[s2[i - n1]]
if window == target:
return True
return False

Find All Anagrams in a String (Medium)

Explanation: Similar to the above, we slide a window of length len(p) over string s, and check if the current
window is an anagram of p. We maintain character counts in the window using a frequency array or map.
One neat approach is to keep a count of how many characters have the desired frequency. Initialize with the
target (p’s frequency). As we move the window, update the counts and track if all characters match the
target frequency. Whenever they do, record the start index. This is O(n) time.

def findAnagrams(s, p):

from collections import Counter
res = []
n, m = len(s), len(p)
if m > n:
return res
p_count = Counter(p)
s_count = Counter(s[:m])
if s_count == p_count:
res.append(0)
for i in range(m, n):
# include s[i], exclude s[i-m]
s_count[s[i]] += 1
s_count[s[i-m]] -= 1
if s_count[s[i-m]] == 0:
del s_count[s[i-m]]
if s_count == p_count:
res.append(i - m + 1)
return res

Fruit Into Baskets (Medium)

Explanation: This is essentially the longest subarray with at most 2 distinct elements. Use a sliding window
and a hash map to count fruits. Expand with right pointer, adding fruit counts. If the window contains
more than 2 types, move the left pointer up until only 2 types remain (decrementing counts and
removing a type when its count drops to 0). Track the maximum window length that satisfied the condition.

def totalFruit(fruits):
from collections import defaultdict
basket = defaultdict(int)
left = 0
max_picked = 0
for right, fruit in enumerate(fruits):

28
 basket[fruit] += 1
# If more than 2 types of fruit, shrink window
while len(basket) > 2:
basket[fruits[left]] -= 1
if basket[fruits[left]] == 0:
del basket[fruits[left]]
left += 1
max_picked = max(max_picked, right - left + 1)
return max_picked

Minimum Window Substring (Hard)

Explanation: Use the sliding window with two pointers to find the smallest window that contains all
characters of string t . Maintain a count of needed characters from t . Expand right until the window
satisfies the requirement (covers all chars), then contract from the left to find a smaller window that still
satisfies. Use two Counters or arrays: one for frequency needed (target) and one for current window
frequency. Also maintain a formed count to know when the current window contains the required count
of each character. This approach is O(n) on average.

def minWindow(s, t):

from collections import Counter
if not s or not t:
return ""
target = Counter(t)
required = len(target)
formed = 0
window_counts = {}
left = 0
min_len = float('inf')
res = (0, 0)
for right, ch in enumerate(s):
window_counts[ch] = window_counts.get(ch, 0) + 1
if ch in target and window_counts[ch] == target[ch]:
formed += 1
# Try to contract from left if all required chars are present
while formed == required:
if right - left + 1 < min_len:
min_len = right - left + 1
res = (left, right)
# Prepare to move left pointer
left_ch = s[left]
window_counts[left_ch] -= 1
if left_ch in target and window_counts[left_ch] < target[left_ch]:
formed -= 1
left += 1

29
 l, r = res
return s[l:r+1] if min_len != float('inf') else ""

Sliding Window Maximum (Hard)

Explanation: To get the maximum in every window of size k, we can use a deque (double-ended queue) to
store indices of useful elements in the current window. The deque is maintained such that the indices in it
are in increasing order of their values (monotonic decreasing values in deque). As we slide the window, we
pop indices from the back if the current element is greater (to maintain monotonicity) and pop from the
front if an index is out of the current window’s range. The max of the current window is at the front of the
deque. This yields O(n) time.

from collections import deque

def maxSlidingWindow(nums, k):
dq = deque() # will store indices
res = []
for i, num in enumerate(nums):
# Remove indices that are out of this window
if dq and dq[0] == i - k:
dq.popleft()
# Remove smaller numbers in k range as they are not useful
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
# The window is fully seen only when i >= k-1
if i >= k - 1:
res.append(nums[dq[0]])
return res

Binary Search
Binary search is an algorithm to find an element’s position (or determine its absence) in a sorted array in
O(log n) time by repeatedly dividing the search interval in half. Binary search is also used in more advanced
scenarios to answer queries or find optimum values (binary search on answer). Key to using binary search is
a monotonic condition – the target space must be ordered or the condition function returns either always
false then always true (or vice versa) as you move through the domain.

Common uses/patterns: - Finding an element or insertion point in a sorted array

- Searching for a condition’s boundary (e.g., first true/last false) using binary search on index space
- Binary search on answer: when you need to minimize or maximize a value under some feasibility condition
(e.g., allocate minimum capacity to satisfy constraints)
- Searching in monotonic but not explicitly sorted structures (like finding square root, or in bit manipulation
range problems)

Binary Search (Easy)

30
 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 # target not found

Search Insert Position (Easy)

def searchInsert(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
# left is now the insertion point
return left

Find First and Last Position of Element (Medium)

Explanation: Use binary search twice – once to find the first (leftmost) occurrence of the target and once to
find the last (rightmost) occurrence. We modify the binary search condition to bias towards the left (when
finding first) or right (when finding last) when equal elements are found, and return the appropriate
boundary. This ensures O(log n) time.

def searchRange(nums, target):

def find_bound(is_first):
left, right = 0, len(nums) - 1
res = -1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
res = mid
if is_first:
right = mid - 1 # search towards left side

31
 else:
left = mid + 1 # search towards right side
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return res
first = find_bound(True)
last = find_bound(False)
return [first, last]

Search in Rotated Sorted Array (Medium)

Explanation: Even though the array is rotated, it consists of two sorted subarrays. We can modify binary
search: at each step, check if the mid falls in the left sorted portion or right sorted portion by comparing
with boundary values, then determine which half to search based on where the target lies relative to the
sorted half’s range. This is O(log n).

def searchRotated(nums, target):

left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# Determine which side is sorted
if nums[left] <= nums[mid]: # left half is sorted
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else: # right half is sorted
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1

Find Minimum in Rotated Sorted Array (Medium)

Explanation: In a rotated sorted array (no duplicates), the minimum element is the only element where its
previous element is greater than it (or it’s at index 0 if no rotation). Binary search can find the pivot:
compare mid element to the last element. If nums[mid] > nums[right] , it means the smallest value is
in the right half; otherwise, it’s in the left half. Narrow down until left meets right, which will be the index of
minimum.

32
 def findMin(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]

Find Peak Element (Medium)

Explanation: A peak element is one that is greater than its neighbors. The array has a property that you can
use binary search: pick mid, if it is a peak return it; if the element on the right of mid is larger, then a peak
must exist on the right side (because going right is uphill), so search right. If the element on the left of mid
is larger, then a peak lies on the left side. This works in O(log n).

def findPeakElement(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] < nums[mid + 1]:
# there is an ascent to the right, so peak must be right
left = mid + 1
else:
# peak is at mid or to the left
right = mid
return left

Median of Two Sorted Arrays (Hard)

Explanation: This can be solved by binary searching on the partition of the two arrays. We choose a partition
in array A and a corresponding partition in array B such that the left halves contain the smaller half of
numbers and right halves contain the larger half. Ensure that max(leftA, leftB) <= min(rightA,
rightB) . We do a binary search on the smaller array’s partition index to find the correct split. The median
is then either the max of left halves (for odd combined length) or average of max(left) and min(right) (for
even combined length). This is quite involved but runs in O(log(min(n, m))).

def findMedianSortedArrays(nums1, nums2):

A, B = nums1, nums2
m, n = len(A), len(B)
if m > n: # ensure A is the smaller array
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError("At least one array must be non-empty")

33
 half_len = (m + n + 1) // 2
imin, imax = 0, m
while imin <= imax:
i = (imin + imax) // 2
j = half_len - i
if i < m and B[j-1] > A[i]:
imin = i + 1 # i is too small, must increase
elif i > 0 and A[i-1] > B[j]:
imax = i - 1 # i is too big, must decrease
else:
# i is perfect
if i == 0: left_max = B[j-1]
elif j == 0: left_max = A[i-1]
else: left_max = max(A[i-1], B[j-1])
if (m + n) % 2 == 1:
return float(left_max)
if i == m: right_min = B[j]
elif j == n: right_min = A[i]
else: right_min = min(A[i], B[j])
return (left_max + right_min) / 2.0

Heap and Priority Queue

Heaps (usually implemented as priority queues) are tree-based structures that always allow quick retrieval
of the minimum or maximum element (in O(1) time) and insertion/deletion in O(log n) time. They are useful
for problems where you need to repeatedly extract the smallest or largest element, or maintain a running
set of top elements. In Python, heapq provides a min-heap implementation.

Common uses/patterns: - Keeping track of top k elements (max-heap or min-heap of size k)

- Merge operations (like merging k sorted lists or files)
- Scheduling problems (priority by time or other weight)
- Dijkstra’s algorithm for shortest path (min-heap for next closest vertex)
- Anytime you need the smallest/largest element dynamically as elements are added/removed

Kth Largest Element in an Array (Medium)

Explanation: Use a min-heap of size k. Add elements to the heap; if heap size exceeds k, pop the smallest.
This way, the heap always holds the k largest elements seen so far. At the end, the root of the min-heap
(smallest of the k) is the k-th largest overall. This is O(n log k) time and O(k) space. Alternatively, sort the
array (O(n log n)) or use Quickselect average O(n).

import heapq
def findKthLargest(nums, k):
minheap = []
for num in nums:
heapq.heappush(minheap, num)

34
 if len(minheap) > k:
heapq.heappop(minheap)
return minheap[0]

Top K Frequent Elements (Medium)

Explanation: First count frequency of each element using a hash map. Then, use a min-heap of size k to keep
track of top k frequencies. Iterate over the frequency map items, push (freq, num) onto min-heap and pop
when size exceeds k. In the end, the heap contains the k most frequent elements. Alternatively, use
nlargest from heapq or sort the frequency list. The complexity is O(n log k).

import heapq
def topKFrequent(nums, k):
from collections import Counter
freq = Counter(nums)
heap = []
for num, count in freq.items():
heapq.heappush(heap, (count, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for (count, num) in heap]

Task Scheduler (Medium)

Explanation: This scheduling problem can be solved using a max-heap for task counts. We repeatedly take
the two most frequent remaining tasks (or one, depending on cooling interval) and execute them,
decrementing counts and then pushing them back if still remaining. The greedy strategy is to always
execute the most pending task available. Alternatively, the mathematical solution computes idle slots using
frequencies. Here, using a heap and simulation ensures tasks execution order.

import heapq
from collections import Counter, deque
def leastInterval(tasks, n):
if n == 0:
return len(tasks)
freq = Counter(tasks)
max_heap = [-cnt for cnt in freq.values()]
heapq.heapify(max_heap)
time = 0
queue = deque() # to hold tasks during cooling
while max_heap or queue:
time += 1
if max_heap:
cnt = heapq.heappop(max_heap)
cnt += 1 # this task is executed once, so decrement its remaining
count (cnt is negative)

35
 if cnt != 0:
# put this task in cooling
queue.append((cnt, time + n))
if queue and queue[0][1] == time:
# the task at front of queue has cooled down, push back to heap
heapq.heappush(max_heap, queue.popleft()[0])
return time

Meeting Rooms II (Medium)

Explanation: To find the minimum number of meeting rooms required, use a min-heap to track end times of
ongoing meetings. Sort meetings by start time. Iterate through each meeting; if the earliest ending meeting
is finished before the current meeting starts (heap root <= current start), pop it (free a room). Then push the
current meeting’s end time onto the heap. The heap size at any point is the number of concurrent
meetings. The maximum heap size during the iteration is the answer.

import heapq
def minMeetingRooms(intervals):
if not intervals:
return 0
intervals.sort(key=lambda x: x[0]) # sort by start time
heap = [] # min-heap for end times
heapq.heappush(heap, intervals[0][1])
for interval in intervals[1:]:
if heap[0] <= interval[0]:
heapq.heappop(heap) # reuse room
heapq.heappush(heap, interval[1])
return len(heap)

Merge K Sorted Lists (Hard)

Explanation: Use a min-heap to keep track of the current smallest head among the k lists. Initialize the heap
with the first node of each list (with (value, list_index) to handle value ties). Then repeatedly extract the
smallest node and append it to the merged list result, and if that node had a next node, push the next node
into the heap. This way we always take the smallest available node. The complexity is O(N log k) where N is
total number of nodes and k is number of lists.

import heapq
def mergeKLists(lists):
minheap = []
# initialize heap with first node of each list
for idx, node in enumerate(lists):
if node:
heapq.heappush(minheap, (node.val, idx, node))
dummy = ListNode(0)
current = dummy

36
 while minheap:
val, idx, node = heapq.heappop(minheap)
current.next = node
current = current.next
if node.next:
heapq.heappush(minheap, (node.next.val, idx, node.next))
return dummy.next

Find Median from Data Stream (Hard)

Explanation: Maintain two heaps – a max-heap for the lower half of numbers and a min-heap for the upper
half. The max-heap holds the smaller half of the numbers, and the min-heap holds the larger half. This way,
the median is either the top of one of the heaps (if total count is odd) or the average of the two tops (if
even). When adding a number, decide which heap to put it in (if number is smaller than or equal to max of
lower half, go to max-heap; else to min-heap). Then balance the heaps sizes (they should differ at most by
one). Retrieving median is O(1). Addition is O(log n).

import heapq
class MedianFinder:
def __init__(self):
self.small = [] # max heap (store negatives for Python)
self.large = [] # min heap

def addNum(self, num: int) -> None:

# Add to max heap (small) by default
heapq.heappush(self.small, -num)
# Balance: make sure every num in small <= every num in large
if self.small and self.large and (-self.small[0] > self.large[0]):
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
# Rebalance sizes to differ at most by 1
if len(self.small) > len(self.large) + 1:
val = -heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -val)

def findMedian(self) -> float:

if len(self.small) == len(self.large):
return (-self.small[0] + self.large[0]) / 2.0
elif len(self.small) > len(self.large):
return float(-self.small[0])
else:
return float(self.large[0])

37
Graphs
Graphs consist of vertices (nodes) connected by edges. Graph problems often involve traversals (depth-first
search or breadth-first search), shortest path algorithms, or union-find (disjoint set union) for connectivity.
Graphs can be directed or undirected, weighted or unweighted. Key patterns include exploring connected
components, cycle detection, topological sorting for DAGs, and pathfinding.

Common uses/patterns: - Traversal (BFS/DFS): explore all nodes reachable from a starting node (e.g.,
connected components, flood fill, maze solving). BFS is used for shortest path in unweighted graphs, DFS
for exhaustive path exploration or topological sort.
- Shortest Path: Dijkstra’s (with min-heap) for weighted graphs with no negative weights; BFS for
unweighted; Bellman-Ford or Floyd-Warshall for graphs with negative weights (if needed, though less
common in interviews).
- Union-Find (DSU): determine connectivity, find cycles, or minimum spanning tree (Kruskal’s algorithm).
- Topological Sort: order vertices given directed acyclic graph (DAG) constraints (prerequisites problems,
build/order scheduling).

Number of Islands (Medium)

Explanation: Count connected components in a grid (matrix) of '1's (land) using BFS or DFS. We iterate over
each cell; when we find a '1', we increment the count and perform a BFS/DFS to mark all connected land as
visited (e.g., flip them to '0'). This ensures each island is counted exactly once. This is O(m*n) for an m x n
grid.

def numIslands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited
dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count

Clone Graph (Medium)

Explanation: Perform a BFS or DFS traversal of the graph, and simultaneously create a copy. Use a dictionary
to map original nodes to their clones. Start from the given node, create its clone, then traverse neighbors:
for each neighbor, if not cloned yet, create clone and put it in the queue/stack; then add the neighbor’s
clone to the current node’s clone’s adjacency list. This ensures each node is cloned once.

38
 def cloneGraph(node):
if not node:
return None
clone_map = {}
from collections import deque
q = deque([node])
clone_map[node] = Node(node.val, [])
while q:
curr = q.popleft()
for nei in curr.neighbors:
if nei not in clone_map:
clone_map[nei] = Node(nei.val, [])
q.append(nei)
# Append the cloned neighbor to the clone node's neighbors
clone_map[curr].neighbors.append(clone_map[nei])
return clone_map[node]

Course Schedule (Medium)

Explanation: This is a cycle detection in a directed graph problem (prerequisite graph). We use DFS or BFS
(Kahn's algorithm). DFS approach: perform a DFS from each course that hasn’t been visited, marking nodes
in recursion stack to detect cycles. If a cycle is found, return False. If DFS finishes without cycles, return True.
Alternatively, use in-degree and BFS (Kahn’s) to detect if all nodes can be completed (i.e., processed in
topological order).

def canFinish(numCourses, prerequisites):

graph = {i: [] for i in range(numCourses)}
for u, v in prerequisites:
graph[v].append(u)
# 0 = unvisited, 1 = visiting, 2 = visited
state = [0] * numCourses
def dfs(node):
if state[node] == 1:
return False # cycle detected
if state[node] == 2:
return True # already fully processed
state[node] = 1 # mark as visiting
for nei in graph[node]:
if not dfs(nei):
return False
state[node] = 2 # mark as done
return True
for course in range(numCourses):
if state[course] == 0:
if not dfs(course):

39
 return False
return True

Course Schedule II (Medium)

Explanation: Similar to Course Schedule, but we need to return an order of courses (topological sort) if
possible. Use Kahn’s algorithm (BFS): compute in-degrees of all nodes, initialize a queue with nodes of in-
degree 0 (no prerequisites). Repeatedly take a node from queue, add it to result, decrement in-degrees of
its neighbors, and enqueue any neighbors that become 0 in-degree. If we processed all courses, return the
order; if a cycle prevented processing all, return an empty list.

def findOrder(numCourses, prerequisites):

graph = {i: [] for i in range(numCourses)}
indegree = [0] * numCourses
for u, v in prerequisites:
graph[v].append(u)
indegree[u] += 1
from collections import deque
q = deque([i for i in range(numCourses) if indegree[i] == 0])
order = []
while q:
node = q.popleft()
order.append(node)
for nei in graph[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
q.append(nei)
return order if len(order) == numCourses else []

Pacific Atlantic Water Flow (Medium)

Explanation: We need cells that can reach both Pacific and Atlantic. Treat the grid as a graph, and perform a
reverse DFS/BFS from the oceans. Specifically, start from all cells adjacent to Pacific (top row and left
column) and mark all reachable cells (they flow into Pacific). Similarly, mark cells reachable from Atlantic
(bottom row and right column). The intersection of these reachable sets is the result. This works because
water can flow from a cell to neighbors with equal or lower height. Complexity is O(m*n).

def pacificAtlantic(heights):
if not heights:
return []
m, n = len(heights), len(heights[0])
pacific_reached = [[False] * n for _ in range(m)]
atlantic_reached = [[False] * n for _ in range(m)]
from collections import deque
pac_q = deque()
atl_q = deque()

40
 # initialize queues with border cells
for i in range(m):
pac_q.append((i, 0)); pacific_reached[i][0] = True
atl_q.append((i, n-1)); atlantic_reached[i][n-1] = True
for j in range(n):
pac_q.append((0, j)); pacific_reached[0][j] = True
atl_q.append((m-1, j)); atlantic_reached[m-1][j] = True
# BFS from Pacific border
directions = [(1,0),(-1,0),(0,1),(0,-1)]
while pac_q:
r, c = pac_q.popleft()
for dr, dc in directions:
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and not pacific_reached[nr][nc] and
heights[nr][nc] >= heights[r][c]:
pacific_reached[nr][nc] = True
pac_q.append((nr, nc))
# BFS from Atlantic border
while atl_q:
r, c = atl_q.popleft()
for dr, dc in directions:
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and not atlantic_reached[nr][nc] and
heights[nr][nc] >= heights[r][c]:
atlantic_reached[nr][nc] = True
atl_q.append((nr, nc))
# collect cells that can reach both
result = []
for i in range(m):
for j in range(n):
if pacific_reached[i][j] and atlantic_reached[i][j]:
result.append([i, j])
return result

Number of Provinces (Medium)

Explanation: This is essentially finding connected components in an undirected graph (adjacency matrix
given for cities connectivity). Use a DFS or Union-Find. DFS: iterate through each city, if not visited, do a DFS
marking all reachable cities as visited, and increment province count. Union-Find: treat each connection as
union operation and count disjoint sets. We'll do DFS here for simplicity.

def findCircleNum(isConnected):
n = len(isConnected)
visited = [False] * n
def dfs(city):
for j in range(n):
if isConnected[city][j] == 1 and not visited[j]:

41
 visited[j] = True
dfs(j)
provinces = 0
for i in range(n):
if not visited[i]:
visited[i] = True
dfs(i)
provinces += 1
return provinces

Graph Valid Tree (Medium)

Explanation: A graph is a valid tree if it is fully connected and has no cycles. We can use union-find to check
for cycles and connectivity: iterate through edges, if an edge connects two already-connected nodes (find
returns same root), then there's a cycle. Also, ensure that number of edges is exactly n-1 for n nodes (a
quick check, as more or less edges disqualify a tree). Alternatively, use DFS to check connectivity and cycle
(like detecting cycle in undirected graph and counting visited nodes).

def validTree(n, edges):

if len(edges) != n - 1:
return False
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
rootX, rootY = find(x), find(y)
if rootX == rootY:
return False
parent[rootY] = rootX
return True
for u, v in edges:
if not union(u, v):
return False
return True

Network Delay Time (Medium)

Explanation: This is a single-source shortest path problem in a directed weighted graph. Use Dijkstra’s
algorithm starting from the source K. Use a min-heap to always pick the next node with the smallest current
distance. Relax edges and update distances. In the end, if all nodes are reachable, the answer is the
maximum distance found; if some are not reachable, return -1. Complexity is O(E log V).

import heapq
def networkDelayTime(times, n, k):

42
 graph = {i: [] for i in range(1, n+1)}
for u, v, w in times:
graph[u].append((v, w))
# distances initialized to infinity except start node
dist = {i: float('inf') for i in range(1, n+1)}
dist[k] = 0
# min-heap of (time, node)
heap = [(0, k)]
while heap:
time, node = heapq.heappop(heap)
if time > dist[node]:
continue
for nei, w in graph[node]:
new_time = time + w
if new_time < dist[nei]:
dist[nei] = new_time
heapq.heappush(heap, (new_time, nei))
max_time = max(dist.values())
return max_time if max_time != float('inf') else -1

Word Ladder (Hard)

Explanation: Model each word as a node in a graph, with edges connecting words that differ by one letter.
Use BFS from the beginWord to find the shortest transformation sequence to endWord . To optimize,
preprocess by grouping words by generic patterns (e.g., *ot for words like hot, dot, lot) to find neighbors
quickly. Each BFS step changes one letter at a time and checks if the resulting word is in the dictionary. The
first time endWord is reached, that level of BFS is the answer.

from collections import deque, defaultdict

def ladderLength(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
# Preprocess generic forms
combos = defaultdict(list)
L = len(beginWord)
for word in wordSet:
for i in range(L):
pattern = word[:i] + "*" + word[i+1:]
combos[pattern].append(word)
# BFS
visited = set([beginWord])
q = deque([(beginWord, 1)])
while q:
word, steps = q.popleft()
for i in range(L):
pattern = word[:i] + "*" + word[i+1:]

43
 for nei in combos[pattern]:
if nei == endWord:
return steps + 1
if nei not in visited:
visited.add(nei)
q.append((nei, steps + 1))
combos[pattern] = [] # avoid re-processing
return 0

Alien Dictionary (Hard)

Explanation: Determine a valid order of characters given a sorted dictionary of an alien language (essentially
perform topological sort on characters). First, build a directed graph of character precedence: compare
adjacent words and find the first differing character; that gives an ordering rule (edge). Then perform
topological sort (Kahn’s or DFS) on this graph of characters. If a cycle exists or a conflict (like prefix issue),
return "". Otherwise, return the computed order.

from collections import defaultdict, deque

def alienOrder(words):
# Build graph
graph = {c: set() for word in words for c in word}
indegree = {c: 0 for c in graph}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
# Check that word2 is not a prefix of word1 (invalid lexicographic
order)
if len(w2) < len(w1) and w1.startswith(w2):
return ""
# Find first differing character
for c1, c2 in zip(w1, w2):
if c1 != c2:
if c2 not in graph[c1]:
graph[c1].add(c2)
indegree[c2] += 1
break
# Topological sort
q = deque([c for c in indegree if indegree[c] == 0])
order = []
while q:
c = q.popleft()
order.append(c)
for nei in graph[c]:
indegree[nei] -= 1
if indegree[nei] == 0:
q.append(nei)
if len(order) != len(graph):

44
 return "" # cycle detected
return "".join(order)

Trees
Trees are hierarchical data structures where each node has zero or more children, and typically one node is
designated as the root. Binary trees (each node has up to two children) are common, and binary search
trees (BSTs) are a special kind where the left subtree has smaller values and right subtree larger values than
the node. Common tree problems involve traversals (inorder, preorder, postorder, level-order), depth
calculations, path finding, and recursive solutions given the natural recursive structure of trees.

Common uses/patterns: - Traversals: DFS (preorder, inorder, postorder) often via recursion or stack; BFS
via queue for level order
- Divide and conquer: Many tree problems can be solved by computing results from children (postorder
style) and combining them (e.g., depth, balancing, LCA, path sums)
- Binary Search Tree: Exploit the BST property for search, insert, in-order traversal yields sorted order, etc.
- Tree shape problems: Balanced tree, symmetric tree, invert tree etc., typically straightforward recursive
definitions
- Least Common Ancestor (LCA): classic recursion or parent pointer approach to find shared ancestor in
tree

Invert Binary Tree (Easy)

def invertTree(root):
if not root:
return None
root.left, root.right = invertTree(root.right), invertTree(root.left)
return root

Same Tree (Easy)

def isSameTree(p, q):

if not p and not q:
return True
if not p or not q or p.val != q.val:
return False
return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Symmetric Tree (Easy)

def isSymmetric(root):
def mirror(n1, n2):

45
 if not n1 and not n2:
return True
if not n1 or not n2 or n1.val != n2.val:
return False
return mirror(n1.left, n2.right) and mirror(n1.right, n2.left)
return mirror(root, root)

Balanced Binary Tree (Easy)

Explanation: A binary tree is balanced if for every node, the height difference between left and right
subtrees is at most 1. Solve via recursion: compute the height of subtrees; if any difference > 1 or a subtree
is unbalanced, propagate failure. We can optimize by returning -1 as a flag for imbalance. If a subtree
returns -1 or the difference is >1, then propagate -1 up. Otherwise, return the actual height (max of children
+ 1).

def isBalanced(root):
def height(node):
if not node:
return 0
lh = height(node.left)
if lh == -1:
return -1
rh = height(node.right)
if rh == -1:
return -1
if abs(lh - rh) > 1:
return -1
return max(lh, rh) + 1
return height(root) != -1

Binary Tree Level Order Traversal (Medium)

from collections import deque

def levelOrder(root):
res = []
if not root:
return res
q = deque([root])
while q:
level_size = len(q)
level_nodes = []
for _ in range(level_size):
node = q.popleft()
level_nodes.append(node.val)
if node.left:

46
 q.append(node.left)
if node.right:
q.append(node.right)
res.append(level_nodes)
return res

Binary Tree Right Side View (Medium)

Explanation: Perform a level-order traversal (BFS) and take the last element of each level (that’s the
rightmost element visible from that level). Alternatively, do a DFS that prioritizes the right subtree first and
record the first node visited at each depth. The BFS approach is straightforward: for each level, add the
rightmost node’s value to result.

from collections import deque

def rightSideView(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result

Lowest Common Ancestor of a BST (Easy)

def lowestCommonAncestorBST(root, p, q):

# In a BST, we can leverage the ordering property
node = root
while node:
if p.val < node.val and q.val < node.val:
node = node.left
elif p.val > node.val and q.val > node.val:
node = node.right
else:
return node

47
Lowest Common Ancestor of a Binary Tree (Medium)
Explanation: For a general binary tree (no ordering), do a DFS. If current node is None or equals p or q,
return it (as a flag that this branch has one of them). Recurse left and right. If both left and right recursion
return non-null, current node is the LCA. If one side is non-null, return that non-null up the chain. This finds
LCA in one pass.

def lowestCommonAncestor(root, p, q):

if not root or root == p or root == q:
return root
left = lowestCommonAncestor(root.left, p, q)
right = lowestCommonAncestor(root.right, p, q)
if left and right:
return root
return left if left else right

Validate Binary Search Tree (Medium)

Explanation: Check if a binary tree is a BST by ensuring that every node’s value is within an allowable range.
Use recursion passing down min and max bounds: initially (-∞, +∞). For each node, its value must be >
min_bound and < max_bound. Recursively validate left subtree with updated max_bound = node.val and
right subtree with min_bound = node.val. Alternatively, an inorder traversal that should produce a sorted
sequence can be used.

def isValidBST(root):
def validate(node, low, high):
if not node:
return True
if not (low < node.val < high):
return False
return validate(node.left, low, node.val) and validate(node.right,
node.val, high)
return validate(root, float('-inf'), float('inf'))

Serialize and Deserialize Binary Tree (Hard)

Explanation: We can use a pre-order traversal to serialize a tree to a string (with a marker for null, e.g., “#”).
For example, Node(val) as string, then serialize(left), then serialize(right). To deserialize, use an iterator or
index on the serialized data: read the next value; if it's "#", return None; else create a node and recursively
construct its left and right subtrees. This preserves the structure.

def serialize(root):
vals = []
def preOrder(node):
if not node:
vals.append("#")

48
 else:
vals.append(str(node.val))
preOrder(node.left)
preOrder(node.right)
preOrder(root)
return ",".join(vals)

def deserialize(data):
vals = data.split(",")
it = iter(vals)
def build():
val = next(it)
if val == "#":
return None
node = TreeNode(int(val))
node.left = build()
node.right = build()
return node
return build()

Binary Tree Maximum Path Sum (Hard)

Explanation: The maximum path sum in a binary tree is the largest sum of node values on any path (not
necessarily root to leaf; can start and end anywhere, but path must be continuous). Use DFS: for each node,
compute the maximum sum of a path starting at that node and extending downward either left or right
(choose the larger, if negative then take 0). Keep track of the maximum path sum seen, which could be the
sum through the current node plus both left and right contributions (this path goes through the node as
highest point). This uses global tracking of result.

def maxPathSum(root):
max_sum = float('-inf')
def gain(node):
nonlocal max_sum
if not node:
return 0
left_gain = max(gain(node.left), 0)
right_gain = max(gain(node.right), 0)
# Price of the path that goes through the current node
current_path_sum = node.val + left_gain + right_gain
max_sum = max(max_sum, current_path_sum)
# Return the max gain if we continue from current node to parent
return node.val + max(left_gain, right_gain)
gain(root)
return max_sum

49
Subtree of Another Tree (Easy)
Explanation: Check if tree t is a subtree of s . A simple solution is for each node in s , if its value matches
t’s root, then check if starting from that node, the subtree matches t (via a helper function that checks
node-by-node equality). Use DFS on s and the match helper for potential roots. This is O(m * n) worst-
case, but pruning when values don’t match helps average. Alternatively, one can serialize both trees (e.g.,
preorder with markers) and check if t’s serialization is a substring of s’s (unique sentinel to avoid incidental
matches).

def isSubtree(s, t):

if not t:
return True
if not s:
return False
if isSameTree(s, t):
return True
return isSubtree(s.left, t) or isSubtree(s.right, t)

# Reusing the isSameTree defined earlier for tree equality check

Kth Smallest Element in a BST (Medium)

Explanation: Since an inorder traversal of a BST yields sorted order, the k-th smallest can be found via an
inorder traversal. Keep a counter of nodes visited; once the counter equals k, return that node’s value. This
is O(h + k) time, where h is tree height (to reach the smallest), which is efficient. Alternatively, utilize an
iterative inorder with a stack.

def kthSmallest(root, k):

stack = []
node = root
count = 0
while stack or node:
while node:
stack.append(node)
node = node.left
node = stack.pop()
count += 1
if count == k:
return node.val
node = node.right

Tries
A Trie (prefix tree) is a tree-like data structure that stores strings by sharing common prefixes. Each node
represents a prefix of some of the inserted strings. Tries are particularly useful for quick prefix lookups,
auto-complete suggestions, and implementing algorithms like prefix-based search or word games.

50
Common uses/patterns: - Autocomplete and prefix search: Insert a dictionary of words and then retrieve
all words with a given prefix efficiently.
- Spell checking or word validation: Quickly check if a word or prefix exists in a large dictionary.
- Word games (Boggle, crossword solving): Use a trie to guide DFS so you can prune search when prefix is
not in any word.
- IP routing, T9 predictive text: (Tries can store sequences beyond just letters, e.g., bits or number presses)

Implement Trie (Prefix Tree) (Medium)

class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False

class Trie:
def __init__(self):
self.root = TrieNode()

def insert(self, word: str) -> None:

node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True

def search(self, word: str) -> bool:

node = self.root
for ch in word:
if ch not in node.children:
return False
node = node.children[ch]
return node.is_end

def startsWith(self, prefix: str) -> bool:

node = self.root
for ch in prefix:
if ch not in node.children:
return False
node = node.children[ch]
return True

Add and Search Word (Word Dictionary) (Medium)

Explanation: This is similar to Trie but with support for ‘.’ wildcard that can match any letter. We can
implement it by storing words in a Trie and then performing a DFS search: for each character in the query
word, if it’s a letter, go down that branch; if it’s '.', try all possible children at that node recursively. Use

51
recursion or backtracking for the search function, exploring all branches when encountering '.'.

class WordDictionary:
def __init__(self):
self.root = TrieNode() # reuse TrieNode from above

def addWord(self, word: str) -> None:

node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True

def search(self, word: str) -> bool:

def dfs(node, i):
if i == len(word):
return node.is_end
ch = word[i]
if ch == '.':
# try all possibilities
for child in node.children.values():
if dfs(child, i+1):
return True
return False
else:
if ch not in node.children:
return False
return dfs(node.children[ch], i+1)
return dfs(self.root, 0)

Word Search II (Hard)

Explanation: Given a board and a list of words, find all words in the board. Use a Trie to store all words, then
DFS from each board cell, following Trie branches. We can prune paths that are not prefixes of any word
using the Trie. Mark visited cells and backtrack. When a word is found (Trie node is_end True), add to result
and optionally mark as found (to avoid duplicates or to prune that word). This is efficient compared to
checking each word independently.

def findWords(board, words):

# Build trie of words
trie = TrieNode()
for w in words:
node = trie
for ch in w:
if ch not in node.children:

52
 node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
res = []
m, n = len(board), len(board[0])
def dfs(r, c, node, path):
char = board[r][c]
if char not in node.children:
return
nxt_node = node.children[char]
path += char
if nxt_node.is_end:
res.append(path)
nxt_node.is_end = False # avoid duplicates
# mark as visited
board[r][c] = '#'
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = r+dr, c+dc
if 0 <= nr < m and 0 <= nc < n and board[nr][nc] != '#':
dfs(nr, nc, nxt_node, path)
board[r][c] = char # backtrack
# Optional: prune leaf node
if not nxt_node.children:
node.children.pop(char)
for i in range(m):
for j in range(n):
dfs(i, j, trie, "")
return res

Replace Words (Medium)

Explanation: We have a dictionary of root words and a sentence. For each word in the sentence, replace it
with the shortest root that is a prefix of the word. Build a Trie of the root dictionary. Then for each word in
sentence, traverse the Trie character by character. If we reach a node that is_end (root word found), or we
run out of trie path, we stop. Use the accumulated prefix if ended on a root; otherwise keep the original
word. This ensures we find the shortest root prefix.

def replaceWords(dictionary, sentence):

trie = TrieNode()
for root in dictionary:
node = trie
for ch in root:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def replace(word):

53
 node = trie
prefix = ""
for ch in word:
if ch not in node.children or node.is_end:
break
node = node.children[ch]
prefix += ch
if node.is_end:
return prefix
return word
return " ".join(replace(word) for word in sentence.split())

Longest Word in Dictionary (Medium)

Explanation: Find the longest word in a list of words that can be built one character at a time by other words
in the list. Tries can help by inserting all words and marking end-of-word. Then perform a DFS on the Trie,
only traversing into children that are end-of-word (meaning that prefix exists in dictionary). Track the
longest word (or lexicographically smallest if equal length). Alternatively, sort words and use a set, but the
Trie DFS is a neat approach.

def longestWord(words):
trie = TrieNode()
# Insert all words into trie
for word in words:
node = trie
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
longest = ""
# DFS function
def dfs(node, path):
nonlocal longest
# Update longest if current path is a valid word and is longer or
lexicographically smaller
if node.is_end:
if len(path) > len(longest) or (len(path) == len(longest) and path <
longest):
longest = path
else:
return
for ch, child in node.children.items():
dfs(child, path + ch)
# Start DFS from root, with empty path
for ch, child in trie.children.items():

54
 dfs(child, ch)
return longest

Dynamic Programming
Dynamic Programming (DP) is an optimization technique for problems that can be broken down into
overlapping subproblems. It typically involves storing results of subproblems (memoization or tabulation)
to avoid recomputation. Key ingredients are optimal substructure (the optimal solution can be constructed
from optimal solutions of subproblems) and overlapping subproblems.

Common uses/patterns: - 1D DP for sequences: e.g., Fibonacci, climbing stairs, house robber (making a
choice at each step), etc. These often use an array dp[i] representing the best value for subproblem ending
at i.
- 2D DP for sequences comparison or grid problems: e.g., Longest Common Subsequence, Edit Distance
(DP table filling), grid unique paths or path sums (dp[i][j] depends on neighbors).
- DP on subsets (bit DP): e.g., Traveling Salesman Problem or bitmask DP for smaller sets.
- DP with two sequences or strings: e.g., LCS, edit distance, typically a matrix with dimensions of input
sizes.
- State machine DP: e.g., stock problems with buy/sell state, DP state can represent something like
"holding stock" vs "not holding".

Climbing Stairs (Easy)

def climbStairs(n):
if n <= 2:
return n
a, b = 1, 2 # ways to climb to step 1 and 2
for i in range(3, n+1):
a, b = b, a + b # Fibonacci sequence essentially
return b

House Robber (Medium)

Explanation: Use DP to decide whether to rob each house. Let dp[i] be the maximum amount that can be
robbed from houses up to index i. Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) – either skip the current
house or rob it (then you must have skipped i-1). Initialize dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
This runs in O(n) time and O(n) or O(1) space (we can keep just two variables for dp[i-1] and dp[i-2]).

def rob(nums):
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])

55
 for i in range(2, n):
curr = max(prev1, prev2 + nums[i])
prev2, prev1 = prev1, curr
return prev1

House Robber II (Medium)

Explanation: Similar to House Robber, but houses are in a circle, so the first and last cannot both be robbed.
We handle this by doing two DP runs: one for the range [0...n-2] and one for [1...n-1], then take the max of
the two results (rob first house or not). Edge cases for small n must be handled.

def robCircle(nums):
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
def rob_linear(arr):
prev2, prev1 = 0, 0
for val in arr:
prev2, prev1 = prev1, max(prev1, prev2 + val)
return prev1
# Max of robbing 0 to n-2, or 1 to n-1
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

Coin Change (Medium)

Explanation: We want the minimum number of coins needed to make up a given amount. Use DP where
dp[x] = minimum coins to get sum x. Initialize dp[0] = 0 and others to infinity. For each coin value, for each x
from coin to amount, update dp[x] = min(dp[x], dp[x - coin] + 1). This is a unbounded knapSack type, coin
can be used multiple times. Final answer dp[amount] or -1 if it’s infinity (not reachable). Complexity
O(amount * number_of_coins).

def coinChange(coins, amount):

max_val = float('inf')
dp = [0] + [max_val] * amount
for coin in coins:
for x in range(coin, amount + 1):
if dp[x - coin] != max_val:
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != max_val else -1

Longest Increasing Subsequence (Medium)

Explanation: Classic DP: dp[i] = length of LIS ending at index i. For each i, look at all j < i and if nums[j] <
nums[i], dp[i] = max(dp[i], dp[j] + 1). Then answer is max(dp). This is O(n^2). There is also a patience sorting

56
method that is O(n log n) using a separate array to store the current LIS tails, but the DP approach is
simpler to implement.

def lengthOfLIS(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n
best = 1
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
best = max(best, dp[i])
return best

Longest Common Subsequence (Medium)

Explanation: Use a 2D DP table where dp[i][j] = length of LCS of text1[:i] and text2[:j]. If last characters match
(text1[i-1] == text2[j-1]), then dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Build up from
dp[0][] = 0 and dp[][0] = 0. Complexity O(m*n) for lengths m, n.

def longestCommonSubsequence(text1, text2):

m, n = len(text1), len(text2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]

Longest Palindromic Subsequence (Medium)

Explanation: Use DP on string where dp[i][j] = length of longest palindromic subsequence in s[i...j]. If s[i] ==
s[j], then dp[i][j] = 2 + dp[i+1][j-1]; else dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Solve for all lengths from 1 to n.
This is O(n^2).

def longestPalindromeSubseq(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
# length 1 substrings are palindromes of length 1
for i in range(n):
dp[i][i] = 1

57
 for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = 2 + (dp[i+1][j-1] if j-1 >= i+1 else 0)
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1]

Edit Distance (Hard)

Explanation: Use DP matrix of size (m+1)x(n+1) where dp[i][j] = minimum edit distance between word1[:i]
and word2[:j]. Recurrence: if word1[i-1] == word2[j-1], dp[i][j] = dp[i-1][j-1] (no operation); else consider
insert, delete, replace: - insert cost = dp[i][j-1] + 1, - delete cost = dp[i-1][j] + 1, - replace cost = dp[i-1][j-1] + 1.
Take min of these. Initialize base cases: dp[i][0] = i (all deletes), dp[0][j] = j (all inserts). Complexity O(m*n).

def minDistance(word1, word2):

m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
dp[i][0] = i
for j in range(1, n+1):
dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
return dp[m][n]

Decode Ways (Medium)

Explanation: Count the number of ways to decode a string of digits to letters (where '1'->'A', ... '26'->'Z'). Let
dp[i] be ways to decode up to index i (1-indexed for string positions). Recurrence: if s[i-1] != '0', then dp[i] +=
dp[i-1] (decode single digit); if the two-digit number s[i-2:i] is between "10" and "26", then dp[i] += dp[i-2]
(decode two-digit together). Initialize dp[0] = 1 (empty string) and dp[1] depends on first char (if not '0').
Complexity O(n).

def numDecodings(s):
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n+1)
dp[0] = 1
dp[1] = 1

58
 for i in range(2, n+1):
# single digit decode
if s[i-1] != '0':
dp[i] += dp[i-1]
# two-digit decode
two_digit = int(s[i-2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i-2]
return dp[n]

Word Break (Medium)

Explanation: Determine if a string can be segmented into dictionary words. Use DP where dp[i] means s[:i]
can be segmented. Initialize dp[0] = True. Then for each i from 1..n, check for any j < i such that dp[j] is True
and s[j:i] is a word in the dict. If found, set dp[i] = True and break. Finally return dp[n]. Complexity O(n^2)
worst-case (or optimized with tries or indexing by word lengths).

def wordBreak(s, wordDict):

word_set = set(wordDict)
n = len(s)
dp = [False] * (n+1)
dp[0] = True
for i in range(1, n+1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]

Unique Paths (Medium)

Explanation: On an m x n grid, count paths from top-left to bottom-right moving only down or right. DP
solution: dp[i][j] = dp[i-1][j] + dp[i][j-1], with base of first row and first column all 1s (only one way straight
right or straight down). This is basically combinations but DP is intuitive. Complexity O(m*n).

def uniquePaths(m, n):

dp = [[1]*n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]

Jump Game (Medium)

Explanation: Greedy can solve this but DP thinking: define a variable reachable = 0 meaning the furthest
index we can reach so far. Iterate through array; if index i is <= reachable, we can jump from it, update

59
reachable = max(reachable, i + nums[i]) . If reachable >= last index, return True. If we finish loop
and last index not reachable, return False. O(n).

def canJump(nums):
reachable = 0
for i, jump in enumerate(nums):
if i > reachable:
return False
reachable = max(reachable, i + jump)
return True

60