Arrays & Strings

Arrays and strings share contiguous memory — O(1) indexed access is the core advantage. The dominant mental model is the 'window': one or two pointers maintain invariants as they scan, avoiding O(n²) brute force. Prefix sums convert range queries to O(1). Master two pointers, sliding window, and prefix sums to handle ~70% of array/string interview problems. What Are Arrays? An array is a contiguous block of memory storing elements of the same type. Each element is accessed by its index in O(1) time. Arrays are the most fundamental data structure — almost every interview starts here. Why arrays matter in interviews: They test your ability to manipulate indices and pointers Many problems reduce to array manipulation Understanding memory layout helps with optimization Key patterns: Two pointers (opposite ends, same direction) Sliding window (variable or fixed size) Prefix sums for range queries In-place modification to avoid extra space Complexity cheat sheet: Time O(1) O(n) O(log n) O(1) amortized O(n) Arrays & Strings Fundamentals Arrays are the most fundamental data structure — a contiguous block of memory storing elements of the same type. Most coding interview problems start here. Core Operations & Complexity Array O(1) O(n) O(1) O(n) O(n) Essential Patterns Two Pointers — Use when array is sorted or you need to compare elements: Sliding Window — For subarray/substring optimization: Prefix Sum — For range queries: Key LeetCode Problems #1 Two Sum, #15 3Sum, #53 Maximum Subarray (Kadane's) #238 Product of Array Except Self, #560 Subarray Sum Equals K Interview Tip "For array problems, I first consider: is it sorted? (two pointers) Is it about subarrays? (sliding window or prefix sum) Can I use a hash map for O(1) lookup?" Java Implementation: