Arrays & Strings

Arrays and strings are your foundation layer. In interviews and in production systems, most “hard” solutions are built by combining a few linear-data patterns correctly: indexing, two pointers, hashing, and prefix-like accumulation.

If this topic is strong, every later topic becomes easier.

Mental Model: Why Arrays Are Fast

An array is conceptually a contiguous block of memory. If element size is fixed, address lookup is:

base_address + index * element_size

That is why random access is O(1).

const arr = [10, 20, 30, 40]
arr[2] // O(1)

CTO reality check

In JavaScript, arrays are dynamic and engine-optimized structures (not raw C arrays), but the performance model for algorithmic interviews is still array-like:

• indexed read/write: O(1) average
• append: O(1) amortized
• middle insert/delete: O(n) due to shifting

Complexity Table (With Practical Caveats)

Key invariant: arrays are excellent when you mostly read/append; poor when you frequently edit near the front/middle.

Strings in JavaScript: Things Interviewers Expect You to Know

Strings are immutable. You cannot update characters in place.

let s = "hello"
s[0] = "H"
console.log(s) // "hello"

If you need mutation-style operations, build new data:

• use array of chars and join(""), or
• use builder-like accumulation (result += ... with caution for very large loops)

function reverseString(s: string): string {
  return s.split("").reverse().join("")
}

Unicode trap (advanced but useful)

s.length counts UTF-16 code units, not user-perceived characters. Emojis and some symbols may occupy 2 code units.

const x = "🙂"
console.log(x.length) // 2

For interview ASCII problems, ignore this unless prompt says Unicode-aware. For product code (search, text editors), this matters.

Pattern Selection in 30 Seconds

When you read a problem, map it quickly:

1. Need pair lookup on unsorted array? -> HashMap (Two Sum style)
2. Need pair logic on sorted array? -> Two pointers
3. Need contiguous best window/substring? -> Sliding window
4. Need many range sum queries? -> Prefix sum
5. Need in-place cleanup/compaction? -> Read/write pointers

If you cannot categorize in 30 seconds, start with O(n^2) brute force and identify repeated work to eliminate.

Core Pattern 1: In-Place Compaction (Read/Write Pointers)

Used when output must reuse input array.

Example: remove duplicates from sorted array

function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0

  let write = 1
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[read - 1]) {
      nums[write] = nums[read]
      write++
    }
  }
  return write
}

Correctness invariant

Before each iteration:

• nums[0..write-1] contains the deduplicated prefix
• read scans unseen elements

When we find a new unique value, writing at write preserves sorted order and extends valid prefix by one.

Variant: remove all occurrences of value

function removeElement(nums: number[], val: number): number {
  let write = 0
  for (let read = 0; read < nums.length; read++) {
    if (nums[read] !== val) nums[write++] = nums[read]
  }
  return write
}

This pattern appears in logs cleanup, dedup pipelines, and stream compaction systems.

Core Pattern 2: Hash-Assisted Lookup

Use when order is arbitrary and you need O(1) average membership checks.

Example: Two Sum (unsorted)

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>() // value -> index

  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need)!, i]
    seen.set(nums[i], i)
  }
  return []
}

Why it works

At index i, we ask whether the complement already appeared. If yes, we have the earliest matching pair in one pass.

Trade-off

• time: O(n)
• space: O(n)

Use this over two-pointers when array is unsorted and sort order must be preserved.

Core Pattern 3: Frequency Modeling for Strings

Many string problems reduce to “compare frequency vectors.”

Anagram (HashMap version)

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false

  const freq = new Map<string, number>()
  for (const ch of s) freq.set(ch, (freq.get(ch) ?? 0) + 1)

  for (const ch of t) {
    const count = freq.get(ch) ?? 0
    if (count === 0) return false
    freq.set(ch, count - 1)
  }
  return true
}

Faster variant for lowercase a-z only

function isAnagramLowercase(s: string, t: string): boolean {
  if (s.length !== t.length) return false
  const cnt = new Array<number>(26).fill(0)
  const a = "a".charCodeAt(0)

  for (let i = 0; i < s.length; i++) {
    cnt[s.charCodeAt(i) - a]++
    cnt[t.charCodeAt(i) - a]--
  }
  return cnt.every((x) => x === 0)
}

Interview rule: if alphabet is fixed/small, array counter beats hashmap for speed and simplicity.

Core Pattern 4: In-Place Reversal and Symmetry

Arrays and strings often ask symmetry questions.

Reverse char array in place

function reverseChars(arr: string[]): void {
  let l = 0
  let r = arr.length - 1
  while (l < r) {
    ;[arr[l], arr[r]] = [arr[r], arr[l]]
    l++
    r--
  }
}

Valid palindrome with normalization

function isAlnum(c: string): boolean {
  return /[a-zA-Z0-9]/.test(c)
}

function isPalindrome(s: string): boolean {
  let l = 0
  let r = s.length - 1
  while (l < r) {
    while (l < r && !isAlnum(s[l])) l++
    while (l < r && !isAlnum(s[r])) r--
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false
    l++
    r--
  }
  return true
}

This pattern is a direct bridge into two-pointers.

Core Pattern 5: Matrix as “Array of Arrays”

2D problems are index arithmetic problems.

Row-major indexing

For matrix m x n, element (r, c) in flattened array sits at:

idx = r * n + c

Example: matrix traversal directions

const DIRS = [
  [1, 0],  // down
  [-1, 0], // up
  [0, 1],  // right
  [0, -1], // left
] as const

If bounds checks are wrong, everything fails. Be strict with:

• 0 <= r < rows
• 0 <= c < cols

Common Interview Traps (Arrays/Strings)

1. Forgetting empty input ([], "")
2. Assuming sorted order when not guaranteed
3. Off-by-one in loops (i < n vs i <= n)
4. Confusing “subarray” (contiguous) with “subsequence” (not contiguous)
5. Using shift() in hot loops (O(n) each)
6. Ignoring duplicates in pair/count problems
7. Re-sorting repeatedly inside loops (hidden O(n log n) blowups)
8. Mutating input when prompt expects pure function

How to Write Better Explanations in Interviews

State three things explicitly:

1. Data model: “I will scan once and store seen values in a map.”
2. Invariant: “Before each step, map contains all previous values.”
3. Complexity: “Each element processed once; map ops O(1) average -> O(n) time, O(n) space.”

Interviewers reward reasoning quality more than syntax speed.

Mini Problem Ladder (Recommended Practice)

Easy

• Remove Duplicates from Sorted Array
• Valid Anagram
• Valid Palindrome
• Best Time to Buy and Sell Stock

Medium

• Two Sum II (sorted) / 3Sum
• Product of Array Except Self
• Group Anagrams
• Longest Substring Without Repeating Characters

Hard-ish foundations

• First Missing Positive
• Minimum Window Substring
• Trapping Rain Water

Complexity Cheat Sheet

Final Guideline

Arrays are the default battlefield.
If a problem gives linear data, do not jump to exotic structures first.

Ask in order:

1. Can one pass solve it?
2. If not, what repeated work can I cache (map/prefix)?
3. If contiguous, can window/pointers avoid nested loops?

Master this sequence and you’ll solve a large chunk of interview problems with clean, explainable solutions.