Stage 1 · Code
Interview Preparation
Optimization Techniques
From brute force to optimal: step-by-step improvement strategies.
7 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode
Start with Brute Force
Always start with a correct brute force solution. It establishes baseline, shows you understand problem, and gives something to optimize. Explain: 'Brute force is O(n²), let me think how to improve.'
Step-by-Step Optimization
| Step | Technique | When It Helps |
|---|---|---|
| 1. Precompute | Prefix sums, frequency maps | Repeated range queries, counting |
| 2. Sort | Two pointers, binary search | Unsorted input, pair finding |
| 3. Hash map | O(1) lookup | Complement search, frequency |
| 4. Two pointers | Eliminate inner loop | Sorted array, palindrome |
| 5. Sliding window | Reuse computation | Subarray with constraint |
| 6. Monotonic stack | Next greater/smaller | Histogram, next element |
| 7. DP/Memoization | Avoid recomputation | Overlapping subproblems |
| 8. Greedy | Local optimal → global | Interval scheduling, coin change (canonical) |
| 9. Binary search answer | Monotonic predicate | Min max subarray sum, Kth smallest |
| 10. Bit manipulation | XOR, masks, subsets | Single number, subsets, parity |
Common Optimization Patterns
Look for: repeated work → cache/memoize; nested loops with condition → hash map/binary search; scanning window repeatedly → sliding window; checking all pairs → sort + two pointers; recomputing prefix sums → prefix array; finding next greater → monotonic stack; overlapping subproblems → DP.
| Before | After | Technique |
|---|---|---|
| O(n²) nested loops | O(n) hash map | Two Sum |
| O(n²) all subarrays | O(n) sliding window | Max sum ≤ k |
| O(n log n) sort + binary search | O(n) two pointers | Pair sum sorted |
| O(2ⁿ) recursion | O(n) DP | Fibonacci, climb stairs |
| O(n) space DP | O(1) space | Fibonacci, House Robber |
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.