Arrays & Strings

What is an array?

An array is a block of contiguous memory where every element sits right next to the previous one. That contiguous layout is why reading any element by index is O(1) — the CPU can compute the exact memory address from base + index × element_size without traversing anything.

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

Array operation complexity

The key takeaway: random access is cheap, middle insertion/deletion is expensive.

Strings in JavaScript

Strings are immutable in JavaScript. You cannot change a character in place.

let s = "hello"
s[0] = "H"  // silently does nothing
console.log(s)  // still "hello"

This matters in interviews. If you need to “modify” a string, you have to build a new one — which is O(n). A common pattern is to convert to an array of characters, manipulate, then join('').

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

Core patterns

1. In-place array modification

Many problems ask you to modify the array in O(1) extra space. The trick is using two pointers — one for reading, one for writing.

// Remove duplicates from sorted array — in-place, O(1) space
function removeDuplicates(nums: number[]): number {
  let write = 1
  for (let read = 1; read < nums.length; read++) {
    if (nums[read] !== nums[read - 1]) {
      nums[write] = nums[read]
      write++
    }
  }
  return write  // new logical length
}

2. Building a result array

When in-place isn’t required, build a new array as you scan. Cleaner code, O(n) space trade-off.

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>()  // value → index
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (seen.has(complement)) return [seen.get(complement)!, i]
    seen.set(nums[i], i)
  }
  return []
}

3. Anagram check

A classic string problem. Two approaches:

Sort approach — O(n log n):

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false
  return s.split('').sort().join('') === t.split('').sort().join('')
}

Hashmap approach — O(n):

function isAnagram(s: string, t: string): boolean {
  if (s.length !== t.length) return false
  const count = new Map<string, number>()
  for (const c of s) count.set(c, (count.get(c) ?? 0) + 1)
  for (const c of t) {
    if (!count.has(c) || count.get(c)! === 0) return false
    count.set(c, count.get(c)! - 1)
  }
  return true
}

Prefer the hashmap approach when you need O(n) and the sort approach when brevity matters more than speed.

The golden rule

Arrays are your default data structure. Only reach for a linked list, tree, or heap when you have a specific reason — insertion order, hierarchical data, priority ordering. If you don’t have a reason, use an array.

When you see a problem involving subarrays, consecutive elements, or pairs — your first thought should be two pointers or sliding window. Both are covered in the next two topics.