DSA Cheat Sheet

Common structures, complexity assumptions and a problem-solving checklist.

Complexities below describe common implementations. State assumptions and check the actual library or implementation.

Structures

• Array: indexing O(1); linear search O(n); insertion in the middle typically O(n).
• Dynamic array: append amortised O(1), with occasional resizing.
• Hash map: lookup and insertion average O(1); worst cases depend on implementation and collisions.
• Stack / queue: typical push/pop or enqueue/dequeue O(1) with suitable implementations.
• Balanced search tree: search, insert and delete O(log n).
• Binary heap: peek O(1); insertion and removing the root O(log n).
• Graph adjacency list: storage O(V + E).

Algorithms

• Binary search: O(log n) on sorted searchable data.
• Merge sort: O(n log n) time and typical O(n) extra storage.
• Quick sort: average O(n log n), worst O(n squared); details depend on pivot choice.
• BFS / DFS: O(V + E) with adjacency lists.

Patterns

• Two pointers: ordered arrays, pairs, in-place transformations.
• Sliding window: contiguous segments with maintainable state.
• Hashing: membership checks, counts, grouping.
• Backtracking: exploring choices and undoing state.
• Dynamic programming: repeated subproblems with a defined state and recurrence.

Solve deliberately

1. Clarify input, output and constraints.
2. Work through a small example.
3. Write a straightforward solution.
4. Identify the bottleneck.
5. Improve and justify the change.
6. Test empty input, boundaries, duplicates and normal cases.
7. Explain correctness, time and space costs.