Algorithms from zero

Traversing an array

Crux Traversing means visiting every element in an array, and it is the single most common operation you will perform. Learn the loop shapes, patterns (accumulate, find, transform, test), early exit, and backwards traversal.

◷ 16 min

You have an array of numbers and you need to process every one of them. You start at index 0, move to 1, then 2, and so on until the end. That simple journey — visiting each element in order — is traversal. It is the foundation of almost every algorithm you will write.

Goal

After this lesson you can traverse an array with a for loop, identify common traversal patterns (accumulate, find, transform, test), understand when and why to use index vs. value, apply early exit to stop as soon as the answer is known, traverse two arrays together, and reverse-traverse an array from end to start.

The idea

Traversal is the act of visiting every element in an array in a specific order, usually from the start to the end. The simplest traversal loop is:

for (let i = 0; i < arr.length; i++) {
  // Process arr[i]
}

This loop visits each element exactly once, from index 0 to arr.length - 1. It is O(n) because you touch every element.

Five traversal patterns:

Accumulate (sum, product, count) — initialize an accumulator before the loop, update it with each element, return it after the loop.
Find (first match, max, min) — scan through the array until a condition is met, return the result.
Transform (build a new array) — as you traverse, build a new array by applying a function to each element.
Test (does any / does every element satisfy a condition?) — scan and return true/false when the answer is clear.
Early exit — stop scanning as soon as you know the answer, without visiting all remaining elements.

Index vs. value:

When you write for (let i = 0; i < arr.length; i++), you iterate with the index i. Inside the loop, you access arr[i] to get the value. Sometimes you need the index (to modify the array, to track position), and sometimes you only need the value. JavaScript offers for...of loops for value-only iteration:

for (let value of arr) {
  // Process value directly
}

But if you need the index (to change elements, to know position), you must use the index loop.

Early exit and best/worst case:

When you search for a value and return immediately upon finding it, you apply early exit. This changes the best and worst cases:

Best case: found at index 0 → 1 step → O(1)
Worst case: not found (check all n) → n steps → O(n)
Big-O: still O(n) because we analyze the worst case

Early exit does not change Big-O, but it changes real-world performance. For a best case, you can be much faster.

Backwards traversal:

Start at the end and move towards the start:

for (let i = arr.length - 1; i >= 0; i--) {
  // Process arr[i] from end to start
}

Common mistake: starting at arr.length instead of arr.length - 1. The last valid index is arr.length - 1.

Traversing two arrays together:

If you have two arrays of the same length, you can iterate both in parallel:

for (let i = 0; i < arr1.length; i++) {
  // Process arr1[i] and arr2[i] together
}

The code

Let us code the five traversal patterns and early exit:

1. Accumulate (sum):

function sum(arr) {
  let total = 0;  // Initialize accumulator
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];  // Add each element
  }
  return total;  // Return the accumulated value
}

2. Find (first index of value, or -1 if not found):

function indexOf(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;  // Early exit: found it
    }
  }
  return -1;  // Reached the end without finding
}

3. Transform (double each element):

function doubled(arr) {
  let result = [];  // Build a new array
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);  // Transform each element
  }
  return result;
}

4. Test (does the array contain a negative number?):

function hasNegative(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < 0) {
      return true;  // Early exit: answer is yes
    }
  }
  return false;  // No negatives found
}

5. Count matching elements:

function countMatching(arr, predicate) {
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    if (predicate(arr[i])) {
      count++;
    }
  }
  return count;
}

Try running these:

Output

Step-by-step trace

Let us trace indexOf (find) with early exit. We are searching for the value 5 in [1, 7, 5, 3]:


      1
      function indexOf(arr, target) {
    

      2
        for (let i = 0; i < arr.length; i++) {
    

      3
          if (arr[i] === target) {
    

      4
            return i;
    

      5
          }
    

      6
        }
    

      7
        return -1;
    

      8
      }

Complexity

All traversal loops touch every element at least once in the worst case, so the time complexity is O(n).

However, early exit changes the best case:

Operation	Best Case	Average Case	Worst Case	Big-O
Sum all elements	O(n)	O(n)	O(n)	O(n)
Find a value (early exit)	O(1) found at start	O(n/2)	O(n) not found	O(n)
Check if any element is negative (early exit)	O(1) found at start	O(n/2)	O(n) none found	O(n)
Count matching elements	O(n)	O(n)	O(n)	O(n)
Transform (build new array)	O(n)	O(n)	O(n)	O(n)

Key insight: Early exit can give you a much faster real-world performance in the best case, even though Big-O analysis focuses on the worst case. In interviews, you can impress by noting: “This is O(n) worst case, but O(1) if the answer is found immediately.”

Practice 0 / 5

Write a function that finds the maximum value in [3, 7, 2, 9, 1]. What is the maximum?

How many steps does indexOf take in the worst case if the target is not found in an array of 100 elements?

When you traverse an array and need to modify each element (e.g., multiply by 2), why do you need the index and not just the value?

What is the time complexity of a function that sums all elements in an array of n elements?

Arrange these steps to traverse an array backwards from index 4 (assuming the array has 5 elements):

Start loop: i = 4
Decrement i (i--)
Check condition: i >= 0
Process arr[i]

Edge cases

Empty arrays. If the input is an empty array, the loop for (let i = 0; i < arr.length; i++) never runs (because 0 < 0 is false). For patterns like sum and count, returning 0 is correct. For patterns like find and max, returning -1 or null is sensible (there is no max of an empty array). Always think about edge cases.

Common mistake

Off-by-one errors in backwards traversal. The most common mistake is starting at i = arr.length (which is out of bounds) instead of i = arr.length - 1. The last valid index is always arr.length - 1. Test with a small array: [1, 2, 3] has length 3, and the last index is 2. Start your backwards loop at 2, not 3.

Check yourself

Quiz

Why does a search function that returns as soon as it finds the target (early exit) still have O(n) Big-O time complexity?

Recap

Traversal is visiting every element in an array, usually from start to end. Key concepts:

The basic loop: for (let i = 0; i < arr.length; i++) visits each element in O(n) time.
Five patterns:
- Accumulate: initialize, update, return
- Find: return when condition is true
- Transform: build a new array
- Test: return true/false when answer is known
- Count: increment a counter
Index vs. value: Use the index loop if you need position or modification. Use for...of for value-only traversal.
Early exit: Return immediately when the answer is found. Improves best case but does not change Big-O (still O(n) worst case).
Backwards traversal: Start at arr.length - 1, use i >= 0, decrement with i--. Common mistake: starting at arr.length.
Two arrays together: Loop over indices and process both arrays in parallel.

Traversal is the foundation of nearly every array algorithm you will write. Master these shapes now; you will reuse them a thousand times.

Continue the climb ↑Two pointers