Complexity & Arrays
A complete, computer-science-grade Data Structures & Algorithms track — from the ground up, in Python, grounded in the agent/RAG code this course builds. This first part gives you the one tool every later chapter depends on: how to reason about the cost of code — Big-O time and space — and the structure everything is built on, the array (Python's list).
Learning objectives
- Read and write Big-O, and know how Θ and Ω differ from it.
- Count operations in a loop and derive the complexity class.
- Reason about space as well as time.
- Understand how Python's
listis a dynamic array — and whyappendis O(1) amortized butinsert(0, x)is O(n). - Apply the two-pointer, sliding-window, and prefix-sum patterns — the array techniques that turn O(n²) into O(n).
Why a DSA track in an AI course? motivation
Because agents are made of data structures. RAG retrieval is a heap (top-k) over cosine similarities; the agent loop is a stack/queue of messages; tool dispatch is a hash map; a dependency-aware DevOps plan is a graph with a topological sort; re-ranking is sorting; chunk lookup is binary search. Knowing the structure — and its cost — is the difference between an agent that scales to a million documents and one that times out on a thousand. This track makes those choices deliberate.
| Part | Structures | Where it shows up |
|---|---|---|
| D1 | Arrays, complexity | Embedding vectors, message buffers, the cost of every loop |
| D2 | Stack, queue, deque, linked list | Agent step stack, task queue, sliding chat window |
| D3 | Hash table, set, recursion | Tool dispatch, dedup, memoized retrieval, backtracking |
| D4 | Trees, BST, heaps, tries | Top-k retrieval (heap), routing trees, prefix autocomplete |
| D5 | Graphs | DevOps dependency plans, knowledge graphs, tool call chains |
| D6 | Sorting & searching | Re-ranking results, binary search over sorted scores |
1 · Big-O, Θ and Ω — the language of cost basic
Big-O describes how the number of operations grows as the input size n grows. We drop constants and lower-order terms because we care about the shape of the growth, not the exact count. 3n + 7 and 100n are both O(n) — they scale linearly.
| Class | Name | n=1000 does ~ | Example |
|---|---|---|---|
| O(1) | constant | 1 | list[i], dict[k], len(x) |
| O(log n) | logarithmic | ~10 | binary search, balanced-tree lookup |
| O(n) | linear | 1000 | a single loop, x in list |
| O(n log n) | linearithmic | ~10000 | good sorts (Timsort, merge, heap) |
| O(n²) | quadratic | 1000000 | nested loops, bubble sort |
| O(2ⁿ) | exponential | astronomically large | naive recursive subsets, brute-force |
2 · Counting operations — deriving the class basic → intermediate
You don't guess complexity — you count. Two rules cover most code: sequential steps add (and you keep the biggest), and nested loops multiply.
This picture is the whole idea of Big-O in one image: how much work grows as the input n grows. The left side is one loop; the right side is a loop inside a loop.
- The left row of blue boxes is a single loop touching each of the
nitems once — a straight line of work, labelledn steps. That is O(n): double the input, double the work. - The right grid of amber cells is a loop nested inside another loop. For each of the
nouter steps you doninner steps, so you touch every pair — the wholen × nsquare. That is O(n²). - Read the size of the shaded area as the cost: a thin row (n) versus a full grid (n²). The caption's rule — nesting multiplies — is why one extra loop is so expensive.
In short: One loop = a line of work (O(n)); a loop-in-a-loop = a filled square (O(n²)). At n=1000 that's 1,000 vs 1,000,000 operations — the gap only widens as n grows.
python# O(n): one loop over n items
def total(nums):
s = 0 # O(1)
for x in nums: # runs n times ...
s += x # ... each O(1) -> n * O(1) = O(n)
return s # O(1) total: O(n)
# O(n^2): a loop inside a loop
def has_duplicate(nums):
for i in range(len(nums)): # n times
for j in range(i+1, len(nums)): # ~n times -> n*n = O(n^2)
if nums[i] == nums[j]:
return True
return False
# O(n): same job, using a set (we'll build sets from scratch in D3)
def has_duplicate_fast(nums):
seen = set()
for x in nums: # n times
if x in seen: # set membership is O(1) avg
return True
seen.add(x)
return False
These three functions show how you count operations to find the complexity class, and how picking a better data structure changes it. All three solve small, real problems; read the # comments on the right — they tally the cost line by line.
total(nums)is O(n). Oneforloop runs once per item (ntimes), and each pass does a constant-cost add (s += x).npasses × O(1) each = O(n). The setup and thereturnare one-time O(1) steps you drop.has_duplicate(nums)is O(n²). The outer loop runsntimes; for eachithe inner loop compares against every later item. That's every pair — aboutn × ncomparisons — the nested-loop grid from the diagram above.has_duplicate_fast(nums)is O(n). Same job, but it remembers what it hasseenin aset. Checkingif x in seenon a set is O(1) on average (you'll build sets from scratch in D3), so one pass overnitems stays linear.
What the output means: total returns the sum; both duplicate-checkers return True/False. The point isn't the answer — it's that the fast version does the same job with far fewer operations (~n instead of ~n²).
Try this: On a list of 10,000 items the nested version does ~50 million comparisons and the set version ~10,000 — the same answer, ~5000× less work. Swapping a list scan for a set is the single most common speed-up in this whole track.
The two duplicate-finders return the same answer, but on 10,000 items the first does ~50 million comparisons and the second does ~10,000. Same output, different data structure, 5000× fewer operations. That is the entire point of this track.
3 · Space complexity intermediate
Time isn't the only cost — memory matters too, especially for agents holding long conversations or large embedding matrices. Space complexity counts the extra memory an algorithm allocates as a function of n.
This diagram is about memory instead of time: how much extra space an algorithm needs as the input n grows. Same Big-O idea, different resource.
- The left green box is
max_val: it keeps just a couple of variables no matter how big the list is, so its extra memory is O(1) — flat, constant, 'same memory for any n'. - The right row of amber boxes is
doubled: it builds a brand-new list the same length as the input, so its extra memory grows one-for-one withn— O(n). - The small print 'a generator would be O(1)' is the escape hatch: a generator hands back items one at a time instead of storing them all, keeping extra space constant.
In short: A fixed handful of variables = O(1) space; a new collection as big as the input = O(n) space. For agents holding long chats or big embedding matrices, that difference decides whether it fits in memory.
python# O(1) extra space: reuses a few variables regardless of input size
def max_val(nums):
best = nums[0]
for x in nums:
if x > best: best = x
return best # space: O(1)
# O(n) extra space: builds a new list as big as the input
def doubled(nums):
return [x*2 for x in nums] # space: O(n)
# The generator version is O(1) space — it yields, storing nothing (see P6)
def doubled_lazy(nums):
for x in nums:
yield x*2 # space: O(1) — one item at a time
These three functions do almost the same thing (look at the numbers), but they cost different amounts of memory. The comments call out the space complexity of each.
max_val— O(1) space. It scans the list keeping a single runningbestvalue. No matter how longnumsis, it holds just that one extra variable, so its extra memory is constant.doubled— O(n) space. The list comprehension[x*2 for x in nums]creates a whole new list the same size as the input. If the input has a million items, so does the output — extra memory grows withn.doubled_lazy— O(1) space. Usingyieldmakes a generator: it produces one doubled value each time it's asked and stores nothing in between (you'll meet generators again in P6). Same results, but memory stays flat.
What the output means: max_val returns the biggest number; doubled returns a new list; doubled_lazy returns a generator you loop over. The lesson is the memory each one uses, not the values.
Try this: Run list(doubled_lazy([1,2,3])) — you get [2,4,6], same as doubled, but the generator never held all three at once. That's how you stream a huge file without loading it into RAM.
4 · Arrays and Python's list basic → intermediate
An array is a block of contiguous memory holding equal-sized slots. Because the slots are contiguous and equal-sized, the address of element i is just base + i × slotsize — one arithmetic step. That's why indexing is O(1). Python's list is a dynamic array: an array that grows itself when full.
i's address is pure arithmetic — no scanning.
This shows why reading lst[i] is instant — the O(1) that makes arrays the foundation of everything else.
- The row of boxes is the array in memory: the slots sit side by side ('contiguous') and are all the same size. The values
10, 20, 30…are what's stored; thei=0, 1, 2…below are the positions (indices). - The bottom labels
baseandbase+2·ware memory addresses:baseis where the array starts, andwis the width of one slot. - The blue formula
lst[2] → base + 2×wis the key: to find any element the computer does one multiplication and one addition — it never walks through the earlier items. That single arithmetic step is what O(1) means here.
In short: Because every slot is the same size, the address of item i is pure arithmetic — no scanning. That's why lst[i] costs the same whether the list has 10 items or 10 million.
| Operation | Complexity | Why |
|---|---|---|
lst[i] | O(1) | direct address arithmetic |
lst[i] = x | O(1) | write to a known slot |
lst.append(x) | O(1) amortized | usually a free slot; occasionally regrow (§5) |
lst.pop() (end) | O(1) | shrink from the tail |
lst.pop(0) / insert(0,x) | O(n) | every later element must shift |
x in lst | O(n) | linear scan — no index |
lst[a:b] (slice) | O(b-a) | copies the sub-range |
len(lst) | O(1) | the length is stored, not counted |
lst.pop(0) and lst.insert(0, x) are O(n) because every remaining element slides down one slot. Doing that in a loop is a hidden O(n²). If you need fast operations at both ends, use a collections.deque — that's exactly what D2 covers.5 · Why append is O(1) "amortized" intermediate → advanced
A dynamic array can't grow one slot at a time — that would copy everything on every append, giving O(n²) to build a list. Instead it over-allocates: when full, it grabs a bigger block (CPython grows by roughly 1.125×, doubling for small sizes) and copies once. Most appends hit a free slot (O(1)); the occasional resize is O(n), but it happens rarely enough that the average over many appends is O(1). That averaging-over-a-sequence is called amortized analysis.
This explains the word 'amortized': why append is called O(1) even though it occasionally has to do expensive work. Read it top-to-bottom as the list grows.
- Each row is the list's capacity (how many slots it has reserved) at a moment in time: first
cap 2, thencap 4, thencap 8. Capacity is usually bigger than the number of items actually stored. - When the slots fill up, Python doesn't add one slot — it allocates a bigger block (roughly double) and copies the old items over once. Those copy steps are the O(n) moments noted on the right ('copy 2 items', 'copy 4 items').
- The extra blue free slots in the
cap 8row mean the next few appends just drop into a waiting slot — each of those is O(1). - The green bottom line is the punchline: a few rare O(n) copies spread over many cheap O(1) appends average out to O(1) amortized per append.
In short: 'Amortized O(1)' = averaged over many appends, each one is effectively constant, because the expensive resize happens rarely and the doubling means the total copy-work is only about n across the whole build.
pythonimport sys
lst = []
prev = -1
for i in range(17):
cap = sys.getsizeof(lst) # bytes the list object occupies
if cap != prev:
print(f"len={len(lst):2d} bytes={cap} <-- grew")
prev = cap
lst.append(i)
# You'll see the byte-size jump only at a few sizes (0, 4, 8, 16, ...),
# not on every append — that's the over-allocation making append O(1) amortized.
This tiny program lets you see the over-allocation happen. It appends items one at a time and prints the list's size in bytes only when that size actually changes.
sys.getsizeof(lst)asks Python how many bytes the list object is currently using. As you append, that number jumps up in steps, not smoothly.- The
if cap != prev:check prints a line only when the byte-size changed — i.e. only when Python grabbed a bigger block.prevremembers the last size so unchanged appends stay silent. - Because Python reserves spare capacity, most of the 17 appends reuse an existing slot and print nothing; only a handful trigger a growth line.
What the output means: A few lines like len=0 … grew, len=4 … grew, len=8 … grew — the size jumps at a few sizes (0, 4, 8, 16…), not on every append. Those gaps are the free slots that make append O(1) amortized.
Try this: Change range(17) to range(100) and watch how the jumps get further and further apart — each resize buys more headroom, so resizes get rarer as the list grows.
n old items, the jar already holds enough tokens to pay for all the copying. Since every append pays a constant 3 tokens, the amortized cost is O(1) — even though individual appends occasionally do O(n) work.6 · Two pointers — O(n²) → O(n) intermediate → advanced
The two-pointer technique walks two indices through an array (from both ends, or at different speeds) so you make one pass instead of nested passes. It's the canonical way to collapse a quadratic brute force into linear time on a sorted array.
python# Brute force: check every pair -> O(n^2)
def two_sum_slow(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return (i, j)
return None
# Two pointers on a SORTED array -> O(n) time, O(1) space
def two_sum_fast(nums, target): # nums must be sorted ascending
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return (lo, hi)
elif s < target:
lo += 1 # need a bigger sum -> move left pointer up
else:
hi -= 1 # need a smaller sum -> move right pointer down
return None
print(two_sum_fast([1, 3, 4, 7, 11], 10)) # (1, 3) -> 3 + 7
The two-pointer technique turns an O(n²) brute force into an O(n) single pass on a sorted array. Both functions find two numbers that add up to target.
two_sum_slowis O(n²). Nested loops try every possible pair (iwith every laterj) until one sums totarget— the quadratic grid again.two_sum_fastis O(n). It puts one pointer at the start (lo) and one at the end (hi) of the sorted array and walks them toward each other.- The
while lo < hiloop compares the current sum to the target. If the sum is too small it movesloup (to a bigger value); if too big it moveshidown (to a smaller value). Because the array is sorted, each move is the only way to fix the sum, so no valid pair is ever skipped. - Each pointer moves at most
ntimes before they meet, so the whole scan is one linear pass — O(n) time and O(1) space.
What the output means: two_sum_fast([1,3,4,7,11], 10) prints (1, 3) — the values at indices 1 and 3 are 3 and 7, and 3+7=10.
Try this: This only works because the array is sorted. Try an unsorted array and you'll get wrong answers — the whole trick relies on 'too small → move left up, too big → move right down'.
This traces the two-pointer scan from the code above, step by step, on the array [1, 3, 4, 7, 11] with target = 10.
- The row of boxes is the sorted array. The blue
lo ▲marker starts under the leftmost value and the red▲ himarker starts under the rightmost. - Each line below is one step. It adds the two pointed-at values and compares to 10:
1+11=12 > 10is too big, sohimoves left (hi--). - Next
1+7=8 < 10is too small, solomoves right (lo++). The pointers keep converging — never crossing without checking. - The green line
3+7=10 ✓is the hit: the pointers landed on a pair that sums to the target, giving indices(1, 3).
In short: Follow the arrows: each comparison forces exactly one pointer to move inward, so the two pointers together take at most n steps — one O(n) pass instead of the O(n²) double loop.
Why it's correct: at each step, if the sum is too small the only way to increase it is to raise the low value; if too big, lower the high value. No pair is ever wrongly skipped, and each pointer moves at most n times — so the whole scan is O(n).
7 · Sliding window advanced
When a problem asks about every contiguous subarray of some size (or every subarray meeting a condition), recomputing each window from scratch is O(n·k). A sliding window keeps a running total and only adjusts for the element entering and the one leaving — O(n) total.
This shows the sliding window idea: instead of re-adding a group of items every time, you slide a fixed-size box across the array and only adjust for what enters and leaves.
- The row of boxes is the array
[2, 1, 5, 1, 3, 2]. The blue outlined rectangle is the window — here it covers the firstk = 3items, whosesum = 8. - To move the window one step right you don't re-add all three items. You add the new item entering on the right and subtract the item that just left on the left — shown as
+nums[i] − nums[i−k]. - That adjustment is two arithmetic operations — O(1) per slide — no matter how big
kis. Sliding across the whole array is therefore O(n), versus O(n·k) if you rebuilt each window from scratch.
In short: The window slides, it doesn't rebuild: one add + one subtract per step. Recomputing each window fresh would redo work you already did — the running total avoids that.
pythondef max_window_sum(nums, k):
if k > len(nums):
raise ValueError("window bigger than array")
window = sum(nums[:k]) # first window: O(k) once
best = window
for i in range(k, len(nums)): # slide across the rest: O(n)
window += nums[i] - nums[i-k] # add new item, drop the one leaving
best = max(best, window)
return best
print(max_window_sum([2, 1, 5, 1, 3, 2], 3)) # 9 (5+1+3)
max_window_sum finds the largest sum of any k consecutive items using the sliding-window trick from the diagram — one pass, not one pass per window.
- The guard
if k > len(nums)raises a clear error if you ask for a window bigger than the array — a small habit that prevents confusing bugs later. window = sum(nums[:k])computes the first window's total once — this costs O(k) but happens only a single time.beststarts as that sum.- The loop
for i in range(k, len(nums))slides one step at a time.window += nums[i] - nums[i-k]adds the item entering on the right and subtracts the one leaving on the left — the O(1) update. best = max(best, window)keeps the biggest window sum seen so far. After the single pass,bestis the answer.
What the output means: max_window_sum([2,1,5,1,3,2], 3) prints 9 — the best 3-in-a-row is 5+1+3.
Try this: Trace it: first window 2+1+5=8; slide → 8 + 1 − 2 = 7; slide → 7 + 3 − 1 = 9; slide → 9 + 2 − 5 = 6. The max seen is 9 — and each slide was just one add and one subtract.
8 · Prefix sums — precompute once, answer in O(1) advanced
If you'll be asked "what's the sum of elements between i and j?" many times, computing each answer is O(n) per query. A prefix-sum array precomputes cumulative totals once (O(n)), then answers any range in O(1). Classic trade of memory for time.
prefix[k] holds the sum of the first k elements, so any range is a single subtraction — O(1) instead of re-summing.
This shows the prefix-sum trick: do a little work once so that every 'sum between i and j' question afterwards is answered instantly.
- The top row (
nums) is the original data[3, 1, 4, 1, 5, 9]. The bottom row (prefix) holds running totals: each cell is the sum of everything before it, starting from0. - So
prefixreads0, 3, 4, 8, 9, 14, 23— e.g. the8is3+1+4and the14is3+1+4+1+5. Building this whole row is one O(n) pass, done once. - The blue formula answers a range query with one subtraction: the sum of a slice is
prefix[end] − prefix[start]. Hereprefix[4] − prefix[1] = 14 − 3 = 11, the sum of the middle chunk. - The two green cells are the two prefix values being subtracted — that's all the work per query, so each answer is O(1).
In short: Precompute the running totals once (O(n)), then any range sum is a single subtraction (O(1)). You trade a bit of memory for the prefix array to make thousands of queries almost free.
pythondef build_prefix(nums):
prefix = [0] * (len(nums) + 1) # prefix[0] = 0
for i, x in enumerate(nums):
prefix[i+1] = prefix[i] + x # running total
return prefix
def range_sum(prefix, i, j): # sum of nums[i..j] inclusive
return prefix[j+1] - prefix[i] # O(1) per query
nums = [3, 1, 4, 1, 5, 9]
p = build_prefix(nums)
print(range_sum(p, 1, 3)) # 6 (1+4+1)
print(range_sum(p, 0, 5)) # 23 (whole array)
These two functions implement the prefix-sum diagram: build_prefix does the one-time O(n) precompute, and range_sum answers any range in O(1).
prefix = [0] * (len(nums) + 1)makes the totals array one longer than the input, with a leading0. That extra slot at the front is what makes the subtraction formula clean (no special case for ranges starting at index 0).- The loop
prefix[i+1] = prefix[i] + xfills each cell with the previous total plus the current value — the running total you saw in the diagram.enumerategives both the indexiand valuex. range_sum(prefix, i, j)returnsprefix[j+1] - prefix[i]— one subtraction, O(1), for the sum ofnums[i..j]inclusive.
What the output means: range_sum(p, 1, 3) prints 6 (that's 1+4+1) and range_sum(p, 0, 5) prints 23 (the whole array).
Try this: Call range_sum(p, 2, 2) — it returns 4, the single element at index 2. The +1 offsets and the leading zero are what make even a one-element range work without special-casing.
Exercises advanced
- State the time and space complexity of
sorted(set(nums))and explain each factor. - Rewrite
has_duplicateto instead return the first duplicated value, keeping it O(n). - Given a sorted array and a target, use two pointers to count how many pairs sum to the target (watch out for duplicates).
- Use a sliding window to find the length of the shortest subarray whose sum is ≥ a target (all positive numbers).
- Extend
range_sumto return the average of a range in O(1).
🎯 Interview practice interview
The interview questions this topic gets asked — worked, with code. For the full pattern catalog see D8 · Big Tech DSA patterns.
"Largest sum of a contiguous subarray." The O(n) DP: at each element, extend the running sum or restart.
pythondef max_subarray(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x) # extend or restart
best = max(best, cur)
return best
Kadane's algorithm finds the largest sum of any contiguous subarray in a single O(n) pass. It's a classic interview question (classic) and a first taste of dynamic programming.
- It walks the array once, tracking two numbers:
cur= the best sum ending at the current element, andbest= the best sum seen anywhere so far. Both start at the first element. - For each next value
x,cur = max(x, cur + x)makes the key choice: either extend the current run (cur + x) or restart a fresh run atx. You restart whenever the running sum has gone negative — dragging it along would only hurt. best = max(best, cur)remembers the largestcurever reached. After one pass,bestis the answer.
What the output means: For [-2,1,-3,4,-1,2,1,-5,4] it returns 6 — the subarray [4,-1,2,1]. One O(n) pass, O(1) space.
Try this: Trace the 'extend or restart' choice on [-2, 1, -3, 4]: after the -3, cur is negative, so at 4 the max picks x (restart) over cur+x. Spotting that restart is what interviewers want to see.
Compact non-zeros to the front with a write pointer, then fill the rest with zeros.
pythondef move_zeroes(nums):
w = 0
for x in nums:
if x != 0:
nums[w] = x; w += 1
for i in range(w, len(nums)):
nums[i] = 0
'Move zeroes' (classic) shifts every 0 to the end while keeping the other numbers in order — done in place with a write pointer, so O(n) time and O(1) extra space.
wis a write pointer: the next slot where a non-zero value should go. It starts at0.- The first loop scans every value; whenever it finds a non-zero, it copies it to position
wand advancesw. This packs all the non-zeros to the front in their original order, without allocating a new list. - After that loop,
wmarks where the non-zeros end. The second loop fills every remaining slot fromwonward with0— putting all the zeros at the back.
What the output means: [0,1,0,3,12] becomes [1,3,12,0,0] — non-zeros keep their order, zeros pushed to the end, and the original list is modified directly (no copy returned).
Try this: The two-pointer 'read everything, write only what you keep' pattern (here read = the loop variable, write = w) is a workhorse for in-place array edits — remember it for dedup and filter problems too.
Checkpoint — you can move on when you can… advanced
- Give the Big-O of a loop by counting nested iterations.
- Explain why
appendis O(1) amortized butinsert(0,x)is O(n). - Recognize when two-pointer / sliding-window / prefix-sum turns O(n²) into O(n).
- Reason about space, not just time, and name the memory-vs-time trade-off.
🪜 Practice ladder beginner → industry
Six graded exercises, easy to real-world. Try each before opening its solution.
Context: Before you can compare algorithms you must be able to read their growth from the loop structure alone. Big-O is the vocabulary every interview and design review is conducted in.
Your task: For three snippets — one flat loop over n, one nested loop, one halving loop — state the Big-O of each and confirm it by counting the iterations that actually run.
Requirements:
- Classify the flat loop as
O(n) - Classify the nested loop as
O(n²) - Classify the halving loop as
O(log n) - Back each claim with an iteration count, not just the label
💡 Hint: A loop that multiplies or divides its index each step touches log₂ n values, not n of them.
Show solution
def ops(n):
a = b = c = 0
for _ in range(n): # (a) O(n)
a += 1
for i in range(n): # (b) O(n^2)
for j in range(n):
b += 1
k = n
while k > 1: # (c) O(log n) -- halves each step
k //= 2
c += 1
return a, b, c
print(ops(8)) # (8, 64, 3) -> n, n^2, log2(n)Constant factors and lower-order terms drop: n + n^2 + log n is O(n^2), dominated by the nested loop.
Context: Two-sum is the canonical "trade space for time" lesson: the obvious double loop is quadratic, but a single pass with a lookup table collapses it to linear.
Your task: Given an array and a target, return the indices of two numbers that add to the target — first the brute-force O(n²) version, then an O(n) version using a hash map.
Requirements:
- Brute force checks every pair and is
O(n²) - The improved version is a single pass,
O(n)time - Use a hash map from value → index to find the complement
- Return the two indices (not the values)
- Both versions agree on the same input
💡 Hint: As you scan, ask the map whether target − current has already been seen; store each value's index as you go.
Show solution
def two_sum_slow(nums, target): # O(n^2) time, O(1) space
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
def two_sum(nums, target): # O(n) time, O(n) space
seen = {} # value -> index
for i, x in enumerate(nums):
if target - x in seen:
return [seen[target - x], i]
seen[x] = i
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
print(two_sum_slow([3, 2, 4], 6)) # [1, 2]The hash map trades O(n) space to remove the inner loop — the classic time/space tradeoff.
Context: When the input is already sorted you can often drop the hash map entirely and solve in constant extra space — the two-pointer pattern that shows up all over array interviews.
Your task: Given a sorted array, find a pair that sums to the target in O(n) time and O(1) space — no hash map.
Requirements:
- Use one pointer at each end of the array
- Move the pointers inward based on whether the current sum is too big or too small
O(n)time,O(1)extra space- Return the pair (or a not-found signal) — assert on a known example
💡 Hint: If the current sum is too small advance the left pointer; if too big retreat the right one — the sortedness is what makes that decision correct.
Show solution
def pair_sum_sorted(nums, target): # O(n) time, O(1) space
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return [lo, hi]
if s < target:
lo += 1 # need a bigger sum
else:
hi -= 1 # need a smaller sum
return None
print(pair_sum_sorted([1, 2, 4, 7, 11, 15], 15)) # [3, 4] -> 4+11Sortedness lets each comparison discard one candidate, so we sweep once instead of nesting loops.
Context: The sliding-window technique turns many "longest/shortest substring" problems from quadratic into linear. This is the textbook one (classic).
Your task: Return the length of the longest substring whose characters are all distinct, in O(n).
Requirements:
- Maintain a window of unique characters over a single pass
- Track the last seen position of each character
- Shrink the window's left edge past a repeat instead of restarting
O(n)time- Return the maximum window length seen
💡 Hint: Keep the window's start just to the right of the previous occurrence of the current character; the answer is the largest end−start you ever reach.
Show solution
def length_of_longest(s): # O(n) time, O(min(n,alphabet)) space
last = {} # char -> last index seen
start = best = 0
for i, ch in enumerate(s):
if ch in last and last[ch] >= start:
start = last[ch] + 1 # shrink window past the repeat
last[ch] = i
best = max(best, i - start + 1)
return best
print(length_of_longest("abcabcbb")) # 3 ("abc")
print(length_of_longest("bbbbb")) # 1
print(length_of_longest("pwwkew")) # 3 ("wke")The window [start, i] only ever grows or jumps forward, so each index is processed once — O(n).
Context: When you must answer thousands of range-sum queries on a fixed array, recomputing each sum is wasteful. A one-time prefix-sum precomputation makes every query constant-time.
Your task: Precompute so that any "sum of elements from i to j" query answers in O(1), and show it beats recomputing the sum per query.
Requirements:
- Build a prefix-sum array once in
O(n) - Each range query is answered by a single subtraction,
O(1) - Handle the inclusive/exclusive index convention consistently
- Demonstrate the speed win versus the naive per-query loop
💡 Hint: sum(i..j) is prefix[j+1] − prefix[i]; get the offset convention right and every query is one subtraction.
Show solution
class RangeSum: # build O(n), query O(1)
def __init__(self, nums):
self.pre = [0]
for x in nums:
self.pre.append(self.pre[-1] + x)
def query(self, i, j): # inclusive sum nums[i..j]
return self.pre[j + 1] - self.pre[i]
rs = RangeSum([3, 1, 4, 1, 5, 9, 2, 6])
print(rs.query(2, 5)) # 4+1+5+9 = 19
print(rs.query(0, 7)) # 31Amortized: 1000 queries cost O(n + q) instead of O(n·q). Precompute-once is the pattern behind range queries, image integrals, and Fenwick trees.
Context: Counting subarrays with a given sum in a stream of possibly-negative values is a top-frequency interview problem (classic) that fuses prefix sums with a hash map.
Your task: Given a stream of daily P&L values (which may be negative), count how many contiguous subarrays sum to exactly K, in O(n).
Requirements:
- Use running prefix sums, not nested loops
- Keep a hash map of how many times each prefix sum has occurred
- For each position, look up how many earlier prefixes equal
current − K O(n)time; correct even with negative values- Return the total count of qualifying subarrays
💡 Hint: A subarray sums to K exactly when prefix_now − prefix_earlier == K; the map counts the matching earlier prefixes as you scan.
Show solution
from collections import defaultdict
def subarray_sum(nums, k): # O(n) time, O(n) space
count = 0
running = 0
seen = defaultdict(int)
seen[0] = 1 # empty prefix sums to 0
for x in nums:
running += x
count += seen[running - k] # prefixes that make (running - prefix)=k
seen[running] += 1
return count
print(subarray_sum([1, 1, 1], 2)) # 2
print(subarray_sum([3, 4, -7, 1, 3, 3, 1, -4], 7)) # 4Negatives break the sliding window, so we count prefix sums instead: if running - k was seen before, every earlier occurrence closes a valid subarray. This is the industrial form of the two-sum trick.
Knowledge check check yourself
Why is Python's list.append called O(1) amortized rather than simply O(1)?
Show answer
How does the sliding-window technique reduce an O(n²) scan to O(n)?