patternMinor
Recover an array from its insertion indices
Viewed 0 times
indicesinsertionarrayrecoveritsfrom
Problem
An array is built starting with an empty array, and then a sequence of insertions:
and so on. When we insert element $a_i$ and index $z_i$ the result is that $a_i$ is now at index $z_i$, whereas everything before index $z_i$ is unchanged and everything after has its index increased by 1. (With one-based indexing) E.g., the sequence
$(3,1), (5,2), (1,2)$ gives $[3]$ then $[3,5]$ then $[3,1,5]$. All of the instructions will make sense, i.e., $1 \leq z_i\leq i$.
My question is about how to calculate the final array. The naive approach would be to start with an empty array, and literally obey the instructions; but in the language I program, insertions have a worst case time complexity of $O(\# $elements shifted$)$; if, for example, all the insertion indices were $1$, this would result in $O(N^2)$ time.
Supposing we have access to all the instructions simultaneously, how can we calculate the final array in faster than $O(N^2)$ time? I would be happy with a name if this problem is well studied. I did make the following (family of) observations:
... and so on.
However I can't think of the algorithms or data structures tha
- insert $a_1$ at index $z_1=1$
- insert $a_2$ at index $z_2$
- insert $a_3$ at index $z_3$
- ...
and so on. When we insert element $a_i$ and index $z_i$ the result is that $a_i$ is now at index $z_i$, whereas everything before index $z_i$ is unchanged and everything after has its index increased by 1. (With one-based indexing) E.g., the sequence
$(3,1), (5,2), (1,2)$ gives $[3]$ then $[3,5]$ then $[3,1,5]$. All of the instructions will make sense, i.e., $1 \leq z_i\leq i$.
My question is about how to calculate the final array. The naive approach would be to start with an empty array, and literally obey the instructions; but in the language I program, insertions have a worst case time complexity of $O(\# $elements shifted$)$; if, for example, all the insertion indices were $1$, this would result in $O(N^2)$ time.
Supposing we have access to all the instructions simultaneously, how can we calculate the final array in faster than $O(N^2)$ time? I would be happy with a name if this problem is well studied. I did make the following (family of) observations:
- the element which ends up at index 1 was the last one which arrived with index 1.
- the element which ends up at index 2 arrived with index 1 or 2. If it arrived with index 2, then none came after it with either index 1 or 2. If it arrived with index 1, then exactly one came after it with index 1, after which came none with index 2.
- the element which ends up at index 3 arrived with index 1, 2, or 3. If it arrived with index 3, then none came after it with index 1, 2 or 3. If it arrived with index 2, then exactly one element with index 1 or 2 followed it, then none after that with index 1, 2, or 3. If it arrived with index 1, then it was followed by one with index 1, then one with index 1 or 2, and then none after that with index 1, 2, or 3.
... and so on.
However I can't think of the algorithms or data structures tha
Solution
Prelimiaries
You can augment an AVL tree to support all the usual operations plus the following:
Shift$(a,b)$ increases all keys $k \ge a$ by $b \ge 0$ in $O(\log n)$ time (where $n$ is the number of elements in the tree).
To do so add a value $x_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$. The Search, Insert, and Shift operations, along with the required rotations can be implemented as follows (I won't be using the Delete operation, but it can also be implemented).
Search
The search operation work as usual except that you now keep track of the cumulative offset in the path from the current node to the root.
Insert
To insert a node with key $k$, use the search operation to find the position where a node with key $k$ would need to be placed and the cumulative offset $\overline{x}$ up to that point. Add a leaf in that position and store its key as $k - \overline{x}$. Perform the necessary rotations to rebalance the tree (see the sequel).
Rotations To perform a right rotation on $u$ let $v$ be its left child.
"Push down" the offset of $u$ as follows: increment the stored key of $u$ by $x_u$, add $x_u$ to the offsets of the children of $u$, and set $x_u$ to $0$. Similarly, "push down" the offset of $v$. Perform the rotation as usual. Left rotations are symmetric.
Shift$(a,b)$. Find the node $u$ with key $a$ or, if no such node exists, find its successor (if the successor doesn't exist either, we are done). Increase the stored key of $u$ by $b$. If $u$ has a right child $v$ then increase $x_v$ by $b$ as well. Walk from $u$ to the root of the tree. Every time you walk to a vertex $w$ from its left child, increase the key of $w$ by $b$ and the offset $x_z$ of the right child $z$ of $w$ by $b$ (if $z$ exists).
Solving your problem
Keep an augmented AVL tree $T$ and consider the operations one at a time. At the end of the generic $i$-th step, the tree will contain $i$ nodes that collectively store the elements of the first $i$ operations.
Each node $u$ is associated with one element of the array. The key of $u$ is exactly the position of $u$'s element in the array, as of the $i$-th operation, while the element's value is stored as satellite data in $u$.
When the operation $(a_i, z_i)$ is to be processed do a Shift$(z_i, 1)$ operation on $T$. Then, insert a new node with key $z_i$ and satellite data $a_i$ in $T$.
At the end of the process you can traverse the tree and recover the final position (the node's key) of each array element (the node's satellite data).
The total time required is $O(n \log n)$.
You can augment an AVL tree to support all the usual operations plus the following:
Shift$(a,b)$ increases all keys $k \ge a$ by $b \ge 0$ in $O(\log n)$ time (where $n$ is the number of elements in the tree).
To do so add a value $x_v$ to each node $v$ in the tree. This value represents an offset to be added to all keys stored in the subtree rooted at $v$. The Search, Insert, and Shift operations, along with the required rotations can be implemented as follows (I won't be using the Delete operation, but it can also be implemented).
Search
The search operation work as usual except that you now keep track of the cumulative offset in the path from the current node to the root.
Insert
To insert a node with key $k$, use the search operation to find the position where a node with key $k$ would need to be placed and the cumulative offset $\overline{x}$ up to that point. Add a leaf in that position and store its key as $k - \overline{x}$. Perform the necessary rotations to rebalance the tree (see the sequel).
Rotations To perform a right rotation on $u$ let $v$ be its left child.
"Push down" the offset of $u$ as follows: increment the stored key of $u$ by $x_u$, add $x_u$ to the offsets of the children of $u$, and set $x_u$ to $0$. Similarly, "push down" the offset of $v$. Perform the rotation as usual. Left rotations are symmetric.
Shift$(a,b)$. Find the node $u$ with key $a$ or, if no such node exists, find its successor (if the successor doesn't exist either, we are done). Increase the stored key of $u$ by $b$. If $u$ has a right child $v$ then increase $x_v$ by $b$ as well. Walk from $u$ to the root of the tree. Every time you walk to a vertex $w$ from its left child, increase the key of $w$ by $b$ and the offset $x_z$ of the right child $z$ of $w$ by $b$ (if $z$ exists).
Solving your problem
Keep an augmented AVL tree $T$ and consider the operations one at a time. At the end of the generic $i$-th step, the tree will contain $i$ nodes that collectively store the elements of the first $i$ operations.
Each node $u$ is associated with one element of the array. The key of $u$ is exactly the position of $u$'s element in the array, as of the $i$-th operation, while the element's value is stored as satellite data in $u$.
When the operation $(a_i, z_i)$ is to be processed do a Shift$(z_i, 1)$ operation on $T$. Then, insert a new node with key $z_i$ and satellite data $a_i$ in $T$.
At the end of the process you can traverse the tree and recover the final position (the node's key) of each array element (the node's satellite data).
The total time required is $O(n \log n)$.
Context
StackExchange Computer Science Q#116897, answer score: 4
Revisions (0)
No revisions yet.