DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Complete quick-reference cheatsheet covering all data structures with operations and complexities, algorithm complexities, and when-to-use guidelines.
Data Structures: Operations & Complexities
Arrays
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(1) | Direct memory access |
| Search (unsorted) | O(n) | Linear scan |
| Search (sorted) | O(log n) | Binary search |
| Insert at end | O(1) amortized | Dynamic array doubling |
| Insert at position | O(n) | Shift elements right |
| Delete at end | O(1) | Just decrement size |
| Delete at position | O(n) | Shift elements left |
Use when: Random access needed, data size known, cache-friendly iteration.
Linked Lists
| Operation | Singly | Doubly |
|---|---|---|
| Access by index | O(n) | O(n) |
| Insert at head | O(1) | O(1) |
| Insert at tail | O(n) or O(1)* | O(1) |
| Delete at head | O(1) | O(1) |
| Delete given node | O(n) | O(1) |
| Search | O(n) | O(n) |
*O(1) if tail pointer maintained.
Use when: Frequent insertions/deletions, unknown size, no random access needed.
Stacks (LIFO)
| Operation | Time |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek/Top | O(1) |
| Search | O(n) |
Use when: Undo operations, expression parsing, DFS, backtracking, matching brackets.
Queues (FIFO)
| Operation | Time |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Front/Peek | O(1) |
| Search | O(n) |
Use when: BFS, task scheduling, buffering, level-order traversal.
Hash Table / Hash Map
| Operation | Average | Worst |
|---|---|---|
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
| Search | O(1) | O(n) |
| Space | O(n) | O(n) |
Worst case happens with hash collisions (all keys hash to same bucket).
Use when: Fast lookup/insert/delete needed, key-value associations, counting frequencies.
Binary Search Tree (BST)
| Operation | Average | Worst (Degenerate) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Min/Max | O(log n) | O(n) |
| In-order traversal | O(n) | O(n) |
Use when: Ordered data with dynamic insertions, range queries, sorted iteration.
Balanced BST (AVL / Red-Black Tree)
| Operation | Time |
|---|---|
| Search | O(log n) guaranteed |
| Insert | O(log n) guaranteed |
| Delete | O(log n) guaranteed |
| Min/Max | O(log n) |
Use when: Need BST guarantees without degeneration. C++ map/set, Java TreeMap/TreeSet.
Heap (Binary)
| Operation | Time |
|---|---|
| Insert | O(log n) |
| Extract Min/Max | O(log n) |
| Peek Min/Max | O(1) |
| Build Heap | O(n) |
| Delete arbitrary | O(log n) |
Use when: Priority queue, Kth element, merge K sorted, scheduling.
Trie (Prefix Tree)
| Operation | Time |
|---|---|
| Insert word | O(m) where m = word length |
| Search word | O(m) |
| Search prefix | O(m) |
| Space | O(ALPHABET × m × n) worst case |
Use when: Autocomplete, spell check, prefix matching, word games.
Graph Representations
| Representation | Space | Edge Lookup | All Neighbors | Add Edge |
|---|---|---|---|---|
| Adjacency Matrix | O(V²) | O(1) | O(V) | O(1) |
| Adjacency List | O(V + E) | O(degree) | O(degree) | O(1) |
| Edge List | O(E) | O(E) | O(E) | O(1) |
Matrix when: Dense graph, frequent edge existence queries. List when: Sparse graph (most real-world graphs), BFS/DFS traversal.
Algorithm Complexities
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes |
| Radix Sort | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | Yes |
Graph Algorithms
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path (unweighted), level-order |
| DFS | O(V + E) | O(V) | Cycle detection, topological sort, components |
| Dijkstra (binary heap) | O((V+E) log V) | O(V) | Shortest path (non-negative weights) |
| Bellman-Ford | O(V × E) | O(V) | Shortest path (negative weights allowed) |
| Floyd-Warshall | O(V³) | O(V²) | All-pairs shortest path |
| Kruskal's MST | O(E log E) | O(V) | Minimum spanning tree |
| Prim's MST | O((V+E) log V) | O(V) | MST (dense graphs) |
| Topological Sort | O(V + E) | O(V) | Task ordering, dependency resolution |
Searching Algorithms
| Algorithm | Time | Requirement |
|---|---|---|
| Linear Search | O(n) | None |
| Binary Search | O(log n) | Sorted array |
| Ternary Search | O(log n) | Unimodal function |
| Hash Lookup | O(1) average | Hash table built |
| BST Search | O(log n) | Balanced BST |
When to Use What
Need fast lookup? → Hash Map
Need sorted order + fast lookup? → Balanced BST / TreeMap
Need min/max quickly? → Heap
Need LIFO? → Stack
Need FIFO? → Queue
Need prefix matching? → Trie
Need connectivity/path? → Graph + BFS/DFS
Need optimization over subproblems? → Dynamic Programming
Need best local choice → Greedy
Complexity Hierarchy (Slowest to Fastest)
Example
O(n!) > O(2^n) > O(n³) > O(n²) > O(n log n) > O(n) > O(√n) > O(log n) > O(1)
What N allows what complexity:
| N (constraint) | Maximum Viable Complexity | Approximate Operations |
|---|---|---|
| N ≤ 10 | O(n!) | Brute force permutations |
| N ≤ 20 | O(2^n) | Bitmask DP, subset enumeration |
| N ≤ 500 | O(n³) | Floyd-Warshall, triple loops |
| N ≤ 5,000 | O(n²) | Simple DP, nested loops |
| N ≤ 10^6 | O(n log n) | Sorting, binary search solutions |
| N ≤ 10^8 | O(n) | Single pass, linear algorithms |
| N ≤ 10^18 | O(log n) | Binary search, fast exponentiation |
Common Patterns Quick Reference
| Pattern | Template Idea | Problems |
|---|---|---|
| Two Pointers | left/right converge or same-direction | 2Sum sorted, remove duplicates, container water |
| Sliding Window | expand right, shrink left | max sum subarray, longest unique substring |
| Binary Search | lo/hi converge to answer | search rotated, minimum in rotated, peak element |
| BFS Level-Order | queue + level tracking | shortest path, level order traversal |
| DFS + Backtrack | choose → explore → unchoose | permutations, subsets, N-Queens |
| Dynamic Programming | state → transition → base case | knapsack, LIS, edit distance |
| Greedy | locally optimal ⟹ globally optimal | activity selection, Huffman, interval scheduling |
| Union-Find | connected components | number of islands, accounts merge |
| Monotonic Stack | maintain increasing/decreasing stack | next greater element, largest rectangle |
| Prefix Sum | precompute cumulative sums | range sum queries, subarray sum equals K |
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for DSA Cheatsheet: Quick Reference.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, interview, preparation, dsa
Related Data Structures & Algorithms Topics
Continue learning this concept
Interview PreparationEssential DSA Interview Questions25+ categorized DSA interview questions with approach hints covering arrays, strings, linked lists, trees, graphs, and dynamic programming.Interview PreparationFAANG DSA Sheet: Company-Specific Patterns and ProblemsCompany-specific DSA patterns for Amazon, Google, Meta, Apple, and Microsoft with 50+ curated problems organized by difficulty and category.Interview PreparationEssential Coding Patterns for InterviewsMaster the 7 most important coding patterns: sliding window, two pointers, fast & slow pointers, merge intervals, cyclic sort, top-K elements, and modified binary search.Interview PreparationProblem Solving Strategies for Coding InterviewsA structured framework for approaching any coding problem: understand, explore examples, brute force, optimize, code, and test. Plus common mistakes and how to think aloud.ArraysArray Interview Problems and SolutionsSolve classic array problems including rotation, duplicate finding, and subarray challenges.Dynamic ProgrammingDynamic Programming Interview ProblemsMaster essential DP interview problems: coin change, edit distance, rod cutting, climbing stairs, and house robber with clear approaches and solutions.