📊 DSA Concepts

Learning Objectives

• Build solid intuition for common data structures and algorithmic patterns used in interviews and production.
• Learn to reason about time and space complexity and pick appropriate data structures.
• Gain pattern fluency: two pointers, sliding window, prefix sums, binary search, recursion, DP, greedy.
• Practice problem-solving with worked examples and progressively harder exercises.

Prerequisites

• Comfortable with a programming language (JavaScript/TypeScript recommended)
• Basic math: algebra, modular arithmetic, simple combinatorics

Difficulty Level

• Beginner → Advanced (topic-dependent)

Estimated Reading Time

Overview: 60–90 minutes; topic deep-dives: 30–120 minutes each.

Mental Model

Think in terms of abstractions: arrays provide indexed access, linked lists provide cheap insertion, trees represent hierarchies, graphs represent relationships. Algorithms manipulate these structures; the right combination makes problems tractable.

How to Use this Section

• Follow the recommended learning path from Foundations → Core Techniques → Advanced Problem Solving.
• For interview prep, practice problems by category and then mixed practice under timed conditions.
• For production, focus on algorithmic trade-offs, memory/performance, and robust edge-case handling.

Study Workflow

1. Read the concept page and understand the complexity table.
2. Type out and run the canonical implementation (learn by doing).
3. Solve 10 problems of increasing difficulty for each pattern.
4. Review and refactor solutions to improve clarity and performance.

One-line summary: A structured, topic-wise roadmap through Data Structures & Algorithms — from first principles to advanced problem solving — with visuals, complexity tables, and curated practice.

Big-O cheat sheet — understand time & space trade-offs across every approach

---

🎯 What Are Data Structures & Algorithms?

• Data Structures are ways to organize and store data so it can be accessed and modified efficiently (arrays, linked lists, stacks, queues, trees, graphs, heaps, hash tables).
• Algorithms are step-by-step procedures that operate on that data to solve a problem (searching, sorting, traversal, optimization).

The right data structure paired with the right algorithm is the difference between a program that runs in milliseconds and one that runs in hours. Mastering DSA sharpens your problem-solving, prepares you for coding interviews, and makes you a stronger engineer for real-world systems.

💡 Complexity first: Every topic below includes a Big-O time/space table. Learn to reason about complexity before optimizing.

---

🗺️ Recommended Learning Path

flowchart TD
    A["🏫 Foundations<br/>School Basics · Math"] --> B["🔤 Core Data<br/>Strings · Sorting · Hashing"]
    B --> C["🔧 Core Techniques<br/>Two Pointers · Sliding Window<br/>Prefix Sum · Binary Search · Recursion"]
    C --> D["🧱 Linear Structures<br/>Stack · Queue · Linked List · Heap"]
    D --> E["🌳 Hierarchical & Graphs<br/>Trees · Graphs · Matrix"]
    E --> F["🚀 Advanced Problem Solving<br/>Backtracking · DP · Greedy · Bit Manipulation"]
    F --> G["🏗️ System Design<br/>Scalable systems & fundamentals"]

    style A fill:#e3f2fd,stroke:#1976d2
    style B fill:#e8f5e9,stroke:#388e3c
    style C fill:#fff3e0,stroke:#f57c00
    style D fill:#f3e5f5,stroke:#7b1fa2
    style E fill:#fce4ec,stroke:#c2185b
    style F fill:#ede7f6,stroke:#512da8
    style G fill:#e0f2f1,stroke:#00796b

How to progress:

1. Foundations — build fluency with basic programming and math for algorithmic thinking.
2. Core Data — learn how strings, sorting, and hashing power almost every problem.
3. Core Techniques — the reusable patterns interviewers love (two pointers, sliding window, binary search).
4. Linear Structures — model order and access patterns with stacks, queues, lists, and heaps.
5. Hierarchical & Graphs — traverse and reason over trees and graphs.
6. Advanced Problem Solving — combine everything with backtracking, DP, greedy, and bit tricks.
7. System Design — scale your knowledge to real, distributed systems.

---

📚 Topic Directory

All topics are grouped by category and cross-linked. Each page includes explanations, complexity tables, patterns, worked examples, and practice problems.

🏫 Foundations

Topic	What You'll Learn	Typical Complexity
🏫 School Basics	Core programming constructs & basic algorithms	Varies
🔢 Math	GCD, primes, modular arithmetic, combinatorics	O(√n) – O(n)

🔤 Arrays, Strings & Sorting

Topic	What You'll Learn	Typical Complexity
🔤 Strings	Pattern matching, two pointers, hashing, KMP	O(n) – O(n+m)
🔃 Sorting	Comparison & non-comparison sorts, stability	O(n log n)
🗺️ Hashing	Hash maps/sets for O(1) lookups	O(1) avg

🔧 Core Techniques

Topic	What You'll Learn	Typical Complexity
🎯 Two Pointers	Converging/parallel pointers on arrays	O(n)
🪟 Sliding Window	Fixed/variable windows for subarrays	O(n)
➕ Prefix Sum	O(1) range queries after preprocessing	O(1) query
🔍 Binary Search	Search sorted spaces & "binary search on answer"	O(log n)
🔁 Recursion	Divide & conquer, call stacks, memoization	Varies
📉 Kadane's Algorithm	Maximum subarray sum	O(n)

🧱 Linear Data Structures

Topic	What You'll Learn	Typical Complexity
🥞 Stack	LIFO, expression parsing, DFS	O(1) push/pop
🚶 Queue	FIFO, BFS, scheduling	O(1) enqueue/dequeue
🔗 Linked List	Pointers, reversal, cycle detection	O(n)
⛰️ Heap	Priority queues, Top-K, heapsort	O(log n)
📏 Monotonic Stack	Next greater/smaller element	O(n)

🌳 Non-Linear Data Structures

Topic	What You'll Learn	Typical Complexity
🔲 Matrix	2D traversal, rotation, spiral	O(m·n)
🌳 Trees	Traversals, BST, LCA, tree DP	O(n)
🕸️ Graphs	BFS, DFS, shortest paths, MST	O(V+E)

🚀 Advanced Problem Solving

Topic	What You'll Learn	Typical Complexity
🔙 Backtracking	Exhaustive search with pruning	O(bᵈ)
🧠 Dynamic Programming	Overlapping subproblems, optimal substructure	O(n) – O(n²)
💡 Greedy	Locally optimal choices, exchange argument	O(n log n)
🔢 Bit Manipulation	XOR tricks, masks, set-bit counting	O(1) – O(n)

---

⚡ Big-O Quick Reference

Complexity	Name	Example
O(1)	Constant	Hash lookup, array index
O(log n)	Logarithmic	Binary search, balanced BST
O(n)	Linear	Single pass, prefix sum build
O(n log n)	Linearithmic	Merge sort, heap sort
O(n²)	Quadratic	Nested loops, bubble sort
O(2ⁿ)	Exponential	Naive recursion (fib), subsets
O(n!)	Factorial	Permutations, brute-force TSP

See the complexity cheat sheet above for a visual comparison.

---

🧭 Where to Begin

Beginner? Start here in order:

1. School Basics
2. Math
3. Strings
4. Sorting & Hashing

Comfortable with basics? Build pattern fluency:

1. Two Pointers
2. Sliding Window
3. Prefix Sum
4. Binary Search & Recursion

Interview prep? Master structures and advanced topics:

1. Stack, Queue, Linked List, Heap
2. Trees & Graphs
3. Dynamic Programming, Greedy, Backtracking, Bit Manipulation

---

🎯 How to Use These Docs

• Read the concept and study the visual/mermaid diagram.
• Memorize the complexity table — interviewers always ask.
• Type out the code templates — don't just read them.
• Solve the practice problems from Easy → Medium → Hard.
• Cross-link topics — most hard problems combine two or more patterns.

Start Learning → · © sparshjaswal