DSA Foundations
Introduction to DSA
Contest clock: n = 10⁵, time limit one second. Your nested scan was correct on the sample, then TLE on the hidden tests. The same failure shows up in product code when a feed, search, or checkout path quietly goes quadratic under load.
and are how you keep that path correct when n grows. The craft is organizing data and transforming it under constraints of time, memory, and edge cases.
Solve journey
Clarify
What is n? Sorted? Duplicates? Mutate in place?
Brute baseline
State the obvious correct idea and its cost.
Name the bottleneck
Repeated scans, missing lookups, or no order?
Pick shape + recipe
Choose a structure and an invariant before coding.
What actually happens
Naive idea: write the first nested loop that matches the problem statement. It works for n = 10³ and feels finished.
Break: at n = 10⁵, O(n²) is about 10¹⁰ operations, past a typical one-second budget. At n = 10⁷, even a careless O(n log n) with a large constant can hurt interactive features.
Better idea: treat every problem as a pair of shape and recipe. Pick a that makes the hot operation cheap, then write an whose you can defend. Measure with , and name the you accepted.
What must never become false
For any claimed solution: it terminates on every valid input, the stated complexity bound matches the actual loops and allocations, and the loop or structure still holds after every update. If any of those slip, the answer is not yet ready.
How to choose what to study next
1. Can you state Big-O for a single pass and a nested scan? If not, start with time complexity.
2. Do arrays, stacks, queues, and hash maps feel automatic? They appear inside almost every other topic. Master them before trees and graphs.
3. Stuck on a concrete problem? Walk the pattern catalog after a brute-force baseline, not before.
Quantitative check
Rough interview and contest budget: about 10⁸ simple operations per second. At n = 10⁵, O(n) and O(n log n) usually fit; O(n²) ≈ 10¹⁰ does not. At n = 10⁷, even O(n log n) needs a lean constant, and O(n²) is impossible. Always say what n counts: nodes, edges, string length, or queries.
Data structures
The shape of your data in memory: contiguous blocks, pointer chains, trees, hash buckets, edges. The shape decides which operations are cheap.
- Linear: arrays, linked lists, stacks, queues, deques
- Hierarchical: trees, heaps, tries
- Relational: graphs (adjacency list / matrix)
- Associative: hash maps, sets, bloom filters
Algorithms
The recipe: finite, unambiguous steps that turn input into output while respecting time, memory, and correctness constraints.
- Sorting & searching: order and membership
- Graph: traversal, shortest paths, flows
- DP & greedy: optimization when structure allows
- String / bits: parsing, hashing, bit tricks
Key insight: the same algorithm (DFS) on an adjacency list feels different than on a dense matrix. Structure and procedure are a pair. Linus Torvalds: "Bad programmers worry about the code. Good programmers worry about data structures and their relationships."
Three questions that keep solutions honest
1. Correctness
Does it terminate? Empty input? Duplicates? Negatives? Overflow? State a loop or induction idea in one sentence.
2. Complexity
Time and space in Big-O of n (and sometimes of alphabet size or graph edges). Best / average / worst when they differ (quicksort, hashing). Watch claims.
3. Trade-offs
Time vs space, preprocess vs query, exact vs approximate, mutable vs immutable. Say why you picked this structure over the next-best option.
A repeatable solve loop
- Clarify: input size, sorted?, duplicates?, return indices or values?, mutate in place?
- Brute force: describe the obvious O(n²) or exponential idea so correctness is clear.
- Bottleneck: "The nested scan repeats work" / "we need O(1) lookup" / "feasibility is monotone."
- Optimize: name a pattern (hash map, two pointers, DP, BFS) and its invariant.
- Code + tests: empty, single, all equal, sorted, reverse-sorted, overflow.
Practice this script on a simple algorithm and the pattern catalog.
Complexity cheat sheet (budget targets)
| Big-O | Name | Typical signal | n ≈ 10⁶ budget? |
|---|---|---|---|
| O(1) | Constant | Hash get, array index, stack pop | Yes |
| O(log n) | Logarithmic | Binary search, balanced tree height | Yes |
| O(n) | Linear | Single pass, two pointers, sliding window | Yes |
| O(n log n) | Linearithmic | Sort + scan, heap of size n | Usually yes |
| O(n²) | Quadratic | Nested loops on pairs | Only if n ≲ 5×10³ |
| O(2ⁿ) | Exponential | Subsets / naive recursion | Only tiny n (≲ 20–25) |
Rule of thumb: ~10⁸ simple operations/sec. Always state assumptions. Deep dive: Time complexity intro.
How to choose a structure
| You need… | Reach for… | Watch out for… |
|---|---|---|
| Fast index / contiguous memory | Array / dynamic array | Middle insert is O(n) |
| O(1) average lookup / count | Hash map / set | Worst-case collisions; no order |
| Min / max repeatedly | Heap (priority queue) | No fast arbitrary delete without handle |
| Ordered keys + range queries | Balanced BST / TreeMap | O(log n), not O(1) |
| Relationships / paths | Graph + BFS/DFS | Representation choice (list vs matrix) |
| Undo / matching brackets / DFS stack | Stack | Don't confuse with queue |
| BFS layers / scheduling | Queue / deque | Prefer deque over list for O(1) ends |
Trade-offs (the real theme)
- Time vs space: prefix sums, memo tables, and indexes burn memory to save scans.
- Preprocess vs query: sort once (n log n), answer many binary searches (log n each).
- Exact vs approximate: bloom filters / sketches trade certainty for space.
- Mutable vs persistent: in-place arrays vs copy-on-write trees.
How to use this track
- Skim time complexity so Big-O feels natural.
- Master arrays, lists, stacks, queues, and hash maps. They appear inside almost everything else.
- Learn trees, heaps, and graphs as one family: traversals, ordering, relaxation.
- Study DP vs greedy vs backtracking as three search philosophies.
- Revisit hard problems with the pattern guides (two pointers, sliding window, heaps).
Where this skill shows up
Efficiency
Predict scaling, avoid accidental quadratic loops, pick the right index or stream model.
Problem solving
Decompose unknowns into known primitives: sort, scan, graph search, DP state.
Communication
Clear solutions name trade-offs, invariants, and tests, not only the final code.
Common beginner traps
- Jumping to code before stating constraints and a brute-force baseline.
- Saying "O(n)" without saying what n is (nodes? edges? string length?).
- Using a list as a queue (O(n) pop from front) when a deque is required.
- Ignoring that hash maps do not preserve order unless you use an ordered map.
- Optimizing micro-constants before fixing an O(n²) design.
Did you know?
The word "algorithm" comes from the 9th-century mathematician Al-Khwarizmi, whose systematic procedures influenced algebra and later medieval Latin algorismus.
Exercises
- For n = 10⁵ and n = 10⁷, list which of O(n), O(n log n), and O(n²) you would accept under a ~10⁸ ops/sec budget. What changes if each "operation" is a hash lookup with a large constant?
- Pick one product feature (autocomplete, feed ranking, or inventory lookup). Name the data structure you would reach for first, and one failure mode if n grows 100×.
- State a one-sentence for "running maximum of a non-empty array." What edge case would make that invariant undefined?
Primary sources
- Cormen et al., Introduction to Algorithms (CLRS): Chapters 1–3 (algorithms, growth of functions, divide-and-conquer).
- Knuth, The Art of Computer Programming, Vol. 1: fundamental algorithms and data structure foundations.
- Sedgewick & Wayne, Algorithms: client-oriented introduction pairing structures with analysis.
Takeaway
Data structures store and link information. Algorithms transform it under constraints. A ready solution is correct, has a clear complexity story, and names the trade-off you accepted.