# NextPeer DSA Cheat Sheet

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.