How can I optimize my code for Swapping the array elements of given range of indexes with related element?

Question

Consider an array of integers A having N elements in which each element has a one- to-one relation with another array element.

For each i, where 1≤i≤N there exists a 1−>1 relation between element i and element N−i+1

The Task is to perform following operations on this array which are as follows:

Given two integers (L,R) we have to swap each element in that range with its related element.(See Sample explanation below)

Sample Input

5
1 2 3 4 5
2
1 2
2 3

Sample Output

5 2 3 4 1

Explanation For first query,we will swap 1 with 5 and 2 with 4. Now the array becomes- 5 4 3 2 1

Similarly now ,for the second query we will swap 4 with 2 and 3 with itself. So the final array will be 5 2 3 4 1

My Program goes like this:

import java.util.Scanner;
public class ProfessorAndOps {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner in=new Scanner(System.in);
    int n=in.nextInt();//length of array
    int a[]=new int[n];//array declaration
    for(int i=0;i<n;i++){
        //inputting array elements
        a[i]=in.nextInt();
    }
    int q=in.nextInt();//number of queries
    for(int i=0;i<q;i++){
        int l=in.nextInt();//left limit
        int r=in.nextInt();//right limit
        //swapping while iterating over the given range of array elements:
        for(int j=l-1;j<=r-1;j++){
            int temp=a[j];
            a[j]=a[n-j-1];
            a[n-j-1]=temp;
            }
        }
    //Printing the output array:
    for(int i=0;i<n;i++){
        if(i!=n-1){
        System.out.print(a[i]+" ");
        }
        else{
            System.out.println(a[i]);
        }

    }

}
}

I could only come up with BruteForce solution. I'm pretty sure there will be some pre-processing step or some optimisation technique with l and r variables, whatever I could think of, giving me wrong answer. Please help me optimise this code. To be specific, I would need my code's time complexity to be reduced from O(N+ Q*(R-L)) to something like O(Q+N)

Answer 1

Here's an O(Q + N) time, O(N) space algorithm. Imagine a list of the corresponding swap counts only for L and R over the elements (we'll use a negative number for the R counts). What if we maintained a virtual stack while traversing it? (By "virtual," I mean it's not a real stack, just an integer that bears some theoretical similarity.)

For example:

1  2  3  4  5  6  7  8  9  10

O(Q) processing:

q [1,3]
1  9  8  7  5 ...  <- what would happen to the array
0  1  0 -1  0 <- counts (what we actually store)

q [2,4]
1  9  3  4  6 ...  <- what would happen to the array
0  1  1 -1 -1 <- counts (what we actually store)

O(N) traversal:

index 0 didn't move,                     no change, stack: 0
index 1 moved once,          odd count,  changed,   stack: 1
index 2 moved 2 (stack + 1), even count, no change, stack: 2
index 3 moved 2 (stack),     even count, no change, stack: 2 - 1
index 4 moved 1 (stack),     odd count,  changed,   stack: 1 - 1