mikuya707 - 1 year ago 50

Javascript Question

Giving an array, say [4,2,1,3,5], based on this array, we have a new array, which each number shows the count of elements on its left that are bigger than itself, which is [0,1,2,1,0]. Now write a function with given input of [0,1,2,1,0], return the original array. The range of array is 1 ~ n (n is the size of the array, you can assume all numbers in the original array are consecutive if sorted)

Now to recover the original array, I have tried a way to solve the problem by iterating through the range of array from the end to the front like this:

*My approach*:

say the range is 1 ~ 5, the original array would be [1, 2, 3, 4, 5] if sorted. Iterate from the end to the beg,

so first 5, there is no element can be bigger than 5, so its maximum count of bigger elements would be 0, then 4 would have 1 as its maximum count of bigger elements, 3 to 2, etc. Store the key-value pairs into an object.

Now iterating through the input from back to front,

- 0 -> 5
- 1 -> can be 4, 3, or 2
- 2 -> can be either 3, 2, or 1
- 1 -> any number bigger than the first one.
- 0 -> (can be anything, since 5 is taken, so it can be either 1, 2, 3, or 4)

Simply to map each element of the input as value to its key from the map is not enough. What would be an intuitive way to approach this with optimal performance? (avoiding O(n ^2) if possible.)

Answer Source

Initially make an AVL Tree from numbers 1 to n.

Start from rear i.e. at nth index (considering 1 based index).

Now the high level outline level of the algorithm should look like this:

```
1. At any ith index, say the number in array(not the originial array) is j
2. Search the number which is at (i-j)th position in your AVL tree(This can be done in O(logn) time. Comment if you need more explanation on this)
3. The element in the AVL tree is your required element. Delete that element from AVL tree.(O(logn))
```

So the total complexity would be O(nlogn).

**Walkthrough**

Initially the tree will contain all 5 elements.

You start at index 5(1-based indexing). Element is 0, i.e. i=5, j=0. So 5th largest element which is 5.

Now the tree contains four elements 1,2, 3, and 4. i=4, j=1. So 4-1 i..e 3rd largest element which is 3 in this case.

i=3, j=2. (3-2)rd largest element is 1 since the tree contains (1, 2, 4).

And so on.

**Using Tree to find the ith largest number**

We can do this by, storing the count of number of nodes in left subtree at the root node. So consider a tree, having elements 1, 2, 3,4 and 5 and tree structure as following:

```
4(3)
/ \
3(1) 5(0)
/ \
1(0) 2(0)
```

At root, number 4 is the value and the number in round bracket has the number of nodes in left subtree.

While constructing(insertion and deletion too) the tree, we can maintain the count.

Now, to find the ith node, say we want suppose 3rd nodes in the given tree. We start with the root, it says it has 3 elements smaller than it to the left so we move to left. Now the root i.e. 3 has 1 smaller left element which is less than 3(ith element) so we move to right of it. Subtract 1(the left count)+1(the root itself) out of 3. Now the root is 2 we want 1st element, the left count is 0. Hence the 1st element of the subtree rooted at 2 is 2.

Basic pseudocode is below:

```
while(true){
count = root->leftCount;
if((count+1)<i){
//move to right
i-=(count+1);
root = root->right;
}
else if(i==(count+1)){
//root is the ith node
break;
} else{
//move to the levft
root=root->left
}
}
```