Dynamic array
Data structuresHigh interview relevance
- Time
- Index O(1); append O(1) amortized; insert or delete in the middle O(n)
- Space
- O(n)
When to use: The default sequence: indexed reads and appends at the end.
Topics
All 34 topics on the site. Search by name or keyword, then narrow by topic, complexity class, interview relevance, or your own progress. Open a topic for the explanation, code, and pitfalls.
34 of 34 topics shown
Hash table (dict and set)
Data structuresHigh interview relevance
- Time
- Lookup, insert, delete O(1) expected; O(n) worst case
- Space
- O(n)
When to use: Membership tests, counting, de-duplication, and mapping keys to values.
Stack
Data structuresHigh interview relevance
- Time
- Push, pop, peek O(1)
- Space
- O(n)
When to use: Undo history, matching brackets, depth-first search, and evaluating expressions.
Queue and deque
Data structuresHigh interview relevance
- Time
- Enqueue and dequeue O(1) with a deque
- Space
- O(n)
When to use: Breadth-first search, scheduling, and sliding-window maximum (with a deque).
Linked list
Data structuresMedium interview relevance
- Time
- Insert or delete at a known node O(1); search O(n)
- Space
- O(n)
When to use: Frequent insertions and removals at positions you already hold, such as an LRU cache paired with a hash map.
Binary heap and priority queue
Data structuresHigh interview relevance
- Time
- Peek O(1); push and pop O(log n); build from n items O(n)
- Space
- O(n)
When to use: Top-k problems, scheduling by priority, Dijkstra's algorithm, and merging sorted lists.
Binary search tree
Data structuresHigh interview relevance
- Time
- Search, insert, delete O(h): O(log n) balanced, O(n) worst case
- Space
- O(n)
When to use: Ordered data with inserts and lookups. In practice, prefer a balanced tree or a sorted container.
Balanced search tree (AVL, red-black)
Data structuresMedium interview relevance
- Time
- Search, insert, delete O(log n) worst case
- Space
- O(n)
When to use: You need ordered operations such as range queries, predecessor, and successor, with a worst-case guarantee.
Trie
Data structuresMedium interview relevance
- Time
- Insert and search O(m) for a key of length m
- Space
- O(total characters)
When to use: Prefix lookup, autocomplete, word search, and storing a dictionary of words.
Union-Find (disjoint-set union)
Data structuresHigh interview relevance
- Time
- Amortized O(α(n)) per find or union
- Space
- O(n)
When to use: Connected components, cycle detection in undirected graphs, and Kruskal's algorithm.
Monotonic stack
Data structuresHigh interview relevance
- Time
- O(n) total
- Space
- O(n)
When to use: Next greater or smaller element, daily temperatures, and the largest rectangle in a histogram.
Quicksort
SortingMedium interview relevance
- Time
- Θ(n log n) average; Θ(n²) worst case
- Space
- O(log n) stack when recursing into the smaller part first; O(n) for a naive version
When to use: General in-memory sorting where average speed matters and stability does not.
Mergesort
SortingHigh interview relevance
- Time
- Θ(n log n) in every case
- Space
- O(n)
When to use: You need a stable sort with a guaranteed n log n bound, or you are sorting linked lists or external data.
Heapsort
SortingMedium interview relevance
- Time
- Θ(n log n) for distinct keys
- Space
- O(1) when done in place
When to use: You need a guaranteed n log n bound with O(1) extra space.
Counting sort
SortingMedium interview relevance
- Time
- Θ(n + k) for values in a range of size k
- Space
- O(n + k)
When to use: Integers, or items mapped to integers, in a small known range.
Python's built-in sort (Timsort)
SortingMedium interview relevance
- Time
- O(n log n) worst case; O(n) on already-sorted input
- Space
- O(n)
When to use: Almost always, unless the problem asks you to implement a sorting algorithm.
Binary search
SearchingHigh interview relevance
- Time
- O(log n)
- Space
- O(1) iterative
When to use: Sorted random-access data, or any yes/no condition that flips once, as in search-on-the-answer problems.
Linear search
SearchingMedium interview relevance
- Time
- O(n); O(1) if the target is first
- Space
- O(1)
When to use: Unsorted data, small lists, or a one-off lookup.
Breadth-first search (BFS)
Graphs and treesHigh interview relevance
- Time
- O(V + E)
- Space
- O(V)
When to use: Shortest path in an unweighted graph, level-order traversal, and minimum-steps problems on grids.
Depth-first search (DFS)
Graphs and treesHigh interview relevance
- Time
- O(V + E)
- Space
- O(V)
When to use: Connected components, cycle detection, topological ordering, and backtracking over graphs and trees.
Tree traversals
Graphs and treesHigh interview relevance
- Time
- O(n)
- Space
- O(h) for depth-first orders
When to use: Visiting every node: copying, serializing, evaluating, or validating a binary search tree with inorder traversal.
Dijkstra's algorithm
Graphs and treesHigh interview relevance
- Time
- O((V + E) log V) with a binary heap
- Space
- O(V + E)
When to use: Shortest paths from one source when every edge weight is non-negative.
Bellman–Ford
Graphs and treesMedium interview relevance
- Time
- O(V · E)
- Space
- O(V)
When to use: Negative edge weights, or when you must detect negative cycles.
Kruskal's algorithm
Graphs and treesMedium interview relevance
- Time
- O(E log E)
- Space
- O(V + E)
When to use: A minimum spanning tree from an edge list, especially on sparse graphs.
Prim's algorithm
Graphs and treesMedium interview relevance
- Time
- O(E log V) with a binary heap; O(V²) with an array
- Space
- O(V + E)
When to use: A minimum spanning tree grown from a start vertex. The array version suits dense graphs.
Graph representations
Graphs and treesHigh interview relevance
- Time
- Edge check: matrix O(1), list O(deg(u))
- Space
- List O(V + E); matrix O(V²)
When to use: Use an adjacency list for most problems. Use a matrix when the graph is dense or edge checks dominate.
Two pointers
PatternsHigh interview relevance
- Time
- O(n)
- Space
- O(1)
When to use: Sorted arrays (pair sums), in-place partitioning or de-duplication, and palindrome checks.
Sliding window
PatternsHigh interview relevance
- Time
- O(n)
- Space
- O(1) or O(n)
When to use: Longest or shortest contiguous subarray or substring that satisfies a constraint.
Prefix sums
PatternsHigh interview relevance
- Time
- O(n) to build; O(1) per range sum
- Space
- O(n)
When to use: Many range-sum queries on a fixed array, or counting subarrays with a given sum (with a hash map).
Hash map frequency counting
PatternsHigh interview relevance
- Time
- Expected O(n) total
- Space
- O(n)
When to use: Anagrams, duplicates, majority element, two-sum, and top-k frequent items.
Backtracking and subsets
PatternsHigh interview relevance
- Time
- O(2ⁿ) subsets; O(n · 2ⁿ) including copying each one
- Space
- O(n) recursion, plus stored output
When to use: Enumerating combinations: subsets, combinations, N-Queens, Sudoku. Prune as soon as a partial answer is invalid.
Permutations
PatternsMedium interview relevance
- Time
- O(n · n!) to generate all
- Space
- O(n) recursion, plus stored output
When to use: Listing every ordering of a collection. Only practical for small n, roughly up to 10 or 11.
Dynamic programming
PatternsHigh interview relevance
- Time
- Number of states × transitions per state
- Space
- Depends on memoization or tabulation
When to use: Overlapping subproblems with optimal substructure: counting ways, minimizing cost, knapsack, and edit distance.
Merge intervals
PatternsHigh interview relevance
- Time
- O(n log n)
- Space
- O(n)
When to use: Overlapping meetings, ranges, and calendar problems.