Choosing the Best Data Structure

1️⃣ What operations do I need to perform efficiently?

Searching? → Use HashMap (O(1)) or Binary Search (O(log n))
Insertion/Deletion? → Use Linked List (O(1)) or Heap (O(log n))
Sorting? → Use Array + Sorting (O(n log n))
Finding min/max frequently? → Use Heap (O(1) for min/max)
Range queries? → Use Segment Tree or Fenwick Tree (O(log n))

2️⃣ How much memory do I have?

Limited memory? → Use In-place sorting (QuickSort, HeapSort)
Need fast lookups but can afford extra space? → Use HashMap
Need efficient traversal? → Use Graph adjacency list instead of matrix

3️⃣ Is the data dynamic or static?

Static (fixed dataset)? → Sorting + Binary Search is often best
Dynamic (frequent updates)? → Use Heap, Linked List, or Balanced BST (e.g., AVL, Red-Black Tree)

4️⃣ Do I need ordering or uniqueness?

Ordering needed? → Use TreeSet (sorted), Priority Queue (heap)
Uniqueness needed? → Use HashSet
Both ordering & uniqueness? → Use Ordered Map (e.g., TreeMap in Java)

How to Approach the Problem

Whenever you're given a problem, ask yourself these four key questions:

What operations do I need to perform efficiently? (Searching, Insertion, Sorting, etc.)
How much memory do I have? (Limited memory vs. extra space for fast lookups)
Is the data dynamic or static? (Fixed dataset vs. frequent updates)
Do I need ordering or uniqueness? (Sorted elements vs. unique values)

Example Scenarios & Best Data Structures

Scenario	Best Data Structure	Why?
Find top K largest elements	MinHeap (Priority Queue)	Efficient O(k log n) retrieval
Check if a number exists in a dataset	HashSet	Fast O(1) lookup
Store key-value pairs with fast lookup	HashMap	O(1) access time
Process elements in sorted order	TreeSet / Priority Queue	Maintains order dynamically
Find shortest path in a graph	Dijkstra’s Algorithm (MinHeap + Graph)	Efficient priority-based traversal
Implement LRU Cache	HashMap + Doubly Linked List	Fast lookups + efficient removals
Find median in a stream of numbers	Two Heaps (MinHeap & MaxHeap)	Efficient median tracking

Final Tip

You don’t need to memorize everything—just practice thinking in terms of operations. If you can explain why a data structure is best for a scenario, you’re already thinking like an SDE2!

C++ STL Data Structures: Set, Heap, Array, Map

1. `set` Usage and Ordering

#include <set>
set<int, greater<int>> numbers; // prints in decreasing order
set<int> nums2; // prints in ascending order

Searching in a Set

int val = 12; // value to search
auto it = numbers.find(val);
if(it != numbers.end()){
    cout << "found" << endl;
} else {
    cout << "not found" << endl;
}

2. When to Use Set, Array, or Heap for Min/Max

Array: Use when you have all values up front and want to sort in ascending or descending order.
Heap (min_heap/max_heap): Use when values come in a stream or you need efficient access to min/max elements, especially if the dataset is very large or k is much smaller than n.
Set: Use when values are unique and you need to check for existence or maintain sorted unique elements.

3. Heap (Priority Queue) Examples

priority_queue<int, vector<int>, greater<int>> minHeap; // min-heap
priority_queue<int> maxHeap; // max-heap

// For pairs:
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minheap; // min-heap with pairs
priority_queue<pair<int, int>> maxheap; // max-heap with pairs

4. `map` vs `unordered_map`

map: Stores nodes in a balanced binary search tree of the keys. Iteration is in ascending key order. Useful for sorted queries.
unordered_map: Uses a hash table. Iteration order is unpredictable. Useful for fast lookups when order doesn't matter.

Map Iteration Example

for(auto it: map_name){
    cout << it.first << " " << it.second << " ";
}