Arrays and Iteration

Reverse Array In Place (Two Pointers)

Walk two indices toward each other from the ends of the array, swapping at each step. Stops when the indices meet or cross. Demonstrates the two-pointer pattern with the smallest possible state.

Algorithm

Canonical input arr=(1 2 3 4 5 6 7) (odd length, middle element stays put) yields three swap frames and reverses to [7, 6, 5, 4, 3, 2, 1].

two pointers `left` starts at index `0`, `right` starts at `${#arr[@]} - 1`. Each loop iteration swaps `arr[left]` and `arr[right]` and moves the pointers toward each other.

Basic Implementation

basic.sh
Replay: real traced execution (multi-file project)
#!/usr/bin/env bash
set -euo pipefail
arr=(1 2 3 4 5 6 7)
left=0
right=$(( ${#arr[@]} - 1 ))
while [ "$left" -lt "$right" ]; do
	tmp=${arr[left]}
	arr[left]=${arr[right]}
	arr[right]=$tmp
	left=$((left + 1))
	right=$((right - 1))
done
printf '['
sep=''
for v in "${arr[@]}"; do
	printf '%s%d' "$sep" "$v"
	sep=', '
done
printf ']\n'

  1. arr ← [1, 2, 3, 4, 5, 6, 7]

    2set -euo pipefail3arr=(1 2 3 4 5 6 7)4left=0
    values this step[1, 2, 3, 4, 5, 6, 7]arr

  2. left ← 0

    3arr=(1 2 3 4 5 6 7)4left=05right=$(( ${#arr[@]} - 1 ))
    values this step0left[1, 2, 3, 4, 5, 6, 7]arr

  3. right ← 6

    4left=05right=$(( ${#arr[@]} - 1 ))6while [ "$left" -lt "$right" ]; do
    values this step6right0left

  4. arr ← [7, 2, 3, 4, 5, 6, 1]

    7tmp=${arr[left]}8arr[left]=${arr[right]}9arr[right]=$tmp
    values this step[1, 2, 3, 4, 5, 6, 7] → [7, 2, 3, 4, 5, 6, 1]arr0left6right

  5. left ← 1

    9arr[right]=$tmp10left=$((left + 1))11right=$((right - 1))
    values this step0 → 1left

  6. right ← 5

    10	left=$((left + 1))11	right=$((right - 1))12done
    values this step6 → 5right

  7. arr ← [7, 6, 3, 4, 5, 2, 1]

    7tmp=${arr[left]}8arr[left]=${arr[right]}9arr[right]=$tmp
    values this step[7, 2, 3, 4, 5, 6, 1] → [7, 6, 3, 4, 5, 2, 1]arr1left5right

  8. left ← 2

    9arr[right]=$tmp10left=$((left + 1))11right=$((right - 1))
    values this step1 → 2left

  9. right ← 4

    10	left=$((left + 1))11	right=$((right - 1))12done
    values this step5 → 4right

  10. arr ← [7, 6, 5, 4, 3, 2, 1]

    7tmp=${arr[left]}8arr[left]=${arr[right]}9arr[right]=$tmp
    values this step[7, 6, 3, 4, 5, 2, 1] → [7, 6, 5, 4, 3, 2, 1]arr2left4right

  11. left ← 3

    9arr[right]=$tmp10left=$((left + 1))11right=$((right - 1))
    values this step2 → 3left

  12. right ← 3

    10	left=$((left + 1))11	right=$((right - 1))12done
    values this step4 → 3right

  13. while [ "$left" -lt "$right" ]; do

    5right=$(( ${#arr[@]} - 1 ))6while [ "$left" -lt "$right" ]; do7	tmp=${arr[left]}
    values this step[7, 6, 5, 4, 3, 2, 1]arr3left3right

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • Bash: explicit three-line tmp=${arr[left]}; arr[left]=${arr[right]}; arr[right]=$tmp swap keeps the move visible. The shell has no built-in reverse for arrays; spawning printf '%s\n' "${arr[@]}" | tac would push the work to another process and return a stream instead of mutating the array.
  • left=0 and right=$(( ${#arr[@]} - 1 )) use plain integer indices; ${#arr[@]} returns the fixed length of the canonical array.
  • The replay distinguishes swap frames from pointer-advance frames so the viewer can see left and right converge.