CODEWITHSUNDEEP
c++arraysalgorithmdata-structures
Cheeku
Cheeku

Reputation: 873

Data structure to handle array with changing indices

I have an array with space for say 8 elements. I want to fill this array with numbers 8,7,...,1 at indices indicated by the following array:

7 4 4 2 1 2 0 0

You must've notices that some indices are repeating. This is so because these numbers indicate indices for the remaining array.

I will guide you through the steps of array filling so you get the idea :

Initial Array(with indices)

_ _ _ _ _ _ _ _
0 1 2 3 4 5 6 7

Step 1

_ _ _ _ _ _ _ 8
0 1 2 3 4 5 6 -

Step 2

_ _ _ _ 7 _ _ 8
0 1 2 3 - 4 5 -

Notice how the indices got updated as I filled in "7", so that I can fill "6" at index 4 too, as index 4 is a new position.

Step 3

_ _ _ _ 7 6 _ 8
0 1 2 3 - - 4 -

Step 4

_ _ 5 _ 7 6 _ 8
0 1 - 2 - - 3 -

Step 5

_ 4 5 _ 7 6 _ 8
0 - - 1 - - 2 -

Step 6

_ 4 5 _ 7 6 3 8
0 - - 1 - - - -

Step 7

2 4 5 _ 7 6 3 8
- - - 0 - - - -

and "1" can be filled at the last place.

I have solved the problem directly scanning the array for the ith empty place if I have to fill at index i. It is O(n^2). I need better.

Question: Is there a data structure that can optimize the above algorithm? Or can the algorithm itself be improved?

NOTE: I have tried using BIT, but failed.

Upvotes: 1

Views: 312

Answers (2)

user3072164
user3072164

Reputation:

Store all initial indices in a binary search tree. Also store along with each node the number of total children (all deeper levels).

As soon as you inserted one element in the array, remove its index from the tree in O(log n). At the same time update the child counts.

For the next insert in the array at index i in "new indices" you need to find the ith element in ordering of the search tree which will give you the position in "original" indices. Since the number of childs at each node can be queried, this can be done in O(log n) as well.

So the full average- and worst-case complexity is O(n log n).

Upvotes: 2

3yakuya
3yakuya

Reputation: 2662

If you accept to use additional O(n) memory you may do this:

  • Create a helper array, which at index i stores the index of i'th free place in the original data array. So, if your original array have indexes 0 - 7 and places indexed 1, 3, 5 are free, then your helper array would look like: [1, 3, 5, -1, -1, -1, -1, -1], where -1 indicates there is no such amount of free space in the original array.

  • In order to insert an element at i'th free position in the data array you do this:

    int j = helperArray[i];
    if (j > -1){
        dataArray[j] = itemYouWantToInsert;
        while (i < helperArray.size() - 1){
              helperArray[i] = helperArray[i+1];
              i++;
          }
          helperArray[i] = -1;
    }
    else
        cout<<"There are less free places in the dataArray.";

The insertion time is O(k) then, where k = (n - i). So pesimistic time of insertion is O(n), but optimistic one is O(1). isFree() is just an example method, as I do not know how do you recogize "empty space" in the dataArray.

Upvotes: 1

Related Questions