Category / Advanced DSA
Data Structures
& Algorithms
DSA is the study of how to organize data (structures) and the step-by-step procedures (algorithms) that operate on it efficiently. Every fast app, search engine, map route, and recommendation feed is DSA applied at scale.
a traversal walking through the topic graph
What is DSA?
DSA stands for Data Structures and Algorithms. A data structure is a way of organizing data (arrays, trees, graphs...). An algorithm is a finite, well-defined sequence of steps that solves a problem or transforms that data. Together, they decide whether a program runs in milliseconds or minutes.
Why it's used
The right structure/algorithm turns an O(n²) brute force into an O(n log n) or O(n) solution — the difference between a feature that scales to millions of users and one that times out. It's also the shared vocabulary engineers use to reason about performance and trade-offs.
Why it's needed
Real systems face limited memory, limited time, and growing input sizes. DSA gives you a toolkit to model a problem correctly, predict how a solution behaves at scale, and pick the cheapest correct approach — it's also the core of most technical interviews.
Types of Data Structures
- Linear: Array, Linked List, Stack, Queue — elements arranged sequentially.
- Non-Linear: Tree, Graph, Heap, Trie — elements arranged hierarchically or as networks.
- Homogeneous vs Heterogeneous: arrays hold one type; structs/objects can hold mixed types.
- Static vs Dynamic: fixed-size arrays vs resizable structures (dynamic arrays, linked structures).
Types of Algorithms
- Brute Force: try every possibility, correct but slow.
- Divide & Conquer: split, solve, combine (merge sort, quick sort).
- Greedy: best local choice at each step.
- Dynamic Programming: cache overlapping subproblem results.
- Backtracking: explore, then undo invalid choices.
- Graph Algorithms: BFS, DFS, shortest path, MST, topological sort.
Every topic, explained
Tap a topic to expand its notes: a plain-language summary, the key facts worth memorizing, a worked code example, and its time/space complexity.
A contiguous block of memory holding elements of the same type, accessed by index. The foundation almost every other data structure is built on top of.
- ▸Random access by index in O(1)
- ▸Insertion/deletion in the middle costs O(n) due to shifting
- ▸Cache-friendly because of memory contiguity
- ▸Common patterns: prefix sums, two pointers, sliding window, Kadane's algorithm
- ▸Dynamic arrays (e.g. ArrayList/Vector) resize by doubling capacity — amortized O(1) push
// Kadane's Algorithm — max subarray sum, O(n)
function maxSubArray(nums) {
let best = nums[0], cur = nums[0];
for (let i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}Pattern recognition toolkit
Most interview and contest problems are a known pattern in disguise. Recognizing the pattern is 80% of the battle.
Two Pointers
Sorted array, pair/triplet sums, palindrome checks
Sliding Window
Contiguous subarray/substring with a constraint
Fast & Slow Pointers
Cycle detection, finding the middle of a linked list
Prefix Sum
Range sum queries, subarray sum equals K
Binary Search on Answer
Minimize/maximize a value over a monotonic search space
Backtracking Template
Generate all subsets, permutations, combinations, board puzzles
Union-Find (DSU)
Dynamic connectivity, cycle detection, Kruskal's MST
Topological Sort
Task scheduling, course prerequisites, build order
Monotonic Stack
Next greater/smaller element, histogram, temperatures
DP: Knapsack Pattern
Choose subset under a capacity constraint
DP: LIS / LCS Pattern
Subsequence comparison and ordering problems
Bitmask DP
Small n (≤ ~20), track subsets as integers
Complexity at a glance
Data structure operations
| Structure | Access | Search | Insert | Delete |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) |
| Stack / Queue | O(n) | O(n) | O(1) | O(1) |
| Hash Map | — | O(1)* | O(1)* | O(1)* |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
| Heap | O(1) top | O(n) | O(log n) | O(log n) |
| Trie | O(L) | O(L) | O(L) | O(L) |
Sorting algorithms
| Algorithm | Best | Worst | Space |
|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(1) |
| Selection Sort | O(n^2) | O(n^2) | O(1) |
| Insertion Sort | O(n) | O(n^2) | O(1) |
| Merge Sort | O(n log n) | O(n log n) | O(n) |
| Quick Sort | O(n log n) | O(n^2) | O(log n) |
| Heap Sort | O(n log n) | O(n log n) | O(1) |
| Counting Sort | O(n+k) | O(n+k) | O(k) |
| Radix Sort | O(nk) | O(nk) | O(n+k) |
Big-O growth, smallest to largest
Problems, grouped by topic
Work through each group in order. Solve Easy first to lock in the pattern, then Medium/Hard to stress-test it.
Arrays & Strings
- Two SumEasy
- Best Time to Buy and Sell StockEasy
- Maximum Subarray (Kadane's)Medium
- Product of Array Except SelfMedium
- Longest Substring Without Repeating CharactersMedium
- Trapping Rain WaterHard
Linked List
- Reverse a Linked ListEasy
- Detect Cycle in a Linked ListEasy
- Merge Two Sorted ListsEasy
- Remove Nth Node From EndMedium
- Merge k Sorted ListsHard
Stack & Queue
- Valid ParenthesesEasy
- Min StackMedium
- Next Greater ElementMedium
- Largest Rectangle in HistogramHard
- Sliding Window MaximumHard
Trees & BST
- Maximum Depth of Binary TreeEasy
- Validate Binary Search TreeMedium
- Lowest Common AncestorMedium
- Binary Tree Level Order TraversalMedium
- Serialize and Deserialize Binary TreeHard
Heap
- Kth Largest Element in an ArrayMedium
- Top K Frequent ElementsMedium
- Find Median from Data StreamHard
- Merge k Sorted ArraysHard
Graphs
- Number of IslandsMedium
- Course Schedule (Topological Sort)Medium
- Clone GraphMedium
- Network Delay Time (Dijkstra)Medium
- Word LadderHard
- Alien DictionaryHard
Dynamic Programming
- Climbing StairsEasy
- House RobberMedium
- Longest Increasing SubsequenceMedium
- Coin ChangeMedium
- Edit DistanceHard
- Regular Expression MatchingHard
Backtracking
- SubsetsMedium
- PermutationsMedium
- Combination SumMedium
- N-QueensHard
- Sudoku SolverHard
Trie
- Implement Trie (Prefix Tree)Medium
- Word Search IIHard
- Design Add and Search Words Data StructureMedium
Advanced Structures
- Range Sum Query — Mutable (Fenwick Tree)Medium
- Count of Smaller Numbers After SelfHard
- Number of Connected Components (Union-Find)Medium
Take the full notes with you
One Markdown file with every topic above, both cheat sheets, all techniques, and the full problem checklist — ready to open in any editor or note-taking app.