Is there any fastest approach to reverse the range of elements in an array consisting of two types of elements?

Question

I have an array, let say:
2, 3, 3, 2, 3, 3, 3, 2

(the array consists of two unique integers, repeated)

Given L and R (denotes the range within the array).
Is there any fastest approach to reverse the elements of array in range L to R?
currently, I am doing it in O(n).

For above example, if L=2 and R=5, the new array will be,
2, 3, 2, 3, 3, 3, 3, 2

I went through this solution: Reversing an array Query

But wanted to whether there is any other approach apart from decorated splay trees ?

Answer 1

I don't think that there is faster way (due to swap operation) but you can use another data structure.

The idea here I guess is to use kind of double-linked list with operation go through which would pass the list by visiting

• next sibling if the next is not before
• before sibling if the next is before

in a pseudo-code something like:

class Node
{
    Node before, next;
}

void goThrough(Node root, Node currentNode)
{
     //some actions here

     if( root.next != null || root.next != currentNode )
     {
         goThrough( root.next );
     }

     if( root.before != null )
     {
         goThrough( root.before );
     }
}

then the reversing range would be just about changing next/before fields at the start and end of range - which actually makes O(1)