Strings & Arrays: Core Patterns

⏱️ ~4-minute bite · solve the sandbox to master

0%lesson

🧒

5-Year-Old Metaphor

— The physical, real-world picture. No jargon.

🧩 Strings are just arrays of characters — and arrays are just indexed buckets. Almost every interview problem is really one of five patterns in disguise.

Pattern 1 — Frequency map (the anagram family)

Count how many times each character (or value) appears. Compare maps. Works for: anagram detection, find duplicates, missing number, majority element.

Mental model: Two bags of letter tiles. Anagram = same tiles, different arrangement. Dump both bags, sort the piles, compare. O(n) not O(n log n) — use a hash map instead of sorting.

Pattern 2 — Two pointers (the palindrome/sorted family)

One pointer from each end, or both from the start at different speeds. Works for: palindrome check, two-sum on sorted array, container with most water, remove duplicates.

Mental model: Two fingers reading a book — one from front, one from back. If the characters they point to match, move both inward. If they don't, you found the mismatch.

Pattern 3 — Prefix sums (the range-query family)

Precompute cumulative sums so any range sum is O(1). Works for: subarray sum equals k, number of subarrays with sum ≤ target, range sum queries.

arr = [3, 1, 4, 1, 5]

prefix = [0, 3, 4, 8, 9, 14]

sum(i..j) = prefix[j+1] - prefix[i] ← O(1)

Pattern 4 — Sorting + scan

Sort first (O(n log n)), then a single linear pass finds duplicates, meeting points, or groups. Anagram grouping: sort each word as a key.

Pattern 5 — In-place modification

Use the array itself as a hash map (index = value trick) for O(1) space. Flip the sign of arr[abs(val)-1] to mark "seen". Works for "find missing", "find duplicate".

🎛️

Interactive Sandbox

— Move something, see it react instantly.

How to use: Type two strings. The frequency map updates live — green bars mean matching counts, red bars mean mismatch.

String A

6 letters

String B

6 letters

✓ ANAGRAM

Character frequency map

■ String A (left)■ String B (right)■ match■ mismatch

🎯

Challenge

Confirm "listen" / "silent" are anagrams, then try "triangle" / "integral".

Solved

✅ Anagram confirmed! Every character appears the same number of times. Frequency map approach: O(n) time, O(1) space (26-letter alphabet). 🎉

🎯

Why Should I Care?

— The exact interview question + the bug it kills.

Exact interview question — is anagram

"Given two strings s and t, return true if t is an anagram of s."

1	function isAnagram(s: string, t: string): boolean {
2	if (s.length !== t.length) return false;
3	const freq = new Array(26).fill(0);
4	for (let i = 0; i < s.length; i++) {
5	freq[s.charCodeAt(i) - 97]++;
6	freq[t.charCodeAt(i) - 97]--;
7	}
8	return freq.every((n) => n === 0);
9	}
10	// One array, two passes merged. O(n) time, O(1) space.

Classic follow-up — valid palindrome

"Given a string, return true if it reads the same forwards and backwards (ignoring non-alphanumeric chars)."

1	function isPalindrome(s: string): boolean {
2	let l = 0, r = s.length - 1;
3	while (l < r) {
4	while (l < r && !isAlNum(s[l])) l++;
5	while (l < r && !isAlNum(s[r])) r--;
6	if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
7	l++; r--;
8	}
9	return true;
10	}
11	function isAlNum(c: string) { return /[a-zA-Z0-9]/.test(c); }
12	// Two pointers from both ends. O(n) time, O(1) space.

Senior variant — subarray sum equals k

1	function subarraySum(nums: number[], k: number): number {
2	const prefixCounts = new Map([[0, 1]]); // sum → count
3	let sum = 0, result = 0;
4	for (const n of nums) {
5	sum += n;
6	result += prefixCounts.get(sum - k) ?? 0; // how many prefixes end here?
7	prefixCounts.set(sum, (prefixCounts.get(sum) ?? 0) + 1);
8	}
9	return result;
10	}
11	// Prefix sum + hashmap: O(n) time, O(n) space.
12	// Key insight: sum(i..j) = prefix[j] - prefix[i-1] = k
13	// → look for prefix[j] - k in the map.

Complexity: choosing the right approach

Problem shape	Reach for	Time
Count chars / detect anagram	Frequency map (array/map)	O(n)
Palindrome / two-sum sorted	Two pointers	O(n)
Range sum, subarray sum = k	Prefix sums + hashmap	O(n)
Group by rearrangement	Sort each word as key	O(n log n)
Find missing / find duplicate	In-place sign flip	O(n) O(1)

🔬

The Deep Dive

— Spec refs, engine internals, the minutiae.

Prefix sums — the most underused pattern

Build a cumulative sum array in O(n), then answer any range-sum query in O(1). The key identity: sum(i, j) = prefix[j+1] - prefix[i]. Store the prefix map as you go — you don't always need the full array.

1	// Range sum query — O(1) after O(n) build
2	class NumArray {
3	private prefix: number[];
4	constructor(nums: number[]) {
5	this.prefix = [0];
6	for (const n of nums) this.prefix.push(this.prefix.at(-1)! + n);
7	}
8	sumRange(left: number, right: number): number {
9	return this.prefix[right + 1] - this.prefix[left];
10	}
11	}
12
13	// Subarray sum = k: combine prefix map + hashmap
14	function subarraySum(nums: number[], k: number): number {
15	const map = new Map([[0, 1]]);
16	let sum = 0, ans = 0;
17	for (const n of nums) {
18	sum += n;
19	ans += map.get(sum - k) ?? 0;
20	map.set(sum, (map.get(sum) ?? 0) + 1);
21	}
22	return ans;
23	}

In-place marking — O(1) space for "find missing/duplicate"

When values are bounded by the array size (common in n-length arrays with values 1–n), you can use the array itself as a hash set. Negate arr[abs(val) - 1] to mark "seen". A positive entry at index i means value i+1 was never seen.

1	// Find all numbers disappeared from [1, n] — O(n) O(1)
2	function findDisappearedNumbers(nums: number[]): number[] {
3	for (const n of nums) {
4	const idx = Math.abs(n) - 1;
5	if (nums[idx] > 0) nums[idx] *= -1; // mark as seen
6	}
7	return nums
8	.map((v, i) => (v > 0 ? i + 1 : 0))
9	.filter(Boolean); // positive → that value was never seen
10	}

⚠️ Mutates the input array. Restore signs afterward if the caller needs it unchanged.

String-specific pitfalls interviewers probe

Unicode vs ASCII: charCodeAt(i) - 97 only works for lowercase ASCII. For Unicode, use a Map.
String immutability in JS: you can't mutate a string in place — convert to array first, then join.const arr = s.split(""); /* mutate */ return arr.join("");
Comparison edge cases: empty string is a palindrome. Two empty strings are anagrams of each other. Clarify before coding.
Sliding window vs prefix sum: if the array has negatives and you need "sum = k" (not ≤ k), sliding window breaks — use prefix sums + hashmap instead.

Group anagrams — a common medium problem

1	function groupAnagrams(strs: string[]): string[][] {
2	const map = new Map<string, string[]>();
3	for (const s of strs) {
4	const key = s.split("").sort().join(""); // sorted chars = canonical key
5	if (!map.has(key)) map.set(key, []);
6	map.get(key)!.push(s);
7	}
8	return [...map.values()];
9	}
10	// "eat","tea","tan","ate","nat","bat"
11	// → [["eat","tea","ate"],["tan","nat"],["bat"]]
12	// Time: O(n · k log k) where k = max word length Space: O(n·k)

The insight: two strings are anagrams iff their sorted characters are equal. Use that as a hashmap key to bucket them in one pass.

Related patterns to know next

Sliding Window — combines frequency map with a moving window. "Minimum window substring" = sliding + freq map.
Two Pointers — sorting first + two pointers solves 3Sum, 4Sum, container with most water.
Binary Search on arrays — when the array is sorted, binary search turns O(n) search into O(log n).
Kadane's Algorithm — maximum subarray sum (dynamic programming, not prefix sum — handles negatives differently).

🎤

Interview Questions

— Real questions from real interviews — with answers.

Build one frequency map (increment for s, decrement for t), then check all entries are zero.

Precompute cumulative sums: sum(i..j) = prefix[j+1] - prefix[i]. One O(n) build, then O(1) per query.

Sliding window relies on monotonicity — shrinking the window must decrease the sum. Negatives break that invariant.

Skip non-alphanumeric from both ends; compare lowercased characters; meet in the middle.

Use the sign of arr[abs(val)-1] as a boolean flag — negate to mark 'seen', positive means never seen.

🎮

Memory Game

— Quick quiz — lock the concept in long-term memory.

1/4

What is the time complexity of Kadane's algorithm for maximum subarray sum?