Arrays & Contiguous Memory
Deep dive into CPU L1/L2 cache prefetching, contiguous pointer offsets, converging two-pointer patterns, fast-slow pointers, and sliding window subarray optimizations.
Contiguous Memory & CPU Cache Locality
An array is a linear collection of elements placed in contiguous memory addresses. Because elements are sequential, the memory address of element at index i is computed instantaneously in O(1) time via base address offset calculation: Address(i) = BaseAddress + (i * ElementSize).
- CPU L1/L2 Cache Prefetching:When accessing an array element, the CPU loads an entire 64-byte Cache Line, making sequential array scans significantly faster than pointer-based linked lists.
- Random Access O(1):Constant time indexing via direct pointer arithmetic.
- Insertion & Deletion O(N):Inserting or deleting at index 0 requires shifting all N-1 subsequent elements by 1 position in memory.
- Opposite Direction Pointers (Converging): Initialize left = 0 and right = len(arr) - 1. Move left forward or right backward based on comparisons (e.g. Two Sum on sorted array, Palindrome verification, Trapping Rain Water).
- Same Direction Pointers (Fast & Slow): Initialize slow = 0 and fast = 0. Fast scans ahead, while slow tracks the boundary of valid processed elements (e.g. Remove Duplicates in-place, Move Zeroes).
- Sliding Window (Expand & Shrink): Expand the right pointer to add elements to window. When a constraint is violated (e.g. sum > k, duplicate character found), advance the left pointer to shrink the window until valid.
An algorithmic paradigm that converts nested O(N^2) subsegment searches into linear O(N) operations by maintaining state within an expanding and shrinking continuous boundary [left, right].
Memory Offset Address Formula
Array Operations Complexity Benchmark
| Operation | Time Complexity | Space Complexity | Cache Friendliness |
|---|---|---|---|
| Access by Index | O(1)Instant | O(1) | Ultra High |
| Append (at end) | O(1) Amortized | O(1) | High |
| Insert (at index 0) | O(N) | O(1) | Moderate |
| Delete (at index 0) | O(N) | O(1) | Moderate |
| Two Pointer Scan | O(N)Optimal | O(1) | Ultra High |
When solving subarray sum problems with negative numbers, simple sliding windows fail because expanding doesn't guarantee a monotonic increase. Use Prefix Sum with a Hash Map instead!
1def length_of_longest_substring(s: str) -> int:2 seen = {}3 left = 04 max_len = 056 for right, char in enumerate(s):7 if char in seen and seen[char] >= left:8 left = seen[char] + 19 seen[char] = right10 max_len = max(max_len, right - left + 1)1112 return max_len1314# Test Cases15s1 = 'abcabcbb'16s2 = 'pwwkew'17print(f'"{s1}" -> Max Length:', length_of_longest_substring(s1))18print(f'"{s2}" -> Max Length:', length_of_longest_substring(s2))
"abcabcbb" -> Max Length: 3 "pwwkew" -> Max Length: 3
Quick Syntax & Reference Sheet
| Concept / Rule | Syntax / Usage |
|---|---|
| Opposite Pointers | left = 0, right = n - 1; while left < right: ...; left++, right-- |
| Fast/Slow Pointers | slow = 0; for fast in range(n): if condition: arr[slow] = arr[fast]; slow += 1 |
| Sliding Window | for right in range(n): window.add(arr[right]); while invalid(): window.remove(arr[left]); left += 1 |
Common Pitfalls & Developer Mistakes
Off-by-one errors with array slicing and bounds
Why it happens: Iterating up to index `len(arr)` instead of `len(arr) - 1` triggers IndexError / Segfault.
# Correct:
while left < right:
mid = (left + right) // 2