2.1 Array Traversal

Array traversal is the base operation for all algorithms over linear data. The task is to visit elements in a defined order, maintain a small amount of state, and ensure that every access is valid. Most higher level patterns reduce to controlled traversal with stronger invariants.

Problem

You have an array A of length n. You want to process each element, possibly combining information from earlier positions, while maintaining correctness and linear time complexity.

Model

An array is a function [ A : {0,1,\dots,n-1} \to T ] for some element type T. A traversal is a sequence of accesses A[i] where the index i ranges over a subset of valid indices.

Correct traversal requires:

• Index bounds: (0 \le i < n)
• Deterministic order: typically increasing or decreasing
• A maintained invariant over processed elements

Forward Traversal

The simplest traversal processes elements from left to right.

for i := 0; i < n; i++ {
    process(A[i])
}

Invariant:

At the start of iteration i, all elements A[0] through A[i-1] have been processed exactly once.

This invariant is sufficient for any algorithm that depends only on past elements.

Example: Sum of Array

sum := 0
for i := 0; i < n; i++ {
    sum += A[i]
}

Invariant:

After iteration i, [ \text{sum} = \sum_{k=0}^{i} A[k] ]

Reverse Traversal

Traversal from right to left is symmetric but useful when future elements matter.

for i := n-1; i >= 0; i-- {
    process(A[i])
}

Invariant:

At the start of iteration i, all elements A[i+1] through A[n-1] have been processed.

Indexed Traversal with State

Most algorithms attach state to traversal.

Example: Track maximum value so far.

maxVal := A[0]
for i := 1; i < n; i++ {
    if A[i] > maxVal {
        maxVal = A[i]
    }
}

Invariant:

At iteration i, [ \text{maxVal} = \max(A[0], \dots, A[i]) ]

The correctness follows directly from maintaining this invariant.

Conditional Traversal

Sometimes only certain elements are processed.

for i := 0; i < n; i++ {
    if A[i] % 2 == 0 {
        process(A[i])
    }
}

Invariant:

All even elements in A[0..i-1] have been processed.

Early Termination

Traversal may stop once a condition is met.

for i := 0; i < n; i++ {
    if A[i] == target {
        return i
    }
}
return -1

Invariant:

If the loop reaches index i, then target does not appear in A[0..i-1].

Multiple Pass Traversal

Some algorithms require more than one pass.

Example: compute prefix sums, then use them.

prefix := make([]int, n)
prefix[0] = A[0]
for i := 1; i < n; i++ {
    prefix[i] = prefix[i-1] + A[i]
}

Invariant:

[ \text{prefix}[i] = \sum_{k=0}^{i} A[k] ]

This transforms repeated range queries into constant time operations.

Two-Dimensional Traversal

Arrays may represent matrices.

for i := 0; i < rows; i++ {
    for j := 0; j < cols; j++ {
        process(A[i][j])
    }
}

Invariant:

All elements in rows < i, and columns < j in row i, have been processed.

Boundary Conditions

Correct traversal must handle:

Common error:

for i := n-1; i > 0; i-- // skips index 0

Correct form:

for i := n-1; i >= 0; i--

Complexity

A single traversal performs exactly n iterations.

Time complexity: [ O(n) ]

Space complexity: [ O(1) ] unless auxiliary storage is introduced.

Design Pattern

Every traversal can be described by three components:

1. Order: forward, reverse, or custom
2. State: variables updated per step
3. Invariant: property preserved after each iteration

A correct algorithm makes the invariant explicit and ensures it is maintained at every step.

Takeaway

Array traversal is not just iteration. It is controlled iteration with invariants. Once the invariant is identified, the traversal becomes a direct implementation of that invariant, and correctness follows from its preservation.