Arrays and Strings — System Engineer

Arrays

An array is a contiguous block of memory that stores elements of the same type at fixed-size offsets. This layout gives arrays a superpower: O(1) random access — any element can be read or written by computing base_address + index × element_size.

Key Properties

Contiguous memory: Elements are stored next to each other, enabling CPU cache prefetching.
Fixed or dynamic size: Static arrays have a fixed capacity; dynamic arrays (like JavaScript’s Array, Python’s list, or ArrayList in Java) grow by allocating a new larger block and copying.
Indexing: Zero-based in most modern languages.
Slice/Subarray: O(k) to extract a contiguous range of k elements.

Common Array Patterns

Pattern	Description	Complexity
Two pointers	One pointer starts at the beginning, another at the end (or both at start with different speeds)	O(n)
Sliding window	Maintain a window `[left, right]` that expands and contracts while tracking a condition	O(n)
Prefix sum	Precompute cumulative sums: `prefix[i] = sum(arr[0..i])` for O(1) range sum queries	O(n) build, O(1) query
In-place reversal	Swap elements from both ends moving inward	O(n)
Dutch National Flag	Three-way partitioning with three pointers	O(n)

Prefix Sum

The prefix sum technique transforms an array into a cumulative sum array where prefix[i] is the sum of all elements from index 0 to i. This allows computing sum(arr[l..r]) in O(1) time:

prefix[i] = arr[0] + arr[1] + ... + arr[i]
sum(l, r) = prefix[r] - prefix[l - 1]  // O(1) after O(n) preprocessing

Strings

A string is a sequence of characters. In most modern languages (JavaScript, Python, Java, C#), strings are immutable — once created, they cannot be modified. Any operation that appears to modify a string actually creates a new string.

String Immutability Implications

Concatenation in a loop is O(n²): Each + creates a new copy of the entire string.
Solution: Use a StringBuilder (Java), StringIO (Python), join (Python/JS), or an array of characters.
Character access: O(1) in languages with indexed string access.

Common String Algorithms

Algorithm	Description	Complexity
Palindrome check	Compare characters from both ends	O(n)
Anagram check	Sort both strings and compare, or count character frequencies	O(n log n) or O(n)
Subsequence check	Two-pointer scan through the longer string	O(n + m)
String reversal	Two-pointer swap on character array	O(n)
Run-length encoding	Compress consecutive repeated characters	O(n)

The StringBuilder Pattern

Instead of:

let s = '';
for (let i = 0; i < n; i++) {
  s += arr[i];  // O(n²): new string allocated each iteration
}

Use:

const parts = [];
for (let i = 0; i < n; i++) {
  parts.push(arr[i]);
}
const s = parts.join('');  // O(n): single allocation

When to Use Arrays vs Linked Lists

Operation	Array	Linked List
Random access by index	O(1) ✅	O(n) ❌
Insert at end (amortized)	O(1) ✅	O(n) (O(1) with tail ptr)
Insert at beginning	O(n) ❌	O(1) ✅
Insert in middle	O(n) ❌	O(1) (with ref) ✅
Memory overhead	Low ✅	High (pointers) ❌
Cache locality	Excellent ✅	Poor ❌
Bidirectional traversal	N/A	With doubly linked ✅

Key Takeaways

Arrays are the default choice for sequential data when you need fast reads by position.
Strings are immutable arrays in most languages — never concatenate in a loop.
Two-pointer and sliding window are the most important array interview patterns.
Prefix sums convert O(n) range queries into O(1) lookups.
Linked lists excel where arrays struggle: frequent insertions/deletions at arbitrary positions.