0
$\begingroup$

Edit: found solution with $O(1)$ look for my answer at here

I have an array of elements, and I wish to reverse the order of elements between indices $i$ and $j$.

Example: Let the array contain elements $A,B,C,D,E,F$. Calling the function reverse(array, 1,4) will modify the array to be $A,E,D,C,B,F$.

I want to do this operation multiple times on different indices. What would be the most efficient way to implement this (precalculations don't count)?

$\endgroup$
  • 1
    $\begingroup$ The size of the array can be assumed to be always constant? (I'm considering to make some pre-computations and to store them in a table) What is the available space for storing pre-computations if any is allowed? $\endgroup$ – Carlos Linares López Oct 27 '13 at 20:50
  • $\begingroup$ I don't quite understand your question. What's wrong with the algorithm given in my answer? $\endgroup$ – Yuval Filmus Oct 28 '13 at 5:18
  • $\begingroup$ Instead of linking to other sites, why not add an answer here? If what you claim is true you need to address the specifics, such as what is the underlying data structure (i.e. how is the array represented?). $\endgroup$ – Juho Nov 1 '13 at 15:15
  • $\begingroup$ @Juho It will be a duplication. I have a source sample and explanations on the other stack exchange site, it is a really great idea $\endgroup$ – Ilya Gazman Nov 1 '13 at 15:38
6
$\begingroup$

Let me restate the problem. We're given an array $A_0$ and a sequence $(\ell_1,r_1),\dots,(\ell_m,r_m)$. Set $A_{i+1}=\text{reverse}(A_i,\ell_i,r_i)$. The goal is to compute the array $A_m$.

The naive way to solve this is to just incrementally apply the reverse operations, i.e., incrementally invoke Yuval's reverse algorithm $m$ times. The running time of the naive solution is $\sum_{i=1}^m (r_i-\ell_i)$. The question is, can we do better?


The answer is, yes, in some cases. It's possible to build a data structure to optimize the sequence of reversal operations, in a way that's faster than the naive solution. With sufficient cleverness, you can get the total running time down to $O(n + m \lg n)$ -- in comparison, the naive algorithm could potentially be as large as $O(nm)$, in the worst case. I'll explain how to do it below.

We can model the desired rearrangement by a permutation $\pi$ on the array indices. Such a permutation acts on arrays: given any array $\pi$ and any permutation $\pi$ on the indices, we can obtain an array $\pi A$, namely, the array $A'$ given by $A'[\pi(j)]=A[j]$. Notice that the operation $\text{reverse}(A,\ell,r)$ should return the array $\pi A$, where $\pi(j)=\ell+r-j$ for $\ell \le j \le r$ and $\pi(j)=j$ for all other $j$. Let $\text{rev}(\ell,j)$ denote this permutation.

This gives us a new strategy for solving the problem: first, compute $\pi = \text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_1,r_1)$; then, compute $A_m = \pi A_0$. The latter step can be done in $O(n)$ time, with no additional space. So, how quickly can we compute $\pi_m$?

Here is one way to compute $\pi_m$. We will represent a permutation $\pi$ as an interval tree, i.e., a binary tree where each leaf has an interval on the indices. The intervals on the leaves will be pairwise disjoint, their union will be $\{1,2,\dots,n\}$, and they will be in sorted order (from left to right). Each internal node will hold an interval representing the union of the intervals on all of its descendants. Also, we'll annotate each leaf with an affine function of the form $f(x)=x+\alpha$ or $f(x)=\alpha-x$. The idea is that if we have a leaf with interval $[a,b]$ and function $f$, then $\pi(j)=f(j)$ for $j=a,a+1,\dots,b$.

In this way, we can represent a permutation as this sort of interval tree. Notice that the identity function can be represented as an interval tree with one leaf, with interval $[1,n]$ and function $f(x)=x$. Also, the permutation $\text{rev}(\ell_m,r_m)$ corresponding to a single reversal operation can be represented as an interval tree with three leaves, namely $[1,\ell_m-1],f(x)=x$, $[\ell_m,r_m],f(x)=\ell_m+r_m-x$, and $[r_m+1,n],f(x)=x$.

Now suppose we have an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$. Let me explain how to derive an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$. Basically, we search the interval tree to find all leaves whose interval overlaps with $[\ell_i,r_i]$, and split them in two pieces if they partially overlap (one piece that doesn't overlap, the other piece containing the rest that is contained within $[\ell_i,r_i]$). Then, for each such leaf that overlaps $[\ell_i,r_i]$, if it currently contains the function $f$, we replace it with the function $g \circ f$, where $g(x)=\ell_i+r_i-x$.

So, we iteratively do this. When we're done, we have an interval tree representation of $\pi$. Now we can compute $\pi A_0$ in linear time. The running time to construct the interval tree is now dependent on the number of intervals that get treated differently. In other words, say that indices $j,j'$ are treated differently if there exists some $i$ such that $j\in [\ell_i,r_i]$ but $j'\notin [\ell_i,r_i]$ (or vice versa); otherwise, say that $j,j'$ are treated the same. Now construct the equivalence classes of the "treated the same" equivalence relation. Each equivalence class is one interval in the final interval tree, so the total running time is related to the total number of such equivalence relations. In particular, if there are $k$ intervals in the final interval tree (i.e., $k$ such equivalence classes), then the running time is $O(mk+n)$.


It's possible to speed this up even further by annotating each internal node with an affine function as well.

The idea is that such an interval tree represents a permutation $\pi$ as follows: if we have a leaf with interval $[a,b]$ and function $f_0$, and its parent has function $f_1$, and its grandparent function $f_2$, and so on up to the function $f_d$ on the root, then for every $j \in [a,b]$, we have $\pi(j) = (f_d \circ \cdots \circ f_1 \circ f_0)(j)$. In other words, the effective function on this leaf is the composition of all of the functions on the path from the leaf to the root.

This tree representation is even better: it allows you to derive the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$ from the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$ in $O(\lg k)$ time, where $k = $ the number of intervals in the tree. Basically, we may have to split at most two intervals (one on the left side, if it partially overlaps $[\ell_i,r_i]$ on the left, and one on the right). Then, we need to compose a function $g(x)=\ell_i+r_i-x$ to all of the leaves whose intervals is contained within $[\ell_i,r_i]$. The latter can be done by identifying $O(\lg k)$ nodes of the tree whose (disjoint) union is $[\ell_i,r_i]$ (by construction you can always find such a set of nodes), and then composing $g$ with the function at each of those nodes: for each such node, if its function was $f$, you update it to $g \circ f$.

Consequently, the total running time of this improved solution is $O(n + m \lg k)$, where $k$ is the number of intervals in the final interval tree. A conservative upper bound is $O(n + m \lg n)$ to perform $m$ reversal operations on an array of size $n$. This is better than the naive algorithm, whose running time could be as bad as $O(nm)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Wow, it looks like you put a lot of effort in to this. Amazing! Can you please explain me some things: Why the native algorithm is $O(nm)$ and not $O(m)$, if I use array list, I can swap to elements in O(1) and I only need $m / 2$ swaps, so why the efficiency is not $O(m)$ or in more generally $O(N)$? $\endgroup$ – Ilya Gazman Oct 29 '13 at 12:09
  • $\begingroup$ This doesn't work. Consider an array $A = [1,2,3]$. Reversing $(1,2)$ yields $A = [2,1,3]$. Then reversing $(2,3)$ yields $[2,4,2]$. $\endgroup$ – S. Pek Mar 9 '17 at 6:44
  • $\begingroup$ @S.Pek, I think you've misunderstood my scheme. You are getting confused between doing arithmetic on the array values vs doing arithmetic on array indices. The functions $f$ in this answer are doing arithmetic on indices. If we reverse $(2,3)$, then we'll have a function $f(x)=2+3-x$ applied to the indices in the range $2..3$. Here $x$ is an index, not an array value. Thus, index $2$ goes to index $f(2)=3$, and index $3$ goes to index $f(3)=2$. That takes array $[2,1,3]$ to array $[2,3,1]$. It's probably easier to see what's happening if you start with $A = [7,8,9]$. $\endgroup$ – D.W. Mar 12 '17 at 2:48
  • $\begingroup$ OK, after the first operation we have $[1,2]$ with $f(x)=3-x$ and $[3]$ with identity. Then $[2,3]$ overlap $[1,2]$ and resulting function on $[2]$ must be $f(x)=5-(3-x)=2+x$. Isn't it? $\endgroup$ – Mr. Newman Dec 4 '17 at 19:22
  • $\begingroup$ Does the [function annotated to the leaf] represent the [image under the composition of permutations for each position in the segment (represented by that leaf)]? If yes, how can we compose the function g to every position in that segment?Because g is to be applied to every position whose image under the composition of permutations is between [L, R], not to the positions that are originally between [L, R]. i.e. g is to be composed with every $\{ i \le n : f(j)=\pi(j) \in [L, R] \}$. But you're applying it to every $\{ i \le n : i \in [L, R] \}$ $\endgroup$ – Siddharth Joshi May 23 at 11:22
5
$\begingroup$

Here is the classical algorithm used to solve the problem:

def reverse(array, i, j):
  if i > j: # ensure i <= j
    i, j = j, i
  while i < j:
    array[i], array[j] = array[j], array[i]
    i += 1
    j -= 1

For example, reverse(array, 1, 4) will swap array[1] and array[4], and then array[2] and array[3]. This algorithm makes the minimal amount of swaps, and is optimal op to a multiplicative constant in any reasonable machine model in which it can be implemented.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why is this better then my solution? $\endgroup$ – Ilya Gazman Oct 28 '13 at 7:11
  • $\begingroup$ @Babibu because it has a precise description and its efficiency can be seen easily. Your suggestion is vague and its complexity hasn't been properly analyzed. $\endgroup$ – David Richerby Oct 28 '13 at 12:15
  • $\begingroup$ @DavidRicherby my solution is better, if it is not clear enough I can explain it why(if you just say what is it you do not understand). But I started my answer when I am mentioning this solution, and even that it is written in very elegant way, this is not what I am looking for. $\endgroup$ – Ilya Gazman Oct 28 '13 at 12:41
  • $\begingroup$ The one thing that this answer doesn't address is, when we want to perform a sequence of many such operations, whether you can do better than just applying each one iteratively. (If you know in advance the sequence of such operations, can we optimize?) $\endgroup$ – D.W. Oct 28 '13 at 15:48
-3
$\begingroup$

Hope this works, the code is self explanatory and is in c#

     private static void ReverseSubArray(ref char[] SourceArray, int i, int j)
    {
        int len = SourceArray.Length;
        if (i > len || j > len)
        {
            Console.WriteLine("Improper Index Supplied !");
            Console.ReadLine();
            return;
        }
        else
        {
            int arrayLen = (j - i) + 1;
            char[] NewArray = new char[arrayLen];
            for (int index = i, localIndex = 0; index <= j; index++, localIndex++)
            {
                NewArray[localIndex] = SourceArray[index];
            }
            Array.Reverse(NewArray);
            for (int index = i, localIndex = 0; index <= j; index++, localIndex++)
            {
                SourceArray[index] = NewArray[localIndex];
            }
            Console.WriteLine("Task Done !");
            return;
        }
    }
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ This just duplicates Yuval's answer, except that you use working space proportional to the number of elements to be flipped (his uses constant working space) and you use a library function to do the actual reversing. $\endgroup$ – David Richerby Oct 28 '13 at 12:00
  • $\begingroup$ Please read and understand other answers before suggesting your own. $\endgroup$ – Ilya Gazman Oct 28 '13 at 12:08
  • $\begingroup$ @DavidRicherby sir, this never means one should vote it down, anyhow it serves the question. $\endgroup$ – manish Oct 28 '13 at 12:10
  • 1
    $\begingroup$ @Manish Please don't take it personally. The purpose of voting is to separate good answers from bad. Yuval's answer works efficiently in any programming language; your answer does the same thing but less efficiently and only works in C#, since it needs that library function. $\endgroup$ – David Richerby Oct 28 '13 at 12:27
  • $\begingroup$ np sir, that's fine, thanks anyways for your corrective measures $\endgroup$ – manish Oct 28 '13 at 12:38
-5
$\begingroup$

A trivial solution will be $O(N)$, just swapping all the necessary indexes. A batter solution for small number of operations in compare to $N$ will be as fallow:

For every operation when you want to reverse the array in between the indexes $i,j$, create a rule as fallow: when iterating over the array, when you will rich index $i$, jump to index j and read in reverse until you will rich index $i$ again, then jump to index $j + 1$. Store this rule on rules array with size of $N$ at index $i$. And in future iterations read the rules array simultaneity.

This algorithm will work only for the first time, and will be brake when you will have operation that modifying your index with a rule. To prevent that happening create a red-black tree, and store then rules indexes inside it, for each operation search the tree to see if there are any rules in between the indexes you are modifying, if there are, change them to feet the new operation.

If the number of rules is very small in compare to $N$, then the efficiency is $O(1)$, if not but the number of rules between $j,i$ is very small in compare to $N$ then the efficiency is $O(Log(N))$, if not then the efficiency is $O(NLog(N))$

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ This description is far too vague to be useful. What happens if several overlapping segments of the array are reversed? What is the complexity of look-up in this system? $\endgroup$ – David Richerby Oct 27 '13 at 19:58
  • $\begingroup$ I am using red-black tree to search for them, because the number of the elements in the tree is small it is $O(1)$, and in worst case $O(NLogN)$ but this is not realistic scenario. $\endgroup$ – Ilya Gazman Oct 28 '13 at 8:04
  • 4
    $\begingroup$ Exactly what is stored in the red-black tree? Exactly how is it updated when another subarray is inverted? Exactly what is the complexity of this? Exactly how do you look up elements in the modified array? Exactly what is the complexity of that? $\endgroup$ – David Richerby Oct 28 '13 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.