Data Structure Index

Complexity CheatSheet

Standard Data Structure

-------------------------------------------------------------------------------------------------
| Standard      | Time Complexity                                           |  Space Complexity |
-------------------------------------------------------------------------------------------------
|               | Average / Worst                                           |  Worst            |
-------------------------------------------------------------------------------------------------
|               | Access       | Search       | Insertion    | Deletion     |                   |
-------------------------------------------------------------------------------------------------
| Array         | O(1)         | O(n)         | O(n)         | O(n)         |  O(n)             |
| Stack         | O(n)         | O(n)         | O(1)         | O(1)         |  O(n)             |
| Queue         | O(n)         | O(n)         | O(1)         | O(1)         |  O(n)             |
| LinkedListS   | O(n)         | O(n)         | O(1)         | O(1)         |  O(n)             |
| LinkedListD   | O(n)         | O(n)         | O(1)         | O(1)         |  O(n)             |
| SkipList      | O(logn)      | O(logn)      | O(logn)      | O(logn)      |  O(nlogn)         |
-------------------------------------------------------------------------------------------------
| HashTable     |              | O(1)/O(n)    | O(1)/O(n)    | O(1)/O(n)    |  O(n)             |
-------------------------------------------------------------------------------------------------
| Binary Tree   | O(n)         | O(n)         | O(n)         | O(n)         |  O(n)             |
| BST           | O(logn)/O(n) | O(logn)/O(n) | O(logn)/O(n) | O(logn)/O(n) |  O(n)             |
| KD Tree       | O(logn)/O(n) | O(logn)/O(n) | O(logn)/O(n) | O(logn)/O(n) |  O(n)             |
| CartesianTree |              | O(logn)/O(n) | O(logn)/O(n) | O(logn)/O(n) |  O(n)             |
-------------------------------------------------------------------------------------------------
| B-Tree        | O(logn)      | O(logn)      | O(logn)      | O(logn)      |  O(n)             |
| RedBlackTree  | O(logn)      | O(logn)      | O(logn)      | O(logn)      |  O(n)             |
| AVL Tree      | O(logn)      | O(logn)      | O(logn)      | O(logn)      |  O(n)             |
| Splay Tree    |              | O(logn)      | O(logn)      | O(logn)      |  O(n)             |
-------------------------------------------------------------------------------------------------

Heap Data Structure

-----------------------------------------------------------------------------------
| Heap      | Time Complexity                                                     |
-----------------------------------------------------------------------------------
|           | Find Max | Extract Max | Increase Key | Insert  | Delete  | Merge   |
-----------------------------------------------------------------------------------
| Binary    | O(1)     | O(logn)     | O(logn)      | O(logn) | O(logn) | O(m+n)  |
| Pairing   | O(1)     | O(logn)     | O(logn)      | O(1)    | O(logn) | O(1)    |
| Binomial  | O(1)     | O(logn)     | O(logn)      | O(1)    | O(logn) | O(logn) |
| Fibonacci | O(1)     | O(logn)     | O(1)         | O(1)    | O(logn) | O(1)    |
-----------------------------------------------------------------------------------

Graph Data Structure and Algorithms

-------------------------------------------------------------------------------------------------
| Graph           | Time Complexity                                                             |
-------------------------------------------------------------------------------------------------
|                 | Storage    | Add Vertex | Add Edge   | Remove Vertex | Remove Edge | Query  |
-------------------------------------------------------------------------------------------------
| AdjacencyList   | O(|V|+|E|) | O(1)       | O(1)       | O(|V|+|E|)    | O(|E|)      | O(|V|) |
| IncidenceList   | O(|V|+|E|) | O(1)       | O(1)       | O(|E|)        | O(|E|)      | O(|E|) |
| AdjacencyMatrix | O(|V|^2)   | O(|V|^2)   | O(1)       | O(|V|^2)      | O(1)        | O(1)   |
| IncidenceMatrix | O(|V||E|)  | O(|V||E|)  | O(|V||E|)  | O(|V||E|)     | O(|V||E|)   | O(|E|) |
-------------------------------------------------------------------------------------------------

------------------------------------------------------------------
| Graph Algs      | Time Complexity           | Space Complexity |
------------------------------------------------------------------
|                 | Average      / Worst      | Worst            |
------------------------------------------------------------------
| DFS             | O(|V|+|E|)                |                  |
| BFS             | O(|V|+|E|)                |                  |
| TopologicalSort | O(|V|+|E|)                | O(|V|+|E|)       |
| Dijkstra's      | O(|E|log|V|) / O(|V|^2)   | O(|V|+|E|)       |
| Kruskal's       | O(|E|log|V|)              |                  |
| Prim's          | O(|E|log|V|) / O(|V|^2)   | O(|V|+|E|)       |
| Bellman-Ford    | O(|E||V|)                 | O(|V|)           |
| Floyd-Warshall  | O(|V|^3)                  | O(|V|^2)         |
| A* Search       | O(|E|)       / O(b^d)     | O(b^d)           |
------------------------------------------------------------------

Data Structure

1. array
2. matrix
3. string
4. hash table
5. linked list
6. stack
7. queue
8. priority queue, heap
9. tree, tree + linked list
10. binary search tree
11. AVL tree, red-black tree
12. trie
13. segment tree
14. graph
15. python built-in

ALgorithms

1. sorting
2. binary search
3. back tracking
4. greedy
5. dynamic programming
6. divide and conquer
7. dfs - graph related or more general
8. bfs - graph related or more general
9. topological sort - graph related
10. union find - graph related

OThers

1. math
2. bit manipulation
3. regex
4. design
5. two pointers
6. minimax
7. memoization
8. brainteaser
9. SQL
10. file
11. object-oriented programming
12. python class

Topics

1. general
2. multi-answers
3. series

Topics 1 includes:

• N Sum [hash, binary search, design]
• Parentheses [hash, stack, backtracking]
• Palindrome [string, backtracking, dp, linked list, hash, trie]
• Contains Dups [hash]
• Combination [backtracking, dp]
• Permutation [list, backtracking, hash]

Topics 2 includes:

• Majority Element [hash, set, Counter, sort, randomization, divide n conquer, Moore Voting, bit manipulation]
• Kth Largest Element [sorting, max heap, quick select, partition]

Topics 3 includes:

• Best Time Buy n Sell [list, minmax, dp]
• House Robber [dp]
• Shortest Word Distance [array, hash]
• Word Break [dp, dfs]
• Word Ladder [bfs, dfs]

Resources

Big O CheatSheet see Eric, bigocheatsheetio
GeekTime Patch see geektime