Title: Given an array of indicies to splice, generate the order in which each element was removed
Tags: algorithm
Question: This is part of a larger program, but this is the bottleneck.
Given an array of numbers that mean &quot;repeatedly splice the element at this index out of an array&quot;, I want to generate an array that represents the order in which each element should be spliced.
So the following:
[3, 1, 4, 4, 3, 1, 1]
means to run these operations:
[a, b, c, d, e, f, g]
[a, b, d, e, f, g]    // 3rd element removed, c
[b, d, e, f, g]       // 1st element removed, a
[b, d, e, g]          // 4th element removed, f
[b, d, e]             // 4th element removed, g
[b, d]                // 3rd element removed, e
[d]                   // 1st element removed, b
[]                    // 1st element removed, d
And I want to generate (without actually running all of the splice operations above):
[2, 6, 1, 7, 5, 3, 4]
which is the order in which each element was removed.
Looking for a solution better than O(N^2)
Below is not part of the question, just what I'm actually doing, for anyone interested:
This is part of a seam carving implementation.  I'm generating a compressed format that represents all of the seams in a given image, and then removing those seams in the client.  Since a seam always moves 1px left or right at each step, a seam can efficiently be stored as:
starting index, left, right, left, left, left, right, ...
I then remove this seam from the image, and calculate the next one.  Storage wise it's 2 bytes + 1 bit per pixel after that, or a seam of length 1024 is stored in 130 bytes.
With respect to the original indicies, however, &quot;left 1&quot; and &quot;right 1&quot; is only accurate for the first seam.  After that any seam can cross over another seam, so &quot;right 1&quot;, with respect to the original indicies, could mean move right 10, or even move left 10.
In other words I'm just trying to decompress this data.
Comment: I don't understand your example output. How does the column, `c, a, f, g, e, b, d`, correspond with `[2, 6, 1, 7, 5, 3, 4]`? It seems to me that it would correspond with `[3, 1, 6, 7, 5, 2, 4]`.

Comment: Do you need the implementation to be in JavaScript or could it be done server-side?

Comment: @DavidEisenstat -- The code here is JS, as it's running in a browser.  It's a bit hard to fully explain what's going on, as the example here is just a minified version of the problem.  The indicies are stored as (in a binary format): `[123, -1, -1, 1, -1, -1, ...]`, which translated to `[123, 122, 121, 122, 121, 120, ...]`.  This is one "seam".  Then the first index of each seam creates the array that I'm talking about in my question (the `[3, 1, 4, 4, 3, 1, 1]` array) for the first row of pixels.  The 2nd index of each seam creates another array for the 2nd row of pixels, etc etc.

Comment: On the server I have a rust script that generates the compressed format.  JS needs to decompress it, but I'm really looking for an algorithm here, not a JS implementation.

Comment: @Socowi - 1) correct  2) Allowing straight seams yields no visual difference from my testing and the files are 40% larger, so I chose to discard them.  I have all of this working, the only issue is that the decompression step takes about 10 seconds at the moment because I'm literally running `.splice()` 1,000,000 times.  Once it's decompressed I can seam carve images as fast as I can drag them :)  Basically I'm generating an array that is the priority to remove each pixel in each row.  So if I want to rescale a 1000px image to 900px I just run through and filter any values < 100

Comment: Your final goal is interesting. I'd like to know more about it. **(1)** Did I understand this correctly: The compressed seams `3 left left` and `2 right right` should be uncompressed to `3 2 1` and (after the first seam was carved) `2 4 5`? **(2)** Why can the seams only go left and right? Why is a straight vertical seam not possible?


Here is another answer: make 2 new arrays.  Index_old is the same size as your original array, and number it consecutively
index_new starts out empty.  loop through your array with numbers, removing that element from index_old and adding it to the end of index_new
index_old[1,2,3,4,5,6,7]
index_new[]
//3rd element removed
index_old[1,2,4,5,6,7]
index_new[3]
//1st element removed
index_old[2,4,5,6,7]
index_new[3,1]
//4th element removed
index_old[2,4,5,7]
index_new[3,1,6]
//4th element removed
index_old[2,4,5]
index_new[3,1,6,7]
//3rd element removed
index_old[2,4]
index_new[3,1,6,7,5]
//1st element removed
index_old[4]
index_new[3,1,6,7,5,2]
//1st element removed
index_old[]
index_new[3,1,6,7,5,2,4]
then create an index final array of the same size and loop
for i= 1 to 7
final[index_new[i]] = i
as it iterates, the loop will populate the final like this
[0,0,0,0,0,0,0]
[0,0,1,0,0,0,0]
[2,0,1,0,0,0,0]
[2,0,1,0,0,3,0]
[2,0,1,0,0,3,4]
[2,0,1,0,5,3,4]
[2,6,1,0,5,3,4]
[2,6,1,7,5,3,4]
Comment for this answer: Yeah, the problem with this is that it's ***slow***, as splicing an array is O(N) so the whole things is O(N^2)

Here is another answer: The simplest O(N log N)-time implementation would probably  be with a Fenwick tree. C++ implementation below.
#include <iostream&gt;
#include <vector&gt;
int NextPowerOfTwo(int n) {
n |= n &gt;&gt; 1;
n |= n &gt;&gt; 2;
n |= n &gt;&gt; 4;
n |= n &gt;&gt; 8;
return n + 1;
class FenwickTree {
public:
explicit FenwickTree(const int n) : sums_(NextPowerOfTwo(n)) {}
void Add(int index, const int delta) {
while (index < sums_.size()) {
sums_[index] += delta;
index += index &amp; -index;
int RankQuery(int target) const {
int index = 0;
for (int stride = sums_.size() &gt;&gt; 1; stride &gt; 0; stride &gt;&gt;= 1) {
if (sums_[index + stride] < target) {
target -= sums_[index + stride];
index += stride;
}
return index + 1;
private:
st75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0vector<int&gt; sums_;
st75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0vector<int&gt; Decompress(const st75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0vector<int&gt;&amp; splice_indices) {
const int n = splice_indices.size();
FenwickTree tree(n);
for (int i = 1; i <= n; i++) tree.Add(i, 1);
st75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0vector<int&gt; result(n);
for (int i = 1; i <= n; i++) {
const int j = tree.RankQuery(splice_indices[i - 1]);
tree.Add(j, -1);
result[j - 1] = i;
return result;
int main() {
for (int i : Decompress({3, 1, 4, 4, 3, 1, 1})) st75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0cout << ' ' << i;
st75b5:f2c1:f5d7:b954:8dc3:cee9:baf:a8c0cout << '\n';
Comment for this answer: This is also O(n log n) worst (individual) case, right?
Comment for this answer: @גלעדברקן indeed.

{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 2, 'CommentCount': 6, 'ContentLicense': 'CC BY-SA 4.0', 'CreationDate': '2021:00:09/26/21', 'FavoriteCount': 5.0, 'PostTypeId': 1, 'Tags': '<algorithm>', 'Title': 'Given an array of indicies to splice, generate the order in which each element was removed', 'ViewCount': 130, 'id': 69334750, 'user_AboutMe': None, 'user_AccountId': 22864172.0, 'user_DisplayName': 'Mark Kahn', 'user_Reputation': 61.0, 'user_Views': 2.0, 'user_id': 17007787.0}}