Arrays and strings

Overview

An array stores elements in one contiguous block of memory, so the address of element i is start + i x size. That is why reading or writing arr[i] is O(1). Inserting or deleting in the middle is O(n), because every later element must shift by one position.

Strings are arrays of characters. In both JavaScript and Java they are immutable: every modification creates a new string. Most string problems reduce to counting characters, comparing positions with two pointers, or building a result efficiently with an array or StringBuilder.

When to use it

• You need fast random access by index.
• Data size is known or grows mostly at the end (append is amortized O(1)).
• You want cache-friendly sequential scans, which are much faster in practice than pointer-based structures.
• Characters come from a small alphabet, so an int[26] or int[128] array can replace a hash map.

Problem patterns it solves

Where it is used in real software

Key terms

Contiguous memory

Elements are stored next to each other, enabling O(1) index access and fast CPU caching.

Dynamic array

An array that resizes (usually doubling) when full: JS arrays, Java ArrayList.

Immutable string

Cannot change after creation; s += c builds a new string.

StringBuilder

Java's mutable character buffer with amortized O(1) append.

charCodeAt / char arithmetic

Converting 'a'..'z' to 0..25 with c - 'a' (Java) or s.charCodeAt(i) - 97 (JS).

Core operations and their cost

1. 1
   Access arr[i]: O(1)

   Address arithmetic jumps straight to the element.

2. 2
   Append at the end: amortized O(1)

   Occasionally the array doubles and copies, but the average stays constant.

3. 3
   Insert or delete at index i: O(n)

   Elements after i must shift. In JS, splice and unshift cost O(n).

4. 4
   Search unsorted: O(n)

   Check every element. If sorted, binary search is O(log n).

5. 5
   Build strings efficiently

   Collect characters in an array (JS) or StringBuilder (Java), then join once at the end.

Valid anagram with a frequency array

s = "listen", t = "silent", counts = int[26]

All 26 counts are zero, so the strings are anagrams. O(n) time and O(1) space, because the counts array always has 26 slots regardless of n.

Implementation

1// Frequency counting with a fixed array instead of a Map2function isAnagram(s, t) {3  if (s.length !== t.length) return false;4  const counts = new Array(26).fill(0);5  for (let i = 0; i < s.length; i++) {6    counts[s.charCodeAt(i) - 97]++;7    counts[t.charCodeAt(i) - 97]--;8  }9  return counts.every((c) => c === 0);10}11 12// In-place: move zeroes to the end, keep order of non-zero values13function moveZeroes(nums) {14  let write = 0;15  for (let read = 0; read < nums.length; read++) {16    if (nums[read] !== 0) {17      [nums[write], nums[read]] = [nums[read], nums[write]];18      write++;19    }20  }21}22 23// Rotate right by k using three reversals: O(n) time, O(1) space24function rotate(nums, k) {25  k %= nums.length;26  const reverse = (l, r) => {27    while (l < r) [nums[l++], nums[r--]] = [nums[r], nums[l]];28  };29  reverse(0, nums.length - 1);30  reverse(0, k - 1);31  reverse(k, nums.length - 1);32}33 34// Build strings with an array, then join once35function compress(chars) {36  const parts = [];37  for (let i = 0; i < chars.length; ) {38    let j = i;39    while (j < chars.length && chars[j] === chars[i]) j++;40    parts.push(chars[i], j - i > 1 ? String(j - i) : "");41    i = j;42  }43  return parts.join("");44}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using JS default sort on numbers.

  Fix: [10, 9, 1].sort() gives [1, 10, 9] because it compares strings. Use sort((a, b) => a - b).

• Comparing Java strings with ==.

  Fix: Use s.equals(t); == compares references.

• Concatenating strings inside a loop.

  Fix: Use StringBuilder (Java) or parts.push then join (JS).

• Off-by-one at array boundaries.

  Fix: Loop i < n, and check i + 1 < n before reading arr[i + 1].

• Modifying an array while iterating over it.

  Fix: Use a separate write pointer, or iterate backward when deleting.

Interview questions

Practice problems