How to efficiently map to original indices of an array after modification?

This is a simplified version of the problem.

We have an array of numbers (between 0 and X-1), at each round, we choose a range of numbers that we compare and only promote the biggest one and eliminate the rest. At each round, we need to output the original indices of the numbers that have been eliminated.

This is best explained using an example:

Here is the input:

8 // X represents the size of the array, 2 ≤ X ≤ 100000
4 // Y represents the number of elimination rounds 1 ≤ Y ≤ X−1
1 0 3 6 2 4 7 5 // the numbers
1 3
2 4
1 3
0 1

Output: 4 lines, the original index of the losers at each round

1 2
4 5
3 7
0

Here is a diagram of how the output was obtained, [] means the numbers inside the brackets are the ones being compared.

1 [0 3 6] 2 4 7 5 // output 1 2 because 0 and 3 were eliminated
1 6 [2 4 7] 5 // output 4 5 because 4 and 2 were eliminated
1 [6 7 5] // output 3 7 because 7 and 5 were eliminated
[1 7] // output 0 because 1 was eliminated
7

The basic idea is that we want to output the original indices of the number eliminated at each round.

Approach:

Model each number as a pair, with the second entry representing the original index. So we have the following:

          1     2
[(1,0),(0,1),(3,2),(6,3),(2,4),(4,5),(7,6),(5,7)]
       -----------------
                4     5
[(1,0),(6,3),(2,4),(4,5),(7,6),(5,7)]
             -----------------
          3           7
[(1,0),(6,3),(7,6),(5,7)]
       -----------------
    0
[(1,0),(7,6)]
 -----------

[(7,6)]

Is this a promising approach? What is the best way to complement it efficiently?

Is there a better, more efficient approach that is easier to implement?

Another approach uses a segment tree but I don’t understand how that would work.

Is it possible for a number to repeat in array?

Also, did you try keeping a Boolean array to keep track of numbers eliminated?

Meaning, instead of using dynamic arrays like queue, stack etc. Use a regular array, and add a condition “if this number isn’t eliminated, include it for the match (until we reach the upper limit)” and likewise perform operations.

Should roughly look like this-

(Assume j and k are upper and lower indices inputted by user)

int count=0;
for(I=0;i< n,count< n;i++)
{
if(eliminated[I]!=0)
  count++;
}//skipped the elements at first which weren't to be included in match. Meaning, now the next element has to be included in match.
for(;I< n,count<=k;i++)
{
if(eliminated[I]!=0)
{
  ....//consider this element for match, You can store it somewhere in some vector or queue etc.
  count++; 
}
}
for(int l=0;l<= j-k;l++)
{
...//perform operations as required.
if(stack[I]!=max) //max stores the winner of that round
eliminated[I]=0
}

This way you shouldn’t have problem with indexing, but again, the problem isn’t given so I cant promise how easy it would be to implement. Some problems, its easy to implement this approach, but sometimes it gets messy.

Can u please share the link of question? As it is getting hard to get the real question of that!

1 Like

I cannot find the original question myself. But based on what is given, can you please assist me?

The problem above is exactly the same as the original problem without the flavor text, the input and output given are correct. I am just struggling to think of an efficient approach that is less than O(N^2).

Can the array contain same elements?

No, everything is unique.

Also, the input numbers are unique between 0 and X-1, X being the number of numbers.