Arrays are the most fundamental data structure. Master two-pointer, sliding window, and prefix sum techniques.
Time
Access: O(1), Search: O(n), Insert: O(n), Delete: O(n)
Space
O(n)
Problems
6 must-do
| # | Problem | Difficulty | Asked At |
|---|---|---|---|
| 1 | Two Sum | Easy | Google Amazon Meta |
| 2 | Best Time to Buy and Sell Stock | Easy | Amazon Microsoft Goldman Sachs |
| 3 | Maximum Subarray (Kadane's) | Medium | Google Microsoft Adobe |
| 4 | Merge Intervals | Medium | Google Meta Amazon |
| 5 | Product of Array Except Self | Medium | Amazon Microsoft Apple |
| 6 | Trapping Rain Water | Hard | Google Amazon Goldman Sachs |
Arrays have O(1) random access but O(n) insertion/deletion
Sorting the array can simplify many problems from O(nĀ²) to O(n log n)
Two pointers work great on sorted arrays
Sliding window is ideal for subarray problems with a constraint
