Reverse an Array In Place
Problem
Read an array and print it reversed. Swap elements inside the same array (no second array).
Constraints
- 1 <= n <= 10^5
Examples
Input
5 1 2 3 4 5
Output
5 4 3 2 1
Solutions
Swapping pairs from both ends needs only n / 2 steps and no extra memory.
/*
* Problem : Process an array.
* Input : n, then n integers.
* Output : The reversed array.
* Approach: Two pointers.
* Time : O(n)
* Space : O(1)
* Java : 8 or newer.
*/
import java.util.Scanner;
import java.util.Arrays;
import java.util.stream.Collectors;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static int[] solve(int[] a) {
// Step 1: One pointer at the start and one at the end.
int left = 0;
int right = a.length - 1;
// Step 2: Swap the two elements, then move both pointers to the middle. Stop when they meet.
while (left < right) {
int temporary = a[left];
a[left] = a[right];
a[right] = temporary;
left++;
right--;
}
return a;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
System.out.println(Arrays.stream(solve(a)).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
}
}
Hints (1)
- When do the two pointers stop?