Arrays and Iteration

Reverse Array In Place (Two Pointers)

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

Algorithm

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

two pointers `left` starts at index `1`, `right` starts at `length(arr)`. Each loop iteration swaps `arr[left]` and `arr[right]` and moves the pointers toward each other.

Basic Implementation

basic.R
Replay: real traced execution (multi-file project)
arr <- c(1, 2, 3, 4, 5, 6, 7)
left <- 1
right <- length(arr)
while (left < right) {
	tmp <- arr[left]
	arr[left] <- arr[right]
	arr[right] <- tmp
	left <- left + 1
	right <- right - 1
}
cat("[", paste(arr, collapse = ", "), "]\n", sep = "")

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

    1arr <- c(1, 2, 3, 4, 5, 6, 7)2left <- 1
    values this step[1, 2, 3, 4, 5, 6, 7]arr

  2. left ← 1

    1arr <- c(1, 2, 3, 4, 5, 6, 7)2left <- 13right <- length(arr)
    values this step1left[1, 2, 3, 4, 5, 6, 7]arr

  3. right ← 7

    2left <- 13right <- length(arr)4while (left < right) {
    values this step7right1left

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

    5tmp <- 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 - 110}
    values this step7 → 6right

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

    5tmp <- 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 - 110}
    values this step6 → 5right

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

    5tmp <- 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 - 110}
    values this step5 → 4right

  13. while (left < right)

    3right <- length(arr)4while (left < right) {5	tmp <- arr[left]
    values this step[7, 6, 5, 4, 3, 2, 1]arr4left4right

Complexity

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

Implementation notes

  • R: explicit three-line tmp <- arr[left]; arr[left] <- arr[right]; arr[right] <- tmp swap keeps the move visible. The stdlib rev(arr) returns a fresh vector instead of mutating, and arr[c(left, right)] <- arr[c(right, left)] (vectorised swap) would collapse the move into a single frame.
  • left <- 1 and right <- length(arr) use plain integer indices; the length() call returns the fixed length of the canonical vector.
  • The replay distinguishes swap frames from pointer-advance frames so the viewer can see left and right converge.