Module 02: Arrays & Strings — Memory, Core Patterns & Optimization

Goal: Master memory architecture, cache mechanics, dynamic array internals, and the fundamental patterns (Two Pointers, Sliding Window, Prefix Sum, Difference Arrays, Kadane's) for solving LeetCode Medium/Hard problems.
Language: C++ (C++17/C++20)
Prerequisites: Module 01 (Complexity Analysis).

📑 Table of Contents

Under the Hood: Memory Layout & Cache Mechanics
C++ std::vector & std::string Internals
Pattern 1: Two Pointers (Opposite & Fast/Slow)
Pattern 2: Sliding Window (Fixed & Variable Size)
Pattern 3: Prefix Sums & Difference Arrays
Pattern 4: Kadane's Algorithm & Subarray Optimization
Pattern 5: String Algorithms & In-Place Manipulation
6 Practice Problems with Detailed Solutions
Top 10 FAANG Interview Questions

1. Under the Hood: Memory Layout & Cache Mechanics

An array is a collection of elements of the same type stored in contiguous memory locations.

Array in Virtual Memory: int arr[5] at address 0x1000 (sizeof(int) = 4 bytes)
Address:   0x1000    0x1004    0x1008    0x100C    0x1010
Elements: [ arr[0] ][ arr[1] ][ arr[2] ][ arr[3] ][ arr[4] ]
Index:        0         1         2         3         4
Formula:  Address(arr[i]) = BaseAddress + (i * sizeof(DataType))  ==> O(1) Access!

1.1 Why Arrays Beat Linked Lists on Real Hardware: CPU Cache Locality

Modern CPUs do not fetch single bytes from RAM; they fetch Cache Lines (typically 64 bytes) into L1/L2/L3 caches.

RAM (Slow: ~100ns) ──────► L3 Cache (~10ns) ──────► L1 Cache (~1ns) ──────► CPU Register (0.2ns)
                                                          ▲
                                                          │ Loads 64-byte block
                                            [ arr[0] | arr[1] | arr[2] | ... | arr[15] ]

Spatial Locality: Accessing arr[0] loads arr[1] through arr[15] into L1 cache for free.
Temporal Locality: Accessing a recently used variable repeatedly is instantaneous.
Traversing an array is sequentially cache-friendly. In contrast, traversing a linked list causes frequent Cache Misses (stall cycles) due to scattered heap addresses.

2. C++ `std::vector` & `std::string` Internals

2.1 `std::vector` Internal Pointers (Typically 24 bytes on 64-bit OS)

struct vector {
    T* _M_start;          // Points to first element
    T* _M_finish;         // Points to one-past-last element (size = finish - start)
    T* _M_end_of_storage; // Points to end of allocated buffer (capacity = end - start)
};

Memory Buffer on Heap:
┌─────────┬─────────┬─────────┬─────────┬─────────┬─────────┐
│ elem[0] │ elem[1] │ elem[2] │  (free) │  (free) │  (free) │
└─────────┴─────────┴─────────┴─────────┴─────────┴─────────┘
▲                             ▲                   ▲
│                             │                   │
_M_start                      _M_finish           _M_end_of_storage
(size = 3, capacity = 6)

push_back vs emplace_back:
- push_back(const T&): Constructs temporary object, then copies/moves into vector.
- emplace_back(Args&&...): Uses placement new to construct object directly in allocated memory, avoiding temporary object construction.
reserve(n) vs resize(n):
- reserve(n): Allocates memory for $n$ elements (changes capacity), but does not initialize objects (size remains unchanged).
- resize(n): Changes size to $n$, default-constructing new elements if growing.

2.2 Small String Optimization (SSO) in `std::string`

For strings smaller than 15–22 bytes (implementation dependent), std::string stores characters inside the stack object itself rather than allocating dynamic heap memory.

3. Pattern 1: Two Pointers (Opposite & Fast/Slow)

Pattern 1A: Opposite-End Pointers (Sorted Arrays / Palindromes)

Left Pointer ──►                                    ◄── Right Pointer
[  1  ,  3  ,  5  ,  7  ,  11  ,  15  ,  18  ,  21  ]
   ▲                                               ▲
  left                                           right

// Template: Opposite End Two Pointers
int left = 0, right = arr.size() - 1;
while (left < right) {
    int currentSum = arr[left] + arr[right];
    if (currentSum == target) {
        // Found solution or collect result
        left++; right--;
    } else if (currentSum < target) {
        left++; // Increase sum
    } else {
        right--; // Decrease sum
    }
}

Pattern 1B: Fast & Slow Pointers (In-place Array Modification)

Used for removing elements or cycle detection:

// Template: Remove Element in-place
int slow = 0;
for (int fast = 0; fast < arr.size(); ++fast) {
    if (arr[fast] != valToRemove) {
        arr[slow] = arr[fast];
        slow++;
    }
}
// Array size is now 'slow'

4. Pattern 2: Sliding Window (Fixed & Variable Size)

Pattern 2A: Fixed-Size Sliding Window (Size = $K$)

// Template: Fixed Window
int windowSum = 0;
// 1. Build first window
for (int i = 0; i < k; ++i) windowSum += arr[i];
int maxSum = windowSum;

// 2. Slide window
for (int i = k; i < arr.size(); ++i) {
    windowSum += arr[i] - arr[i - k]; // Add incoming, subtract outgoing
    maxSum = std::max(maxSum, windowSum);
}

Pattern 2B: Variable-Size Sliding Window (Dynamic Expansion & Contraction)

Window: [ left . . . . . . right ]
1. Expand 'right' to include elements until condition is met/broken.
2. Shrink 'left' to restore valid state or minimize window size.

// Template: Variable Sliding Window
int left = 0, maxLen = 0;
std::unordered_map<char, int> freq;

for (int right = 0; right < s.size(); ++right) {
    // 1. Add current element to window state
    freq[s[right]]++;
    
    // 2. Shrink window while invalid
    while (/* window is invalid condition */) {
        freq[s[left]]--;
        if (freq[s[left]] == 0) freq.erase(s[left]);
        left++;
    }
    
    // 3. Update answer
    maxLen = std::max(maxLen, right - left + 1);
}

5. Pattern 3: Prefix Sums & Difference Arrays

5.1 1D Prefix Sum

Given array $A$, define $P[i] = \sum_{j=0}^{i-1} A[j]$ with $P[0] = 0$. $$\text{Sum}(L \dots R) = P[R + 1] - P[L] \quad \implies O(1) \text{ Range Query!}$$

Index:    0    1    2    3    4
Arr:    [ 3 ,  1 ,  4 ,  1 ,  5 ]
Prefix: [ 0 ,  3 ,  4 ,  8 ,  9 , 14 ]
Sum(1..3) = Prefix[4] - Prefix[1] = 9 - 3 = 6 (1 + 4 + 1 = 6)

5.2 2D Matrix Prefix Sum

For 2D grid $M[r][c]$: $$P[r+1][c+1] = M[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]$$ Range sum of rectangle $(r_1, c_1)$ to $(r_2, c_2)$: $$\text{Sum} = P[r_2+1][c_2+1] - P[r_1][c_2+1] - P[r_2+1][c_1] + P[r_1][c_1]$$

┌─────────────────┬───────────┐
│      A          │     B     │
│                 │           │
├─────────────────┼───────────┤
│      C          │  TARGET   │
│                 │  RECT (D) │
└─────────────────┴───────────┘
Sum(D) = Total(A+B+C+D) - Top(A+B) - Left(A+C) + Overlap(A)

5.3 Difference Array for $O(1)$ Range Updates

To apply multiple range additions $+V$ to interval $[L, R]$ on an array initialized with zeros:

diff[L] += V
diff[R + 1] -= V
Compute running prefix sum of diff to recover final values in $O(N)$ total time!

6. Pattern 4: Kadane's Algorithm & Subarray Optimization

Find the contiguous subarray with the maximum sum.

Intuition & State Invariant

At index $i$, the maximum sum subarray ending at $i$ is either:

Just the current element $A[i]$ (start a new subarray).
The current element $A[i]$ combined with the maximum sum subarray ending at $i-1$.

$$dp[i] = \max(A[i], dp[i-1] + A[i])$$

int maxSubArray(const std::vector<int>& nums) {
    int currentSum = nums[0];
    int maxSum = nums[0];
    for (size_t i = 1; i < nums.size(); ++i) {
        currentSum = std::max(nums[i], currentSum + nums[i]);
        maxSum = std::max(maxSum, currentSum);
    }
    return maxSum;
}

7. Pattern 5: String Algorithms & In-Place Manipulation

7.1 In-Place Word Reversal

Problem: "the sky is blue" $\to$ "blue is sky the".

Reverse entire string: "eulb si yks eht".
Reverse each individual word: "blue is sky the".
Clean up extra spaces in-place using two pointers.

7.2 Rabin-Karp & Polynomial Rolling Hash

Compute hash of substring $S[i \dots i+k-1]$ in $O(1)$ time: $$H(S[0 \dots k-1]) = \sum_{j=0}^{k-1} S[j] \cdot p^{k-1-j} \pmod M$$ Rolling step: $$H_{\text{next}} = \left((H_{\text{prev}} - S[i] \cdot p^{k-1}) \cdot p + S[i+k]\right) \pmod M$$ Base $p = 31$ or $53$, Modulo $M = 10^9 + 7$.

8. 6 Practice Problems with Detailed Solutions

Problem 1: Trapping Rain Water (LeetCode #42 - Hard)

Problem: Given $n$ non-negative integers representing elevation map where width of each bar is 1, compute how much water it can trap after raining.

       █
   █   ██ █
 █ ██ ██████
[0,1,0,2,1,0,1,3,2,1,2,1] -> Output: 6

#include <vector>
#include <algorithm>

int trap(const std::vector<int>& height) {
    if (height.empty()) return 0;
    
    int left = 0, right = height.size() - 1;
    int leftMax = 0, rightMax = 0;
    int trappedWater = 0;
    
    while (left < right) {
        if (height[left] < height[right]) {
            if (height[left] >= leftMax) {
                leftMax = height[left];
            } else {
                trappedWater += leftMax - height[left];
            }
            left++;
        } else {
            if (height[right] >= rightMax) {
                rightMax = height[right];
            } else {
                trappedWater += rightMax - height[right];
            }
            right--;
        }
    }
    return trappedWater;
}
// Time Complexity: O(N) single pass
// Space Complexity: O(1) auxiliary

Problem 2: Minimum Window Substring (LeetCode #76 - Hard)

Problem: Given two strings $s$ and $t$, return the minimum window substring of $s$ such that every character in $t$ (including duplicates) is included in the window.

#include <string>
#include <vector>
#include <climits>

std::string minWindow(const std::string& s, const std::string& t) {
    std::vector<int> targetFreq(128, 0);
    for (char c : t) targetFreq[c]++;
    
    int requiredChars = 0;
    for (int count : targetFreq) {
        if (count > 0) requiredChars++;
    }
    
    std::vector<int> windowFreq(128, 0);
    int formedChars = 0;
    int left = 0, minLen = INT_MAX, startIndex = 0;
    
    for (int right = 0; right < s.size(); ++right) {
        char c = s[right];
        windowFreq[c]++;
        
        if (targetFreq[c] > 0 && windowFreq[c] == targetFreq[c]) {
            formedChars++;
        }
        
        // Contract window when valid
        while (left <= right && formedChars == requiredChars) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                startIndex = left;
            }
            
            char leftChar = s[left];
            windowFreq[leftChar]--;
            if (targetFreq[leftChar] > 0 && windowFreq[leftChar] < targetFreq[leftChar]) {
                formedChars--;
            }
            left++;
        }
    }
    
    return (minLen == INT_MAX) ? "" : s.substr(startIndex, minLen);
}
// Time Complexity: O(|S| + |T|)
// Space Complexity: O(1) auxiliary (fixed ASCII 128 array)

Problem 3: Subarray Sum Equals K (LeetCode #560 - Medium)

Problem: Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals k.

#include <vector>
#include <unordered_map>

int subarraySum(const std::vector<int>& nums, int k) {
    // Map stores: {prefix_sum, frequency_of_occurrence}
    std::unordered_map<int, int> prefixFreq;
    prefixFreq[0] = 1; // Base case: prefix sum of 0 has occurred once
    
    int currentSum = 0;
    int count = 0;
    
    for (int num : nums) {
        currentSum += num;
        // If (currentSum - k) exists in map, we found subarrays ending at current index
        if (prefixFreq.count(currentSum - k)) {
            count += prefixFreq[currentSum - k];
        }
        prefixFreq[currentSum]++;
    }
    
    return count;
}
// Time Complexity: O(N) average
// Space Complexity: O(N) for hash map

Problem 4: Product of Array Except Self (LeetCode #238 - Medium)

Problem: Return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i], without using division in $O(N)$ time and $O(1)$ extra space.

#include <vector>

std::vector<int> productExceptSelf(const std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> result(n, 1);
    
    // Pass 1: Prefix products
    int prefixProduct = 1;
    for (int i = 0; i < n; ++i) {
        result[i] = prefixProduct;
        prefixProduct *= nums[i];
    }
    
    // Pass 2: Suffix products multiplied directly into result
    int suffixProduct = 1;
    for (int i = n - 1; i >= 0; --i) {
        result[i] *= suffixProduct;
        suffixProduct *= nums[i];
    }
    
    return result;
}
// Time Complexity: O(N)
// Space Complexity: O(1) auxiliary (output array doesn't count towards auxiliary space)

Problem 5: Longest Palindromic Substring (LeetCode #5 - Medium)

Problem: Given a string s, return the longest palindromic substring in s.

#include <string>
#include <algorithm>

std::string longestPalindrome(const std::string& s) {
    if (s.empty()) return "";
    int start = 0, maxLen = 1;
    
    auto expandAroundCenter = [&](int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        // Length is (right - 1) - (left + 1) + 1 = right - left - 1
        int len = right - left - 1;
        if (len > maxLen) {
            maxLen = len;
            start = left + 1;
        }
    };
    
    for (int i = 0; i < s.length(); ++i) {
        expandAroundCenter(i, i);     // Odd length palindromes
        expandAroundCenter(i, i + 1); // Even length palindromes
    }
    
    return s.substr(start, maxLen);
}
// Time Complexity: O(N^2)
// Space Complexity: O(1) auxiliary

Problem 6: Maximum Product Subarray (LeetCode #152 - Medium)

Problem: Given an integer array nums, find a contiguous non-empty subarray that has the largest product.

#include <vector>
#include <algorithm>

int maxProduct(const std::vector<int>& nums) {
    int maxProd = nums[0];
    int minProd = nums[0];
    int result = nums[0];
    
    for (size_t i = 1; i < nums.size(); ++i) {
        int val = nums[i];
        if (val < 0) {
            std::swap(maxProd, minProd); // Negative number flips max and min
        }
        
        maxProd = std::max(val, maxProd * val);
        minProd = std::min(val, minProd * val);
        
        result = std::max(result, maxProd);
    }
    return result;
}
// Time Complexity: O(N)
// Space Complexity: O(1) auxiliary

9. Top 10 FAANG Interview Questions

Q1: Why does `std::vector` multiply its capacity rather than adding a fixed constant (e.g., +100) when full?

Answer: If capacity increases by a constant $C$, inserting $N$ elements requires $\frac{N}{C}$ reallocations. Total copies: $\sum_{i=1}^{N/C} i \cdot C \approx \Theta(N^2)$. Amortized cost per insertion becomes $O(N)$ (quadratic total time). Geometric growth (multiplying by factor $g > 1$) ensures total copies form a geometric series bounded by $O(N)$, giving amortized $O(1)$ insertion.

Q2: How does `std::string_view` (C++17) optimize substring operations?

Answer: std::string::substr creates a new string on the heap/stack and copies characters ($O(K)$ time and memory). std::string_view is a lightweight non-owning reference consisting of just a pointer to char and a length (16 bytes). Substring operations on string_view only adjust pointer and length ($O(1)$ time, zero allocation).

Q3: When should you prefer a Sliding Window over Two Pointers?

Answer:

Two Pointers: Used when the array is sorted, or when two elements at different positions interact (e.g., meeting in the middle for 2-sum, water container).
Sliding Window: Used on contiguous sequences/subarrays/substrings where we maintain a running aggregate state (sum, character frequency, distinct count) over a dynamic or fixed range.

Q4: How do you handle negative numbers in Sliding Window problems?

Answer: Traditional sliding window assumes monotonicity (e.g., expanding right increases the sum, shrinking left decreases it). When negative numbers are present, this invariant is broken. Instead, we use Prefix Sum + Hash Map (as in LeetCode 560) or Monotonic Deque.

Q5: What is iterator invalidation in `std::vector`?

Answer: When vector::push_back or insert triggers reallocation, all existing iterators, pointers, and references to elements are invalidated because memory moved to a new buffer. If no reallocation occurs, iterators after the insertion point are invalidated due to element shifts.

Q6: Explain the difference between `std::vector<bool>` and `std::vector<char>`.

Answer: std::vector<bool> is a space-specialized STL template that packs booleans into individual bits (1 bit per boolean instead of 1 byte). Because CPU architecture cannot address individual bits directly, operator[] returns a proxy object (std::vector<bool>::reference) instead of bool&. This breaks standard container requirements (e.g. taking address of element &vec[0]). If real byte-addressable booleans are needed, use std::vector<uint8_t> or std::vector<char>.

Q7: How does Kadane's algorithm handle arrays with all negative numbers?

Answer: If maxSum is initialized to $0$ and empty subarrays are allowed, it returns $0$. If a non-empty subarray is required, initialize maxSum and currentSum to nums[0]. If all numbers are negative, it correctly returns the maximum negative number (the least negative value).

Q8: What is the Difference Array technique and its advantage over Segment Trees?

Answer: Difference arrays allow $O(1)$ offline range updates $[L, R, +V]$. After all $Q$ queries are accumulated, the final state is reconstructed in a single $O(N)$ prefix sum pass. Total time: $O(N + Q)$. Segment Trees allow online interleaved updates and queries in $O(\log N)$ each, but have higher memory and constant factor overhead ($O(4N)$ space).

Q9: How can 2D Matrix rotation by 90 degrees clockwise be performed in-place?