How can I optimize my code to replace array elements of a given range of indices with an associated element?

Question

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

For each i, where 1≤i≤N there is 1> 1 relationship between the element i and the element Ni + 1

The task is to perform the following operations on this array:

Given two integers (L, R), we must swap each element in this range with its related element. (See example below)

Input example

5 1 2 3 4 5 2 1 2 2 3 

Output example

 5 2 3 4 1 

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

Similarly, now for the second request we will change 4 from 2 and 3 with ourselves. So the last array will be 5 2 3 4 1

My program is as follows:

 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[nj-1]; a[nj-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 a BruteForce solution. I am sure that there will be some kind of preprocessing step or some optimization method with the variables l and r, no matter what I think, giving me the wrong answer. Please help me optimize this code. To be specific, I would need my code time complexity to be reduced from O (N + Q * (RL)) to something like O (Q + N)

Answer 1

Here O(Q + N) time, O(N) spatial algorithm. Provide a list of the corresponding swap values ​​only for L and R by element (we will use a negative number to calculate R ). What if we support the virtual stack while it passes? (By "virtual", I mean that this is not a real stack, but an integer that has some theoretical similarities.)

For instance:

 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