Intro

// ===== Core structures =====
// Array / List        contiguous, O(1) index, O(n) insert middle
// Linked list         O(1) insert/delete given node, O(n) lookup
// Stack / Queue       LIFO / FIFO; O(1) push/pop/enqueue/dequeue
// Hash map / set      O(1) average lookup/insert; unordered
// Tree (binary)       hierarchical; balanced trees give O(log n) ops
// Heap                priority queue; O(log n) push/pop
// Graph               nodes + edges; BFS/DFS/Dijkstra/A*
// Trie                prefix tree; autocomplete + dictionary
// Bloom filter        approximate membership; tiny space

// ===== Core algorithms =====
// Sorting:    merge / quick / heap (n log n); radix (O(n) on bounded keys)
// Searching:  binary search (sorted), BFS/DFS (graphs)
// Dynamic programming: memoise overlapping subproblems
// Greedy:     local-best choice when it composes to global optimum
// Two pointers / sliding window: O(n) on sorted/streaming arrays
// Recursion:  divide + conquer; mind the stack
// Backtracking: explore + undo; combinatorial search

// ===== Worked tiny example =====
// Two-sum (classic) — O(n) with a hash:
function twoSum(nums, target) {
  const seen = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need), i];
    seen.set(nums[i], i);
  }
  return [];
}

// ===== When DSA matters =====
// - Interviews (system design tests these directly)
// - Hot paths (the wrong structure costs orders of magnitude)
// - Scale decisions (sharding, indexing, caching all build on DSA)
// - Library design (correct abstractions = correct DSA)

// ===== When DSA hurts =====
// - Over-engineering small CRUD apps
// - Rolling your own when the language has a battle-tested impl

// ===== Patterns to internalise =====
// - Pick the structure based on the hot operation
// - Hash for O(1) lookup; sort + sweep for pairwise
// - Sliding window / two pointers on ordered arrays
// - Prefix sums for range queries

// ===== Pitfalls =====
// - 'It is O(n) but with a huge constant' -> measure on real n
// - Hash maps degrade under adversarial inputs
// - Recursive solutions blow the stack at n=1e5
// - 'Premature optimisation' is real; benchmark before tuning

// Algorithms + data structures = how you turn problems into running code.
// Pick the right data structure first — the algorithm often falls out for free.