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 {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 `1`, `right` starts at `#arr`. Each loop iteration swaps `arr[left]` and `arr[right]` and moves the pointers toward each other.

Basic Implementation

basic.lua
Replay: real traced execution (multi-file project)
local arr = {1, 2, 3, 4, 5, 6, 7}
local left = 1
local right = #arr
while left < right do
	local tmp = arr[left]
	arr[left] = arr[right]
	arr[right] = tmp
	left = left + 1
	right = right - 1
end
io.write("[")
for i = 1, #arr do
	if i > 1 then io.write(", ") end
	io.write(tostring(arr[i]))
end
io.write("]\n")

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

    1local arr = {1, 2, 3, 4, 5, 6, 7}2local left = 1
    values this step[1, 2, 3, 4, 5, 6, 7]arr

  2. left ← 1

    1local arr = {1, 2, 3, 4, 5, 6, 7}2local left = 13local right = #arr
    values this step1left[1, 2, 3, 4, 5, 6, 7]arr

  3. right ← 7

    2local left = 13local right = #arr4while left < right do
    values this step7right1left

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

    5local tmp = arr[left]6arr[left] = arr[right]7arr[right] = tmp
    values this step[1, 2, 3, 4, 5, 6, 7] → [7, 2, 3, 4, 5, 6, 1]arr1left7right

  5. left ← 2

    7arr[right] = tmp8left = left + 19right = right - 1
    values this step1 → 2left

  6. right ← 6

    8	left = left + 19	right = right - 110end
    values this step7 → 6right

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

    5local tmp = arr[left]6arr[left] = arr[right]7arr[right] = tmp
    values this step[7, 2, 3, 4, 5, 6, 1] → [7, 6, 3, 4, 5, 2, 1]arr2left6right

  8. left ← 3

    7arr[right] = tmp8left = left + 19right = right - 1
    values this step2 → 3left

  9. right ← 5

    8	left = left + 19	right = right - 110end
    values this step6 → 5right

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

    5local tmp = arr[left]6arr[left] = arr[right]7arr[right] = tmp
    values this step[7, 6, 3, 4, 5, 2, 1] → [7, 6, 5, 4, 3, 2, 1]arr3left5right

  11. left ← 4

    7arr[right] = tmp8left = left + 19right = right - 1
    values this step3 → 4left

  12. right ← 4

    8	left = left + 19	right = right - 110end
    values this step5 → 4right

  13. while left < right do

    3local right = #arr4while left < right do5	local tmp = arr[left]
    values this step[7, 6, 5, 4, 3, 2, 1]arr4left4right

Complexity

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

Implementation notes

  • Lua: explicit three-line local tmp = arr[left]; arr[left] = arr[right]; arr[right] = tmp swap keeps the move visible. Lua has no stdlib reverse for tables, but a for loop with arr[i], arr[#arr - i + 1] = arr[#arr - i + 1], arr[i] (parallel assignment) would collapse the swap into a single frame.
  • left = 1 and right = #arr use plain integer indices; the # length operator 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.