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 `0`, `right` starts at `n - 1`. Each loop iteration swaps `arr(left)` and `arr(right)` and moves the pointers toward each other.

Basic Implementation

basic.scala
Replay: real traced execution (multi-file project)
object Main {
	def main(args: Array[String]): Unit = {
		val arr = Array(1, 2, 3, 4, 5, 6, 7)
		var left = 0
		var right = arr.length - 1
		while (left < right) {
			val tmp = arr(left)
			arr(left) = arr(right)
			arr(right) = tmp
			left = left + 1
			right = right - 1
		}
		println(arr.mkString("[", ", ", "]"))
	}
}

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

    2def main(args: Array[String]): Unit = {3	val arr = Array(1, 2, 3, 4, 5, 6, 7)4	var left = 0
    values this step[1, 2, 3, 4, 5, 6, 7]arr

  2. left ← 0

    3val arr = Array(1, 2, 3, 4, 5, 6, 7)4var left = 05var right = arr.length - 1
    values this step0left[1, 2, 3, 4, 5, 6, 7]arr

  3. right ← 6

    4var left = 05var right = arr.length - 16while (left < right) {
    values this step6right0left

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

    7val tmp = 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 + 111right = right - 1
    values this step0 → 1left

  6. right ← 5

    10	left = left + 111	right = right - 112}
    values this step6 → 5right

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

    7val tmp = 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 + 111right = right - 1
    values this step1 → 2left

  9. right ← 4

    10	left = left + 111	right = right - 112}
    values this step5 → 4right

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

    7val tmp = 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 + 111right = right - 1
    values this step2 → 3left

  12. right ← 3

    10	left = left + 111	right = right - 112}
    values this step4 → 3right

  13. while (left < right)

    5var right = arr.length - 16while (left < right) {7	val tmp = arr(left)
    values this step[7, 6, 5, 4, 3, 2, 1]arr3left3right

Complexity

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

Implementation notes

  • Scala: explicit three-line val tmp = arr(left); arr(left) = arr(right); arr(right) = tmp swap keeps the move visible. The stdlib arr.reverse (or Array.copyOf with a reversed range) would hide the lesson.
  • var left = 0 and var right = arr.length - 1 use plain Int indices; the left < right guard handles the meet-in-the-middle exit honestly for the odd-length canonical input.
  • The replay shows both left and right, the values about to be swapped, and the array contents after the swap. The loop-exit frame is the moment the pointers meet.