Array Buffering

Array buffering uses temporary storage while processing data. The buffer holds intermediate values before they are copied, merged, flushed, or written back.

You use it when in-place updates would overwrite values that are still needed.

Problem

Given an input array $A$ , produce an output array $B$ using temporary storage so that reads from $A$ are not corrupted by writes.

For many algorithms, the buffer has length:

n = length(A)

Algorithm

Copy transformed elements into a buffer, then write them back.

buffer_transform(A, f):
    n = length(A)
    B = allocate(n)

    for i from 0 to n - 1:
        B[i] = f(A[i])

    for i from 0 to n - 1:
        A[i] = B[i]

Example

Let

A = [8, 3, 5, 1, 9]

Apply:

f(x) = 2x

Buffer after the first pass:

B = [16, 6, 10, 2, 18]

step	action	array
1	read from A, write to B	A unchanged
2	copy B back to A	[16, 6, 10, 2, 18]

Correctness

The first pass reads only from the original array and writes only to the buffer. Therefore, no input value is overwritten before it is used.

The second pass copies each buffered value back to the same index in the original array. Thus the final array contains exactly the transformed values.

Complexity

operation	time
fill buffer	$O(n)$
write back	$O(n)$
total	$O(n)$

Space usage:

O(n)

When to Use

Array buffering is appropriate when:

output depends on original input values
in-place writes would corrupt later reads
merging or stable rearrangement needs temporary storage
batch writes are simpler than immediate mutation

It is less suitable when memory is limited and a true in-place algorithm is available.

Implementation

def buffer_transform(a, f):
    b = [None] * len(a)

    for i in range(len(a)):
        b[i] = f(a[i])

    for i in range(len(a)):
        a[i] = b[i]

func BufferTransform[T any](a []T, f func(T) T) {
    b := make([]T, len(a))

    for i := 0; i < len(a); i++ {
        b[i] = f(a[i])
    }

    copy(a, b)
}