Question: Write a program to reverse an array or string.
Example:
Input : arr[] = {1, 2, 3}
Output : ar[] = {3, 2, 1}
Logic: O ( n )
- Take two pointers i and j
- put i on arr [ 0 ] and put j on arr [ arr.length -1 ]
- swap i and j till i becomes greater than or equal to j
import java.util.Scanner;
public class Solution{
//This function depicts the recursive solution of the question.
public static void reverseArray(int arr[],int i, int j){
if(i >= j){
return;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
reverseArray(arr,i++,j--);
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0 ; i<arr.length ; i++){
arr[i] = sc.nextInt();
}
int i=0;
int j = arr.length-1;
reverseArray(arr, i, j);//For recurssive function above
//This is itterative method.
while(i<j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
for(int k=0; k<arr.length; k++){
System.out.print(arr[k]+" ");
}
System.out.println();
}
}
Top comments (2)
Nice post! Question though, wouldn't the time complexity be O(n / 2 ) since it only goes through half the length of the array?
That's true but if you simplify (n/2) so it becomes (n^-2). As power is negative we neglect it. and hence the total complexity becomes O(n). What are your views?