# Array Reversal

# Array Reversal

Array reversal rearranges elements so that the first becomes the last, the second becomes the second last, and so on.

You use it as a basic primitive in many algorithms, including rotation, palindrome checks, and two-pointer techniques.

## Problem

Given an array $A$ of length $n$, transform it into:

$$
A' = [a_{n-1}, a_{n-2}, \dots, a_0]
$$

## Algorithm

Use two pointers from both ends and swap elements until they meet.

```id="array-reversal"
reverse(A):
    l = 0
    r = length(A) - 1

    while l < r:
        swap A[l], A[r]
        l += 1
        r -= 1
```

## Example

Let

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

| step |  l |  r | array           |
| ---- | -: | -: | --------------- |
| 1    |  0 |  4 | [9, 3, 5, 1, 8] |
| 2    |  1 |  3 | [9, 1, 5, 3, 8] |
| 3    |  2 |  2 | stop            |

Result:

$$
[9, 1, 5, 3, 8]
$$

## Correctness

At each step, the algorithm swaps symmetric elements around the center. After $k$ steps, positions $0$ through $k-1$ and $n-k$ through $n-1$ are in their correct reversed positions.

When the pointers meet or cross, all positions have been processed exactly once, so the array is fully reversed.

## Complexity

| operation | time   |
| --------- | ------ |
| reverse   | $O(n)$ |

Space usage:

$$
O(1)
$$

## When to Use

Array reversal is appropriate when:

* reversing order is required
* used as a building block for other algorithms
* in-place transformation is preferred

It is less suitable when:

* the original array must remain unchanged
* immutability is required, in which case create a copy

## Implementation

```python id="array-reversal-python"
def reverse(a):
    l, r = 0, len(a) - 1
    while l < r:
        a[l], a[r] = a[r], a[l]
        l += 1
        r -= 1
```

```go id="array-reversal-go"
func Reverse[T any](a []T) {
    l, r := 0, len(a)-1
    for l < r {
        a[l], a[r] = a[r], a[l]
        l++
        r--
    }
}
```