Data Structures & Algorithms course
0 of 44 lessons done
+ 1 advanced lessons in S2 Pro - Big-O notationHow running time grows as input grows
- Space complexityHow much extra memory an algorithm uses
- Recognizing complexity by reading codeLoops, nesting, and halving -- the patterns that give away Big-O at a glance
- Amortized analysisWhy a dynamic array's push is "usually O(1)"
- Checkpoint: Complexity & Big-ORe-test the whole unit
- Two pointersWalk from both ends (or two speeds) instead of nesting loops
- Sliding windowA moving range that grows and shrinks instead of restarting
- Prefix sumsPrecompute running totals to answer range-sum queries in O(1)
- Hashing patternsTrade memory for speed: O(1) lookups turn O(n^2) pair problems into O(n)
- Checkpoint: Arrays, strings & hashing patternsRe-test the whole unit
- StacksLast in, first out -- push, pop, peek
- QueuesFirst in, first out -- enqueue, dequeue
- Linked listsNodes connected by pointers, not laid out contiguously in memory
- Fast & slow pointersCycle detection and finding the middle, in one pass
- Checkpoint: Stacks, queues & linked listsRe-test the whole unit
- RecursionA function that calls itself, with a base case to stop
- BacktrackingTry a choice, recurse, undo it if it doesn't work out
- SubsetsEvery possible selection of elements, via include-or-exclude
- PermutationsEvery possible ordering, via choose-one-remaining-at-a-time
- Checkpoint: Recursion & backtrackingRe-test the whole unit
- Binary trees & traversalsDFS (preorder, inorder, postorder) and BFS (level order)
- Binary search treesThe ordering invariant that makes search O(log n)
- Heaps & priority queuesAlways-accessible min (or max) in O(log n) per update
- Checkpoint: Trees, BSTs & heapsRe-test the whole unit
- Graph representationsAdjacency list vs. adjacency matrix
- BFS on graphsShortest path (by edge count) in an unweighted graph
- DFS on graphsConnected components and cycle detection
- Topological sort & union-findOrdering dependencies, and tracking which nodes are connected
- Checkpoint: GraphsRe-test the whole unit
- Top-down vs. bottom-upMemoization (recursion + cache) and tabulation (iterative table-filling)
- 1D DPHouse Robber: a one-dimensional state, one decision per step
- 2D DPUnique Paths: a grid where each cell depends on the cell above and to the left
- The knapsack patternChoose a subset under a capacity constraint, maximizing value
- Checkpoint: Dynamic programmingRe-test the whole unit
- Greedy algorithmsMake the locally best choice at each step, and never look back
- Bit manipulationAND, OR, XOR and shifts -- operating on a number's binary representation directly
- Monotonic stackA stack that stays sorted, for O(n) 'next greater element'-style problems
- TriesA tree shaped like the words you insert into it, for fast prefix search
- Segment treesO(log n) range queries and range updates, where prefix sums fall short
- Checkpoint: Greedy, bit manipulation & advanced patternsRe-test the whole unit
- Binary search variantsNot just "find the target" -- find the boundary
- Merge sortDivide and conquer: split, sort each half, merge
- QuicksortPick a pivot, partition around it, recurse on both sides
- Checkpoint: Sorting & searching algorithmsRe-test the whole unit
- DSA final examS2 ProThe final exam: ~30 minutes, covering the whole course