Time Complexity of Common Algorithms
| Algorithm Pattern | Time Complexity | Space Complexity | Key Characteristics |
|---|---|---|---|
| DFS (Depth First Search) | O(V + E) | O(H) where H is height | Explores as far as possible along each branch before backtracking. Good for path finding and tree/graph traversal. Uses stack (recursive or explicit). |
| BFS (Breadth First Search) | O(V + E) | O(W) where W is max width | Explores all nodes at present depth before moving to next level. Good for finding shortest path. Uses queue. |
| Two Pointers | O(n) | O(1) | Used for sorted arrays/strings. Examples: palindrome check, container with most water. |
| Sliding Window | O(n) | O(1) or O(k) | For contiguous sequence/substring problems. Fixed or variable size window. |
| Binary Search | O(log n) | O(1) | Requires sorted array. Divides search interval in half each time. |
| Fast & Slow Pointers | O(n) | O(1) | Cycle detection, middle of linked list, etc. Also called Floyd's Tortoise and Hare. |
| Merge Intervals | O(n log n) | O(n) | Sort first, then linear scan. Good for meeting rooms, schedule conflicts. |
| Topological Sort | O(V + E) | O(V) | For directed acyclic graphs (DAGs). Used in scheduling, build systems. |
| Union Find | O(α(n)) - nearly O(1) | O(n) | Disjoint set operations. Good for connecting components, redundant connections. |
| Backtracking | O(b^d) typically | O(d) | b is branching factor, d is depth. For combinatorial problems like subsets, permutations. |
| Dynamic Programming | Varies | Usually O(n) or O(n²) | Breaks problem into subproblems. Common in optimization problems. |
| Greedy | Usually O(n) or O(n log n) | Usually O(1) | Makes locally optimal choice at each step. Example: activity selection. |
| Kadane's Algorithm | O(n) | O(1) | For maximum subarray problems. Dynamic programming approach. |
| Tree Traversal (In/Pre/Post) | O(n) | O(h) - height | Different ways to visit all nodes. Can be recursive or iterative. |
| Heap/Priority Queue | O(log n) per operation | O(n) | For k-th largest/smallest elements, median finding. |
Additional Important Points:
- V = number of vertices, E = number of edges in graph algorithms
- For graphs, space complexity can be O(V) for adjacency list or O(V²) for adjacency matrix
- Many string/array problems combine multiple patterns
- Space complexity often can be optimized using iterative instead of recursive approaches
Time Complexity of Data Structures
I'll create a comprehensive table showing time complexities for the most commonly used data structures in LeetCode problems, breaking down different operations:
| Data Structure | Access | Search | Insertion | Deletion | Space | Additional Operations |
|---|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) | Sort: O(n log n) |
| Dynamic Array (List) | O(1) | O(n) | O(1) amortized | O(n) | O(n) | Resize: O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | Reverse: O(n) |
| Doubly Linked List | O(n) | O(n) | O(1) | O(1) | O(n) | - |
| Stack | O(n) | O(n) | O(1) | O(1) | O(n) | Top: O(1) |
| Queue | O(n) | O(n) | O(1) | O(1) | O(n) | Front/Back: O(1) |
| Hash Table | N/A | O(1) avg, O(n) worst | O(1) avg | O(1) avg | O(n) | Rehash: O(n) |
| Binary Search Tree | O(log n) avg, O(n) worst | O(log n) avg | O(log n) avg | O(log n) avg | O(n) | Height: O(log n) avg |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Rebalance: O(log n) |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Rebalance: O(log n) |
| Min/Max Heap | O(n) | O(n) | O(log n) | O(log n) | O(n) | Get Min/Max: O(1) |
| Priority Queue | O(n) | O(n) | O(log n) | O(log n) | O(n) | Get Top: O(1) |
| Trie | O(m) | O(m) | O(m) | O(m) | O(ALPHABET_SIZE * m) | m = key length |
| Graph (Adjacency List) | O(V) | O(V) | O(1) | O(V+E) | O(V+E) | - |
| Graph (Adjacency Matrix) | O(1) | O(1) | O(1) | O(1) | O(V²) | - |
| Union Find | O(α(n)) | O(α(n)) | O(α(n)) | N/A | O(n) | α = inverse Ackermann |
| Segment Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Range Query: O(log n) |
| Fenwick Tree (BIT) | O(log n) | O(log n) | O(log n) | O(log n) | O(n) | Range Sum: O(log n) |
Special Data Structure Operations:
HashSet Operations:
- Add: O(1) average
- Remove: O(1) average
- Contains: O(1) average
- Size: O(1)
TreeSet Operations:
- Add: O(log n)
- Remove: O(log n)
- Contains: O(log n)
- Floor/Ceiling: O(log n)
- First/Last: O(1)
HashMap/Dictionary Operations:
- Put: O(1) average
- Get: O(1) average
- Remove: O(1) average
- ContainsKey: O(1) average
TreeMap Operations:
- Put: O(log n)
- Get: O(log n)
- Remove: O(log n)
- FloorKey/CeilingKey: O(log n)
- FirstKey/LastKey: O(1)
Important Notes:
- The complexities mentioned are average case unless specified
- Hash table operations can degrade to O(n) in worst case due to collisions
- BST operations can degrade to O(n) if tree becomes unbalanced
- Many dynamic array operations have amortized time complexity
- Graph complexities: V = vertices, E = edges
- Trie complexities: m = length of string
Please leave a like, if you found this helpful Cheers!
Comments (7)