Say it before they ask
After every approach: time and space in terms of n (and m if needed).
Patterns to memorize
| Structure | Typical |
|-----------|---------|
| Hash map / set | O(1) avg lookup; O(n) space |
| Sort then scan | O(n log n) |
| Two pointers on sorted | O(n) |
| Binary search | O(log n) |
| BFS/DFS graph | O(V+E) |
| Heap of size k | O(n log k) |
| DP over n states | often O(n) or O(n·W) |
Space tradeoffs
Interviewers love “I can trade O(n) space for O(n) time.” Offer the tradeoff even if you pick one.
Trap
Claiming O(1) space while building a recursion stack of depth n — call it O(n) stack.