ZEESHAN IBRAR

Python AI / ML Developer

CODING & TECHNICAL INTERVIEW PREP

Medium Level · 9 Topic Areas · 30+ Problems · Variations, Traces & Complexity

Covers: Arrays · Sliding Window · Hash Maps · Linked Lists · Stacks · Binary Search · Trees · DP · Strings
How to Use This Document
Each problem follows this structure:
• Problem Statement — what the interviewer asks
• Approach — the mental model before writing any code
• Clean Solution — production-quality Python with inline comments
• Complexity Table — Time and Space with reasoning
• Execution Trace — step-by-step walkthrough of a key example
• Edge Cases — what to check before you start coding
• Variations Table — common twists on the same problem

💡 Interview Tip: In an interview, always talk through the approach before typing. Interviewers care as much
about your reasoning as your code.
SECTION 1: Arrays & Two Pointers
Two-pointer problems use two index variables that move toward or away from each other. The pattern
eliminates the need for a nested loop, reducing O(n²) brute force to O(n).
Core mental model: place one pointer at the start and one at the end. Move the pointer that gives you a better
candidate based on the current comparison.

1.1 Two Sum (Hash Map — O(n))

Problem: given a list of integers and a target, return the indices of the two numbers that add up to the target.
Exactly one solution exists.

Approach
For each number, compute its complement (target − current). If the complement is already in a hash map, you
found the pair. Otherwise, store the current number and its index.
Why hash map beats sorting: sorting returns values, not indices. The hash map approach preserves the
original indices in O(n) time.
def two_sum(nums: list[int], target: int) -> list[int]:
# seen maps: value → index
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i] # found the pair
seen[num] = i # store for future lookups
return [] # guaranteed solution exists

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(n) Single pass. Hash map stores
up to n entries.

Execution Trace — nums=[2,7,11,15], target=9

i=0 num=2 complement=7 seen={} → store {2:0}
i=1 num=7 complement=2 seen={2:0} → 2 IS in seen → return [0, 1] ✓

Edge Cases
• Duplicate values — [3, 3], target=6 — works because we store after checking
• Negative numbers — [-1, -2, -3], target=-5 — complement math handles negatives
• Zero — [0, 4, 3], target=4 — 0+4 is a valid pair

Variation Key Change in Approach

Two Sum II (sorted input) Use two pointers. Sum too small → move left right. Sum too
big → move right left. O(n) time, O(1) space.
Two Sum — count all pairs Use Counter. For each value check if complement exists
(handle same-element pairs with count ≥ 2).
Three Sum Sort first, then fix one element and two-pointer the rest. See
Section 1.3.
 Four Sum Extend Three Sum — fix two elements with two nested loops,
two-pointer for the remaining pair.

💡 Interview Tip: If the interviewer asks for all pairs (not just indices), switch to a set and yield tuples instead
of returning on first match.

1.2 Best Time to Buy and Sell Stock

Problem: given an array where prices[i] is the stock price on day i, return the maximum profit from one buy
and one sell. You must buy before you sell.

Approach
One pass. Track the minimum price seen so far (min_price). At each step compute the profit if you sold today
(price − min_price). Track the maximum of all such profits.
Key insight: you don't need to know the buy day explicitly — the running minimum captures it.
def max_profit(prices: list[int]) -> int:
if not prices:
return 0
min_price = float('inf')
max_profit = 0
for price in prices:
if price < min_price:
min_price = price # found cheaper buy day
elif price - min_price > max_profit:
max_profit = price - min_price # better profit found
return max_profit

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Single pass, two scalar
variables only.

Execution Trace — prices=[7,1,5,3,6,4]

price=7 min=7 profit=0
price=1 min=1 profit=0 ← new minimum
price=5 min=1 profit=4 ← sell at 5, bought at 1
price=3 min=1 profit=4
price=6 min=1 profit=5 ← best profit: sell at 6, buy at 1
price=4 min=1 profit=5
Return: 5

Variation Key Change in Approach

Prices all decreasing min keeps resetting, max_profit stays 0. Correct — no
profitable trade.
Multiple transactions allowed Greedy: add every positive consecutive difference. O(n) time,
O(1) space.
At most 2 transactions DP with states: hold1, profit1, hold2, profit2. O(n) time, O(1)
space.
Cooldown (1-day wait) DP with states: held, sold, rest. Transition: rest=max(rest,sold).
1.3 Three Sum
Problem: find all unique triplets in the array that sum to zero. No duplicate triplets in the output.

Approach
Sort the array. For each element nums[i], use two pointers (left=i+1, right=end) to find pairs that sum to
−nums[i]. Skipping duplicates is handled by advancing pointers past repeated values.
def three_sum(nums: list[int]) -> list[list[int]]:
[Link]() # O(n log n) — enables two-pointer
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicate fixed element
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
[Link]([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1
right -= 1
elif total < 0:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return result

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n²) O(1) extra Sorting is O(n log n). Outer loop
× two-pointer = O(n²).

Edge Cases
• All zeros — [0,0,0,0] → [[0,0,0]] only once
• Fewer than 3 elements → return []
• All positive or all negative → no valid triplets

Variation Key Change in Approach

Closest Three Sum Track min abs difference. Update result when |total−target|
decreases. Same O(n²).
Four Sum Add an outer loop over i, call three_sum logic for remaining
slice. O(n³).
Count triplets (not return) Increment counter instead of appending. Same complexity.

1.4 Container With Most Water

Problem: given heights of vertical lines on the x-axis, find two lines that together with the x-axis form a
container that holds the most water.

Approach
Two pointers at both ends. Area = min(height[left], height[right]) × (right − left). The limiting factor is the
shorter line — moving the shorter pointer inward is the only way to potentially find a taller boundary.
 def max_area(height: list[int]) -> int:
left, right = 0, len(height) - 1
best = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
best = max(best, area)
if height[left] <= height[right]: # move the shorter side
left += 1
else:
right -= 1
return best

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Each pointer moves at most n
times total.

💡 Interview Tip: The greedy proof: keeping the taller line and shrinking the width can never increase area
(min stays same or decreases, width decreases). Only chance is moving the shorter line to something taller.

1.5 Move Zeroes (In-Place)

Problem: move all zeros in the array to the end while maintaining the relative order of non-zero elements. Do
it in-place without returning a new array.

Approach
Use a write pointer that only advances when a non-zero element is placed. After the first pass, fill the
remaining positions with zeros.
def move_zeroes(nums: list[int]) -> None:
write = 0 # position for next non-zero
for read in range(len(nums)):
if nums[read] != 0:
nums[write] = nums[read]
write += 1
# fill rest with zeros
while write < len(nums):
nums[write] = 0
write += 1

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Two passes, no extra array.

Variation Key Change in Approach

Move specific value to end Replace != 0 check with != target_value.

Maintain order + minimise writes Two-pointer swap: swap nums[write] with nums[read] when
non-zero. Avoids second pass.
Remove element in-place Same write-pointer pattern; don't fill the tail — just return write
as new length.
SECTION 2: Sliding Window
Sliding window problems involve a contiguous sub-array or sub-string whose size is either fixed or variable.
The key insight: instead of re-computing the window from scratch on each step, maintain running state and
update it incrementally.
Rule of thumb: if a problem asks for the longest/shortest contiguous sub-array satisfying a condition, sliding
window is likely optimal.

2.1 Longest Substring Without Repeating Characters

Problem: given a string, return the length of the longest substring that contains no repeating characters.

Approach
Expand the window by moving right. If s[right] is already in the current window, shrink from the left until the
duplicate is removed. A hash map stores each character's most recent index for O(1) left-pointer jumps.
def length_of_longest_substring(s: str) -> int:
char_index = {} # char → last seen index
left = 0
best = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
# jump left past the duplicate
left = char_index[char] + 1
char_index[char] = right
best = max(best, right - left + 1)
return best

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(min(n, 26)) Each character visited at most
twice (right expands, left
jumps). Map ≤ alphabet size.

Execution Trace — s="abcabcbb"

right=0 a left=0 window='a' best=1
right=1 b left=0 window='ab' best=2
right=2 c left=0 window='abc' best=3
right=3 a a seen at 0 ≥ left(0) → left=1 window='bca' best=3
right=4 b b seen at 1 ≥ left(1) → left=2 window='cab' best=3
right=5 c c seen at 2 ≥ left(2) → left=3 window='abc' best=3
right=6 b b seen at 4 ≥ left(3) → left=5 window='cb' best=3
right=7 b b seen at 6 ≥ left(5) → left=7 window='b' best=3
Return: 3

Variation Key Change in Approach

At most k distinct characters Use a frequency map. Shrink window when map size > k.

Longest with at most 2 distinct k=2 specialisation. Common in interview follow-ups.

Minimum window containing all See Section 2.3 — different shrink condition.
chars
2.2 Maximum Sum Subarray of Size K
Problem: given an array of integers and integer k, find the maximum sum of any contiguous subarray of length
exactly k.

Approach
Build the first window by summing the first k elements. Then slide: add the incoming element on the right,
subtract the outgoing element on the left. Track the running maximum.
def max_sum_subarray(nums: list[int], k: int) -> int:
if len(nums) < k:
return 0
window_sum = sum(nums[:k]) # O(k) seed
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # slide
best = max(best, window_sum)
return best

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Seed is O(k) ≤ O(n). One more
pass for the slide.

Execution Trace — nums=[2,1,5,1,3,2], k=3

Initial window [2,1,5] sum=8 best=8
Slide: +1 -2 → [1,5,1] sum=7 best=8
Slide: +3 -1 → [5,1,3] sum=9 best=9
Slide: +2 -5 → [1,3,2] sum=6 best=9
Return: 9

Variation Key Change in Approach

Variable window — max sum ≥ S Expand right until sum ≥ S, then shrink left while still ≥ S.

Minimum length subarray with sum ≥ Track minimum window length when condition is met. Classic
S follow-up.

Maximum product subarray Track both max and min products (negatives flip sign). O(n)
DP.

2.3 Minimum Window Substring

Problem: given strings s and t, return the minimum window in s that contains every character of t (including
duplicates). Return empty string if none exists.

Approach
Expand the right pointer to include required characters. Once all of t is covered (formed == required), shrink
from the left to minimise the window. Update the best answer on each valid window.
from collections import Counter

def min_window(s: str, t: str) -> str:

if not t or not s:
return ''
need = Counter(t) # required char frequencies
have = {} # current window frequencies
required = len(need) # distinct chars we must satisfy
formed = 0 # distinct chars currently satisfied
 left = 0
best = (float('inf'), 0, 0) # (length, left, right)

for right, char in enumerate(s):

have[char] = [Link](char, 0) + 1
if char in need and have[char] == need[char]:
formed += 1

while formed == required: # valid window — try to shrink

if right - left + 1 < best[0]:
best = (right - left + 1, left, right)
lc = s[left]
have[lc] -= 1
if lc in need and have[lc] < need[lc]:
formed -= 1
left += 1

return '' if best[0] == float('inf') else s[best[1]: best[2]+1]

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(|s| + |t|) O(|s| + |t|) Each char enters and leaves
the window once. Two
frequency maps.

💡 Interview Tip: This is the hardest sliding window problem. The 'formed' counter tracks how many distinct
characters are fully satisfied — cleaner than checking the entire map each iteration.
SECTION 3: Hash Maps & Sets
Hash maps give O(1) average-case lookup, insert, and delete. They are the answer whenever you need:
frequency counting, fast existence checking, caching previously seen values, or grouping items by a
computed key.

3.1 Valid Anagram

Problem: given two strings s and t, return true if t is an anagram of s (contains exactly the same characters
with the same frequencies).
def is_anagram(s: str, t: str) -> bool:
if len(s) != len(t): # quick length check
return False
count = {}
for c in s:
count[c] = [Link](c, 0) + 1
for c in t:
if c not in count:
return False
count[c] -= 1
if count[c] < 0:
return False
return True
# One-liner alternative: return Counter(s) == Counter(t)

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Alphabet size ≤ 26 for
lowercase — map is bounded.

Variation Key Change in Approach

Unicode / arbitrary chars Same algorithm, but O(k) space where k = unique chars.
Group anagrams together Sort each word as key → group words by key. See Section
3.2.
Find all anagram start indices Sliding window of length len(p) over s. Compare frequency
maps.

3.2 Group Anagrams

Problem: given an array of strings, group the anagrams together. Each group can be in any order.

Approach — Sorted Key

Sort each word alphabetically to get its canonical key. All anagrams share the same sorted key. Use a hash
map: key → list of original words.
def group_anagrams(strs: list[str]) -> list[list[str]]:
groups = {}
for word in strs:
key = ''.join(sorted(word)) # 'eat','tea','ate' → 'aet'
if key not in groups:
groups[key] = []
groups[key].append(word)
return list([Link]())
 ⏱ Time Complexity 💾 Space Complexity 📝 Notes
O(n · k log k) O(n · k) n words, k = max word length.
Sorting each word costs k log k.

Faster Alternative — Frequency Tuple Key

Represent each word as a tuple of 26 character counts. Avoids the sort — O(k) per word instead of O(k log k).
def group_anagrams_fast(strs):
groups = {}
for word in strs:
key = tuple([Link](chr(ord('a')+i)) for i in range(26))
[Link](key, []).append(word)
return list([Link]())

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n · k) O(n · k) Frequency tuple is O(k). Better
when k is large.

3.3 Subarray Sum Equals K

Problem: given an integer array and integer k, return the total number of subarrays whose sum equals k.

Approach — Prefix Sum + Hash Map

The sum of subarray [i+1..j] equals prefix[j] − prefix[i]. So if prefix[j] − k exists in the map, we found a subarray.
Maintain a running prefix sum and count how many times each prefix has appeared.
def subarray_sum(nums: list[int], k: int) -> int:
count = 0
prefix = 0
freq = {0: 1} # empty prefix exists once
for num in nums:
prefix += num
# how many previous prefixes equal prefix - k?
count += [Link](prefix - k, 0)
freq[prefix] = [Link](prefix, 0) + 1
return count

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(n) Single pass. Hash map stores
each unique prefix sum once.

Execution Trace — nums=[1,1,1], k=2

prefix=0 freq={0:1}
num=1 prefix=1 look for 1-2=-1 [Link](-1)=0 freq={0:1,1:1} count=0
num=1 prefix=2 look for 2-2=0 [Link](0)=1 freq={0:1,1:2,2:1} count=1
num=1 prefix=3 look for 3-2=1 [Link](1)=2 freq={...3:1} count=3
Return: 3 (subarrays [1,1] starting at index 0 and 1, and [1,1,1] doesn't equal 2)
Correction: subarrays are nums[0:2]=[1,1] and nums[1:3]=[1,1] → 2 subarrays of sum 2

💡 Interview Tip: The {0:1} initialisation handles the case where the entire prefix from index 0 equals k —
without it you'd miss those subarrays.
SECTION 4: Linked Lists
Linked list problems almost always involve one of three techniques: two pointers at different speeds
(fast/slow), reversing pointers in-place, or using a dummy head node to simplify edge cases.
class ListNode:
def __init__(self, val=0, next=None):
[Link] = val
[Link] = next

4.1 Reverse Linked List

Problem: reverse a singly linked list and return the new head.

Iterative Approach (preferred in interviews)

def reverse_list(head: ListNode) -> ListNode:
prev = None
curr = head
while curr:
next_node = [Link] # save next before overwriting
[Link] = prev # reverse the pointer
prev = curr # advance prev
curr = next_node # advance curr
return prev # prev is now the new head

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) One pass. Three pointer
variables — no extra space.

Execution Trace — 1→2→3→None

prev=None curr=1: next=2 [Link]=None prev=1 curr=2 List: None←1 2→3
prev=1 curr=2: next=3 [Link]=1 prev=2 curr=3 List: None←1←2 3
prev=2 curr=3: next=None [Link]=2 prev=3 curr=None List: None←1←2←3
Return prev = 3 (new head) → 3→2→1→None ✓

Variation Key Change in Approach

Recursive reversal reverse([Link]), then [Link] = head, [Link] =
None. O(n) space (call stack).
Reverse between positions i and j Find node before i, reverse sublist, reconnect. O(n) time.

Reverse k-group Recursively reverse every k nodes. O(n) time, O(n/k) recursion
space.

4.2 Detect Cycle in Linked List (Floyd's Algorithm)

Problem: given a linked list, return True if it contains a cycle.

Approach — Fast and Slow Pointers

Move slow one step and fast two steps. If they ever meet, there is a cycle. If fast reaches null, there is no
cycle. Floyd's tortoise-and-hare proof: in a cycle of length L, after at most L steps the two pointers will be in
the same cycle and will converge within L more steps.
 def has_cycle(head: ListNode) -> bool:
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
if slow is fast:
return True
return False

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Pointers move at most 2n steps
before meeting or exiting. No
extra storage.

Variation Key Change in Approach

Find cycle start node After meeting, reset one pointer to head. Move both one step
at a time — they meet at the cycle start. Mathematical proof
based on distances.
Find cycle length After detecting cycle, keep slow fixed, advance fast until it
returns to slow. Count steps.
Middle of linked list Fast/slow with no cycle: when fast reaches end, slow is at the
middle.

4.3 Merge Two Sorted Lists

Problem: merge two sorted linked lists and return the merged list (sorted). Do not create new nodes.

Approach — Dummy Head

Use a dummy head node to avoid special-casing the start of the result list. Compare current nodes from both
lists, attach the smaller one, advance that pointer. Attach the remaining non-null list at the end.
def merge_two_lists(l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) # sentinel — [Link] will be our result
curr = dummy
while l1 and l2:
if [Link] <= [Link]:
[Link] = l1
l1 = [Link]
else:
[Link] = l2
l2 = [Link]
curr = [Link]
[Link] = l1 or l2 # attach remaining
return [Link]

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n + m) O(1) n and m are lengths of the two
lists. Pointer manipulation only.

Variation Key Change in Approach

Merge k sorted lists Use a min-heap of size k. Push (val, node) for each list head.
Pop min, push next from same list. O(n log k).
 Sort linked list Merge sort: split at middle (fast/slow), recursively sort each
half, merge. O(n log n) time, O(log n) stack.

4.4 Find Middle of Linked List

Problem: return the middle node. If even length, return the second middle.
def middle_node(head: ListNode) -> ListNode:
slow = fast = head
while fast and [Link]:
slow = [Link]
fast = [Link]
return slow

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Fast pointer covers the list in
one pass. Slow lands at the
middle.

💡 Interview Tip: Combining middle-finding with reversal is the basis for palindrome linked list detection: find
middle, reverse second half, compare both halves.
SECTION 5: Stacks & Queues
A stack is LIFO — last in, first out. Use it whenever you need to track a 'pending' item that will be resolved by
a future item (brackets, temperatures, next greater element). In Python, use a list as a stack (append / pop
from the right end).

5.1 Valid Parentheses

Problem: given a string of brackets, return True if every opening bracket is closed in the correct order.
def is_valid(s: str) -> bool:
stack = []
mapping = {')': '(', '}': '{', ']': '['}
for char in s:
if char in mapping: # closing bracket
top = [Link]() if stack else '#'
if mapping[char] != top:
return False
else: # opening bracket
[Link](char)
return len(stack) == 0 # all opened brackets were closed

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(n) Each char processed once.
Stack holds at most n/2 open
brackets.

Edge Cases
• Empty string → True
• Single bracket → False
• Interleaved wrong types → ([)] → False
• Extra unclosed open → ((( → False (stack not empty at end)

Variation Key Change in Approach

Minimum add to make valid Count unmatched open and close brackets separately. Sum =
additions needed.
Minimum remove to make valid Two passes: forward to remove unmatched ), backward to
remove unmatched (.
Longest valid parentheses DP or stack-based. Track indices of unmatched brackets.

5.2 Daily Temperatures (Monotonic Stack)

Problem: given temperatures array, for each day return the number of days until a warmer temperature.
Return 0 if no future warmer day exists.

Approach — Monotonic Decreasing Stack

Maintain a stack of indices where temperatures are in decreasing order. When a warmer day arrives, pop all
cooler days from the stack and compute the wait.
def daily_temperatures(temps: list[int]) -> list[int]:
 result = [0] * len(temps)
stack = [] # stores indices, temps in decreasing order
for i, temp in enumerate(temps):
# pop all days cooler than today
while stack and temps[stack[-1]] < temp:
j = [Link]()
result[j] = i - j # days waited
[Link](i)
return result # unpopped indices stay 0 (no warmer day)

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(n) Each index pushed and popped
exactly once. Stack holds at
most n indices.

Execution Trace — temps=[73,74,75,71,69,72,76,73]

i=0 73: stack=[0]
i=1 74: 74>73 → pop 0, result[0]=1; stack=[1]
i=2 75: 75>74 → pop 1, result[1]=1; stack=[2]
i=3 71: stack=[2,3]
i=4 69: stack=[2,3,4]
i=5 72: 72>69 pop 4 result[4]=1; 72>71 pop 3 result[3]=2; stack=[2,5]
i=6 76: 76>72 pop 5 result[5]=1; 76>75 pop 2 result[2]=4; stack=[6]
i=7 73: stack=[6,7]
Result: [1,1,4,2,1,1,0,0]

Variation Key Change in Approach

Next greater element Same pattern. Stack stores values instead of indices since we
don't need distance.
Previous greater element Process left-to-right, pop when current > top. The top when not
popped is the answer.
Stock span problem Monotonic stack counting consecutive days ≤ current price.
Classic variation.

5.3 Min Stack

Problem: design a stack that supports push, pop, top, and getMin — all in O(1) time.

Approach
Maintain a parallel min_stack alongside the main stack. Each entry in min_stack records the minimum of
everything currently in the main stack up to that point. On push, append min(val, min_stack[-1]). On pop, pop
from both.
class MinStack:
def __init__(self):
[Link] = []
self.min_stack = []

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

[Link](val)
current_min = min(val, self.min_stack[-1] if self.min_stack else val)
self.min_stack.append(current_min)

def pop(self) -> None:

[Link]()
 self.min_stack.pop()

def top(self) -> int:

return [Link][-1]

def getMin(self) -> int:

return self.min_stack[-1]

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(1) all ops O(n) Doubling the stack space to
avoid re-scanning for minimum
on every call.
SECTION 6: Binary Search
Binary search eliminates half the search space on each step. The classic form requires a sorted array, but the
pattern generalises to any problem where the answer space is monotonic — if a value x works, then x-1 also
works (or doesn't work).
Template: left=0, right=len-1. Loop while left ≤ right. Compute mid=(left+right)//2. Move left or right based on
the comparison at mid.

6.1 Classic Binary Search

Problem: given a sorted array, return the index of target. Return -1 if not found.
def binary_search(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2 # avoids integer overflow
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(log n) O(1) Halves the search space each
iteration. No recursion needed.

Execution Trace — nums=[1,3,5,7,9,11], target=7

left=0 right=5 mid=2 nums[2]=5 < 7 → left=3
left=3 right=5 mid=4 nums[4]=9 > 7 → right=3
left=3 right=3 mid=3 nums[3]=7 == 7 → return 3 ✓

Variation Key Change in Approach

Find first/last occurrence After finding target, continue searching left (or right) half to find
boundary.
Count occurrences last_occurrence − first_occurrence + 1. Two binary searches.

Search insert position Return left after the loop — left points to where target would be
inserted.

6.2 Search in Rotated Sorted Array

Problem: a sorted array has been rotated at some pivot. Find the index of target in O(log n).

Approach
At each mid, one half of the array is always sorted. Determine which half is sorted by comparing nums[left]
and nums[mid]. Check if target falls in the sorted half — if so, search there. Otherwise search the other half.
def search_rotated(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
 mid = (left + right) // 2
if nums[mid] == target:
return mid
# left half is sorted
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1 # target in sorted left half
else:
left = mid + 1 # target in right half
# right half is sorted
else:
if nums[mid] < target <= nums[right]:
left = mid + 1 # target in sorted right half
else:
right = mid - 1 # target in left half
return -1

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(log n) O(1) Still halves the space each step
despite the rotation.

Variation Key Change in Approach

Find rotation pivot Binary search for the single point where nums[i] > nums[i+1].
O(log n).
Rotated array with duplicates When nums[left]==nums[mid], cannot determine sorted side.
Left += 1. Worst case O(n).
Find minimum in rotated array Binary search: move toward the side that breaks ascending
order.

6.3 Binary Search on Answer — Koko Eating Bananas

Problem: Koko must eat all piles of bananas in h hours. She eats at speed k bananas/hour (one pile per hour,
leftover if pile < k). Find the minimum k.

Approach — Search the Answer Space

The answer k lies in [1, max(piles)]. Binary search on k: for a given speed, compute hours needed. If hours ≤
h, try slower (right=mid). If hours > h, must go faster (left=mid+1).
import math

def min_eating_speed(piles: list[int], h: int) -> int:

def can_finish(speed: int) -> bool:
return sum([Link](pile / speed) for pile in piles) <= h

left, right = 1, max(piles)

while left < right: # find leftmost valid speed
mid = (left + right) // 2
if can_finish(mid):
right = mid # mid works, try slower
else:
left = mid + 1 # too slow
return left

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n log m) O(1) n = len(piles), m = max(piles).
Binary search on m, each check
costs n.

💡 Interview Tip: This pattern — binary search on the answer space rather than an array — applies to:
minimum ship capacity, split array largest sum, divide chocolates, etc. The key is a monotonic feasibility
function.
SECTION 7: Trees
Tree problems reduce to two traversal strategies: Depth-First Search (DFS — recurse into children, use the
call stack) and Breadth-First Search (BFS — process level by level, use a queue). DFS is simpler to code
recursively; BFS is needed for level-order results or shortest path in unweighted trees.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
[Link] = val; [Link] = left; [Link] = right

7.1 Maximum Depth of Binary Tree

Problem: return the maximum depth (number of nodes on the longest root-to-leaf path).
def max_depth(root: TreeNode) -> int:
if not root: # base case: empty tree
return 0
left_depth = max_depth([Link])
right_depth = max_depth([Link])
return 1 + max(left_depth, right_depth)

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(h) Every node visited once. Stack
depth = tree height h. O(log n)
balanced, O(n) skewed.

Variation Key Change in Approach

Minimum depth Take min instead of max, BUT only when both children exist
(min_depth of a leaf is 1, not min of null=0).
Iterative (BFS) Use a deque. Increment depth counter each time you start a
new level. O(n) time, O(w) space where w = max width.
Diameter of binary tree At each node, diameter candidate = left_height + right_height.
Track global max via closure or nonlocal.

7.2 Binary Tree Level Order Traversal

Problem: return node values grouped by level [[root], [level1...], [level2...]].

Approach — BFS with Queue

from collections import deque

def level_order(root: TreeNode) -> list[list[int]]:

if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue) # number of nodes at current level
level = []
for _ in range(level_size):
node = [Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])
 [Link](level)
return result

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(w) Every node enqueued and
dequeued once. Queue holds at
most one full level (max width
w).

Variation Key Change in Approach

Zigzag level order Alternate appending level left-to-right vs right-to-left using a
flag.
Right side view From each level, take only the last element.

Average of each level Compute sum(level)/len(level) for each level list.

7.3 Validate Binary Search Tree

Problem: determine if a binary tree is a valid BST (left subtree values < node < right subtree values,
recursively).

Approach — Passing Bounds

Pass a (min_val, max_val) constraint to each recursive call. Every node must satisfy min_val < [Link] <
max_val.
def is_valid_bst(root: TreeNode) -> bool:
def validate(node, low, high):
if not node:
return True
if not (low < [Link] < high):
return False
return (validate([Link], low, [Link]) and
validate([Link], [Link], high))
return validate(root, float('-inf'), float('inf'))

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(h) Every node visited once.
Recursion depth = tree height.

💡 Interview Tip: Common mistake: only checking that [Link] < [Link]. This misses the case where a right
subtree node is less than an ancestor. The bounds propagation catches this.

Variation Key Change in Approach

In-order traversal check In-order traversal of a valid BST produces a strictly increasing
sequence. Compare each value to the previous. O(n) time,
O(h) stack.
Find kth smallest in BST In-order traversal, count to k. With an augmented tree, O(h).
Lowest common ancestor (BST) If both values < root go left; if both > root go right; else root is
the LCA.
7.4 Lowest Common Ancestor (Binary Tree — not BST)
Problem: find the lowest node that has both p and q as descendants (a node is a descendant of itself).
def lowest_common_ancestor(root, p, q):
if not root or root is p or root is q:
return root
left = lowest_common_ancestor([Link], p, q)
right = lowest_common_ancestor([Link], p, q)
if left and right: # p found in one subtree, q in the other
return root
return left or right # both in same subtree

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(h) Visits every node in worst case.
Stack depth proportional to
height.
SECTION 8: Dynamic Programming
DP solves problems by breaking them into overlapping subproblems and caching the results. Ask two
questions: (1) What is the subproblem? (2) How does the solution to a larger problem depend on solutions to
smaller ones (the recurrence)?
Start with top-down (memoisation with recursion). If recursion overhead is a concern, convert to bottom-up
(tabulation with an array). Often you can reduce space from O(n) to O(1) by observing the recurrence only
looks back a fixed number of steps.

8.1 Climbing Stairs

Problem: you can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

Recurrence: dp[i] = dp[i-1] + dp[i-2] (Fibonacci)

def climb_stairs(n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
curr = prev1 + prev2
prev2, prev1 = prev1, curr
return prev1

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Rolling two variables instead of
an n-length array.

Variation Key Change in Approach

Up to k steps at once dp[i] = sum(dp[i-1] ... dp[i-k]). Maintain a sliding window sum.
O(n) time, O(k) space.
Minimum cost to climb stairs dp[i] = min(dp[i-1], dp[i-2]) + cost[i]. Classic 'min cost' DP.

8.2 Coin Change (Minimum Coins)

Problem: given coins of different denominations and a total amount, return the minimum number of coins
needed. Return -1 if impossible.

Recurrence: dp[i] = min(dp[i - coin] + 1) for each coin ≤ i

def coin_change(coins: list[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # base case: 0 coins to make 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1

⏱ Time Complexity 💾 Space Complexity 📝 Notes

 O(amount × |coins|) O(amount) Fill dp array of size amount+1.
Inner loop over all coin
denominations.

Execution Trace — coins=[1,2,5], amount=6

dp = [0, inf, inf, inf, inf, inf, inf]
i=1: coin=1 dp[0]+1=1 → dp[1]=1
i=2: coin=1 dp[1]+1=2, coin=2 dp[0]+1=1 → dp[2]=1
i=3: coin=1 →2, coin=2 →2 → dp[3]=2
i=4: coin=1 →3, coin=2 →2 → dp[4]=2
i=5: coin=1 →3, coin=2 →3, coin=5 dp[0]+1=1 → dp[5]=1
i=6: coin=1 →2, coin=2 →2, coin=5 →2 → dp[6]=2
Return: 2 (5+1 or 2+2+2)

Variation Key Change in Approach

Count ways to make amount dp[i] += dp[i-coin] instead of min. Counts combinations.

Unbounded knapsack Same DP structure — items can be reused unlimited times.

0/1 knapsack Process items in outer loop, amounts in reverse inner loop to
avoid reuse.

8.3 Longest Common Subsequence (LCS)

Problem: given two strings, return the length of their longest common subsequence (characters don't need to
be contiguous).

Recurrence
If s1[i] == s2[j]: dp[i][j] = dp[i-1][j-1] + 1
Else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
def lcs(s1: str, s2: str) -> int:
m, n = len(s1), len(s2)
# dp[i][j] = LCS length of s1[:i] and s2[:j]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[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]

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(m × n) O(m × n) Fill an (m+1)×(n+1) table. Can
reduce to O(n) space using two
rows.

Variation Key Change in Approach

Longest Common Substring Same DP but reset dp[i][j]=0 when chars differ. Track global
max.
Edit Distance (Levenshtein) dp[i][j] = min(insert, delete, replace). Replace costs 0 if chars
match.
 Shortest Common Supersequence Length = m + n - LCS. Reconstruct by tracing dp table.

8.4 House Robber

Problem: rob houses in a row. Adjacent houses cannot both be robbed. Maximise total stolen.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])

def rob(nums: list[int]) -> int:
if not nums: return 0
if len(nums) == 1: return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
curr = max(prev1, prev2 + nums[i])
prev2, prev1 = prev1, curr
return prev1

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(1) Rolling two variables.
Recurrence only depends on i-1
and i-2.

Variation Key Change in Approach

House Robber II (circular) Houses in a circle. Run rob twice: once excluding first house,
once excluding last. Take the max.
House Robber III (binary tree) DFS returning (rob_this, skip_this) pair for each subtree. O(n).

Delete and earn Choosing number i means removing all i-1 and i+1. Convert to
house robber: dp over value buckets.
SECTION 9: Strings
Strings are immutable in Python — any modification creates a new string. For frequent character-level
manipulation, convert to a list first. For pattern recognition in strings, sliding window and hash maps are the
dominant tools.

9.1 Valid Palindrome

Problem: given a string, return True if it reads the same forwards and backwards after keeping only
alphanumeric characters and lowercasing.
def is_palindrome(s: str) -> bool:
cleaned = [[Link]() for c in s if [Link]()]
left, right = 0, len(cleaned) - 1
while left < right:
if cleaned[left] != cleaned[right]:
return False
left += 1
right -= 1
return True
# One-liner: return cleaned == cleaned[::-1] (O(n) space)

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) O(n) Cleaning creates a new list of
up to n chars. Two-pointer
check is O(n).

Variation Key Change in Approach

Longest palindromic substring Expand Around Centre: for each index, expand outward while
chars match. O(n²) time, O(1) space.
Palindrome partitioning DP: precompute is_palindrome[i][j] in O(n²), then DP for
minimum cuts.
Valid palindrome II (delete one) Two pointers. On first mismatch, try skipping left or right char
and check the rest.

9.2 Longest Palindromic Substring

Problem: return the longest palindromic substring of s.

Approach — Expand Around Centre

A palindrome has a centre (one char for odd length, gap between two chars for even). Try expanding from
every centre. O(n²) time but O(1) space — no DP table needed.
def longest_palindrome(s: str) -> str:
def expand(left: int, right: int) -> str:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1 : right] # slice after final failed expansion

result = ''
for i in range(len(s)):
odd = expand(i, i) # odd-length palindrome
 even = expand(i, i+1) # even-length palindrome
if len(odd) > len(result): result = odd
if len(even) > len(result): result = even
return result

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n²) O(1) 2n centres, each expands up to
n/2 steps. No extra array.

💡 Interview Tip: Manacher's algorithm solves this in O(n) but is complex to implement under interview
pressure. Expand-around-centre is the expected answer unless the interviewer specifically asks for linear time.

9.3 Encode and Decode Strings

Problem: design an algorithm to encode a list of strings to a single string and decode it back. The strings may
contain any character including the delimiter.

Approach — Length-Prefix Encoding

Prefix each string with its length followed by a separator that will never conflict with content. Format:
"len#content". On decode, read the length, skip the separator, slice exactly that many characters.
class Codec:
def encode(self, strs: list[str]) -> str:
return ''.join(f'{len(s)}#{s}' for s in strs)

def decode(self, s: str) -> list[str]:

result = []
i = 0
while i < len(s):
j = [Link]('#', i) # find next delimiter
length = int(s[i:j])
[Link](s[j+1 : j+1+length])
i = j + 1 + length # advance past this token
return result

⏱ Time Complexity 💾 Space Complexity 📝 Notes

O(n) encode / O(n) O(n) n = total characters across all
decode strings.

Variation Key Change in Approach

Run-length encoding Compress consecutive identical characters. 'aaabbc' →
'3a2b1c'. O(n) time.
Serialize/deserialize binary tree BFS or pre-order with null markers. Use the decode pattern to
reconstruct.
SECTION 10: Big-O Cheat Sheet
Keep these in your head. Interviewers expect you to state complexity before you are asked.

Algorithm / Structure Time (avg) Space Notes

Two Sum (hash map) O(n) O(n) Single pass
Sorting (Python) O(n log n) O(n) Timsort
Binary Search O(log n) O(1) Array must be sorted
BFS / DFS on tree O(n) O(h) or O(w) h=height, w=width
Sliding Window O(n) O(k) k = window or alphabet
Merge Two Sorted Lists O(n+m) O(1) Pointer manipulation
DP — Coin Change O(n·k) O(n) n=amount, k=coins
DP — LCS O(m·n) O(m·n) Reducible to O(n) space
Three Sum O(n²) O(1) extra After O(n log n) sort
Reverse Linked List O(n) O(1) Iterative beats recursive
Valid Parentheses O(n) O(n) Stack holds open brackets
Monotonic Stack O(n) O(n) Each element pushed/popped
once
Floyd's Cycle Detection O(n) O(1) Fast+slow pointers
Prefix Sum O(n) build O(n) O(1) range queries after
Hash Map operations O(1) avg O(n) O(n) worst case (collisions)

Interview Dos and Don'ts

Before you type
• Repeat the problem back to the interviewer to confirm your understanding
• Ask about input constraints: can values be negative? Can the array be empty? Are there duplicates?
• State your intended approach and complexity before writing code

While coding
• Name variables clearly — seen, left, right, complement beat a, b, x
• Add a one-line comment before each logical block, not each line
• Handle the empty / null case first — write the guard clause at the top

After coding
• Trace through your own example manually — catch off-by-one errors
• State the complexity unprompted: 'This is O(n) time and O(1) space because...'
• Offer a variation: 'If the array could be unsorted, I would instead...'

Common mistakes to avoid

• Forgetting to handle empty array / empty string / None head
• Using fit_transform on test data (data leakage)
• Using list instead of deque for queue (O(n) pop from front vs O(1))
• Sorting when the problem has an O(n) hash map solution
• Returning inside a loop before checking all elements

Build the intuition. The pattern is always more important than the code.