Module Review: Arrays & Lists
Key Takeaways
- Static vs Dynamic: Static arrays are fixed size; Dynamic arrays (ArrayList/Slice) resize automatically with amortized O(1) insertion.
- Sliding Window: Use for contiguous subarray problems (e.g., longest substring). Reduces O(N2) to O(N).
- Two Pointers: Use for sorted array pairs (Two Sum II) or reversing (Reverse String). Reduces O(N2) to O(N).
- Prefix Sums: Use for O(1) range sum queries after O(N) preprocessing.
- In-Place: Many array problems (Remove Duplicates, Rotate) require O(1) space solutions.
Flashcards
What is the Time Complexity of resizing a Dynamic Array?
O(N) to copy elements, but amortized O(1) per insertion.
When should you use Sliding Window?
When finding a contiguous subarray that satisfies a condition (e.g., max sum, min length).
When should you use Two Pointers?
When searching for pairs in a sorted array or processing from both ends.
How do you calculate Range Sum(L, R) with Prefix Sums?
P[R] - P[L-1]
Cheat Sheet
| Technique | Problem Type | Time Complexity | Space Complexity |
|---|---|---|---|
| Sliding Window | Longest Substring, Min Window | O(N) | O(1) or O(K) |
| Two Pointers | Two Sum (Sorted), Container Water | O(N) | O(1) |
| Prefix Sums | Range Sum Query | O(1) per query | O(N) for array |
| Cyclic Sort | Missing Number (1 to N) | O(N) | O(1) |
Next Steps
Now that you’ve mastered Arrays, move on to Strings or Linked Lists.
Module Review: Arrays & Lists
[!NOTE] This module explores the core principles of Module Review: Arrays & Lists, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.
1. Practice in the Vault
Looking to solidify your understanding? Head over to the Problem Vault to solve curated problems related to this module with detailed walkthroughs and optimal solutions.