Array Traversal Patterns

Most array problems are one of four walks. Recognising which one you need is faster than inventing a solution from scratch.

1. Single pass with running state

Carry one value through the array and update it as you go. Works whenever the answer depends only on what you have already seen.

function largest(items) {
  let best = items[0]
  for (const n of items) {
    if (n > best) best = n
  }
  return best
}

// Largest sum of any run of consecutive numbers.
function bestRun(items) {
  let best = items[0]
  let current = items[0]

  for (let i = 1; i < items.length; i++) {
    current = Math.max(items[i], current + items[i])
    best = Math.max(best, current)
  }

  return best
}

console.log(bestRun([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  // 6

bestRun is worth reading twice. The trick is that you never need the whole array - only the best run ending at the current position.

2. Two indices from both ends

Start outside and walk inward. Needs the array sorted, or the problem to be symmetric.

function isPalindrome(items) {
  let left = 0
  let right = items.length - 1

  while (left < right) {
    if (items[left] !== items[right]) return false
    left++
    right--
  }

  return true
}

console.log(isPalindrome([1, 2, 1]))  // true
console.log(isPalindrome([1, 2, 3]))  // false

3. Two indices moving forward

One pointer reads, the other writes. This is how you rearrange in place without allocating.

// Strip out every zero without creating a new array.
function removeZeros(items) {
  let write = 0

  for (let read = 0; read < items.length; read++) {
    if (items[read] !== 0) {
      items[write] = items[read]
      write++
    }
  }

  items.length = write
  return items
}

console.log(removeZeros([0, 1, 0, 3, 12]))  // [1, 3, 12]

4. Remember what you have seen

When the answer depends on a value appearing earlier, store it in a Set or Map rather than scanning backwards.

function firstRepeat(items) {
  const seen = new Set()

  for (const n of items) {
    if (seen.has(n)) return n
    seen.add(n)
  }

  return null
}

console.log(firstRepeat([1, 2, 3, 2]))  // 2
console.log(firstRepeat([1, 2, 3]))     // null

Choosing between them

• Answer depends only on what came before - single pass.
• Array is sorted and you want a pair - both ends.
• Modifying in place without extra memory - read and write pointers.
• Need to know if something appeared earlier - a Set or Map.

Walking backwards

When you remove elements while looping, going forwards skips items: removing index 2 shifts index 3 into its place, and the loop then moves to index 3, stepping over it. Iterating backwards avoids the problem entirely because the indices you have not visited yet never move.

const items = [1, 2, 2, 3, 2]

// Wrong — skips the second 2 of each pair.
for (let i = 0; i < items.length; i++) {
  if (items[i] === 2) items.splice(i, 1)
}

// Right — later indices are untouched by earlier removals.
const values = [1, 2, 2, 3, 2]
for (let i = values.length - 1; i >= 0; i--) {
  if (values[i] === 2) values.splice(i, 1)
}

console.log(values)  // [1, 3]

Choosing the loop itself

• for with an index - when you need the index, or must go backwards.
• for...of - when you only need values. Works on strings, Maps and Sets too.
• forEach - readable, but you cannot break out of it.
• some / every - an early exit with a boolean result, which is the readable way to say "stop when found".

In an interview, a plain indexed for loop is never the wrong answer. The functional methods are clearer to read but allocate and cannot short-circuit, which matters once n is large.