# 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.

```go
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

```go
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.

```go
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.

```go
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.

```go
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.

```go
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.

```go
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.

```go
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:

| Case           | Requirement                    |
| -------------- | ------------------------------ |
| Empty array    | Loop must not execute          |
| Single element | Exactly one iteration          |
| Large indices  | Avoid overflow in `i++`        |
| Reverse loop   | Ensure termination at `i >= 0` |

Common error:

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

Correct form:

```go
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.