Arrays and Immutable Strings

Arrays are indexed sequences with tradeoffs

An array gives each element a numbered position. Reading values[i] is constant time because the position directly identifies the slot. Work at the end is usually cheap; work at the front or middle often moves everything after it.

Dynamic arrays occasionally need a larger backing store. That is why push is described as amortized rather than worst-case O(1): one append may trigger a copy, but a long series of appends still averages constant work per operation.

Suppose the current storage has four slots and all are occupied:

capacity 4: [A, B, C, D]
push E
allocate a larger area: [_, _, _, _, _, _, _, _]
copy four values:       [A, B, C, D, _, _, _, _]
append E:               [A, B, C, D, E, _, _, _]

That resize makes this particular push O(n). The next few pushes simply fill open slots. Across a long sequence, the expensive copies happen infrequently enough that the average cost per push remains O(1). “Amortized” does not mean every push is constant; it means the sequence distributes the occasional larger bill.

Mutation versus copying

JavaScript methods do not all behave alike:

• sort, reverse, splice, push, and pop mutate the array.
• slice, map, filter, and spread create new arrays.

Mutation is useful when a problem requires O(1) auxiliary space, but it can surprise a caller that expected the original input to remain intact. State your choice explicitly.

Strings are values, not editable character arrays

You can read text[i], but you cannot assign a character back into the string. Operations such as slice, toLowerCase, and concatenation produce new strings.

Repeated result += character can create and copy a growing string many times. Modern engines optimize some cases, but an interview analysis should not depend on an invisible optimization. For predictable linear construction, collect pieces and join once:

function alternatingCase(input: string): string {
  const parts: string[] = []
  for (let i = 0; i < input.length; i += 1) {
    parts.push(i % 2 === 0 ? input[i].toUpperCase() : input[i].toLowerCase())
  }
  return parts.join("")
}

Choose the loop by the information you need

Use for...of when values are enough. Use an index loop when you need neighbors, positions, two moving boundaries, or an index in the answer.

Longest Common Prefix (LeetCode #14) gives an array of strings and asks for the longest starting substring shared by all of them. A column-by-column scan needs both the character position and each word:

function longestCommonPrefix(words: string[]): string {
  if (words.length === 0) return ""

  for (let column = 0; column < words[0].length; column += 1) {
    const expected = words[0][column]
    for (let row = 1; row < words.length; row += 1) {
      if (column >= words[row].length || words[row][column] !== expected) {
        return words[0].slice(0, column)
      }
    }
  }
  return words[0]
}

If there are w words and the shortest relevant prefix has length k, the scan is O(w · k). Describing it as O(n) hides the two dimensions.

Character codes and alphabets

Computers store characters using numeric codes. For lowercase English letters in the common ASCII range, the codes are consecutive:

"a".charCodeAt(0) → 97
"b".charCodeAt(0) → 98
"c".charCodeAt(0) → 99
...
"z".charCodeAt(0) → 122

Subtracting the code for a converts those codes into zero-based array positions:

a → 97  - 97 = 0
b → 98  - 97 = 1
z → 122 - 97 = 25

That makes a 26-element frequency array possible:

const counts = Array<number>(26).fill(0)

for (const character of word) {
  const index = character.charCodeAt(0) - "a".charCodeAt(0)
  counts[index] += 1
}

The technique is correct only when the input contract guarantees lowercase English letters. An uppercase A, punctuation mark, accented character, or emoji does not map into 0..25 under this rule. A Map is the safer general solution when the alphabet is not fixed by the constraints.

Common mistakes

• Calling shift() repeatedly to simulate a queue and accidentally creating O(n²) work.
• Mutating a caller’s array through sort() or reverse() without acknowledging it.
• Forgetting the comparator for numeric sorting.
• Treating strings as mutable arrays.
• Using for...of and then searching again for an index you could have retained.