## Google Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

This is a nice solution...

I am thinking of slightly simplifying it as below.

a) Each node when it enters has its "value" (Number of people greater in height) as its initial value. I am calling it the "current node" (till it reaches its final position).

b) A "current node" goes "left" to the existing node, when its value is <= the existing node's value. At that time it increments the existing node's value by 1.

When the "current node" goes "right", no change to any values.

Repeat for all nodes. Nodes to be pushed in decreasing order of height. Finally do in-order traversal.

The changes from the previous solution are no "right" rule & no +1 for the current node.

With this, the following will be the iterations...

a) 6 = 0

b) 5 = 0, 6 = 1

c) 4 = 0, 5 = 1, 6 = 2.

d) 4 = 0, 5 = 1, 3 = 2, 6 = 3.

e) 4 = 0, 5 = 1, 2 = 2, 3 = 3, 6 = 4.

f) 4 = 0, 5 = 1, 2 = 2, 3 = 3, 1 = 4, 6 = 5.

The "intuition" is - In each iteration, an element is inserted at the same position as its "value".

Though I like the idea of sorting using the comparator as mentioned above by amitb2108 but below is the approach that came to my mind first.

lets say height[] = {3,1,2,4}

pos[] = {0,2,1,0}; //no of persons greater height than him

1. create an array of person struct of size n and fill the data from the above two arrays

struct person

{

int height;

int num;

};

2. Sort the person array with height as the key in decreasing order. o(nlgn)

index 0,1,2,3

person[] = {4,3,2,1}

{0,0,1,2} //person.num

3. Remember the index of array represents the no of persons greater in front of the current index. e.g. person with height 3 has array index 1, so 1 person is in front of him with greater height. But we need to have 0 no of person greater than 3, so swap it with index 0.

person[] = {3,4,2,1} //after swapping 3

//2 has only one person in front but index of 2 is 2 currently there are 2 persons

//swap it with index 1

person[] = {3,2,4,1}

//1 has only 2 persons in front but index of 1 is 3, so currently there are 3 persons

//swap it with index 2

person[] = {3,2,1,4}

the idea is, previous index, has a person with greater height than current index. The previous index person's position is already set. Now if we move this previous index person towards right it doesn't impact the position of this person. e.g. person with height 4, if we move this person towards the right, still the no of persons with greater height will be 0.

Total complexity = o(nlogn)

I don't think your solution is O(nlogn).For instance:

4321

0011

as your idea

step 1:

3421

step 2:

3241

step 3:

It should be 3124.

Then I realize that it shouldn't be swap. It's insert.

Just insert person.height to arr[person.num] is ok.

The insertion complexity = o(n^2)

Anyway, thanks for your idea!

@dmxmails: The complexity can be further reduced if you use a clever data structure that supports fast insertion at an arbitrary position.

This can be achieved using a modified skiplist (expected insertion time O(logN)) or a modified balanced binary tree for which we store the in each node the number of nodes in the subtree rooted at that node (worst case insertion time: O(logN)).

So, the final complexity of the algorithm would be O(N*log(N)).

@dmxmails - in step 3, why it should be 3124? In 3124, 1 has only one person in front with greater height. But as per the input height[] = {3,1,2,4} pos[] = {0,2,1,0}, 1 should have 2 persons with greater height in front.

If I understand correctly, you are swapping every element a with the element b in left holding a's actual position. But I guess just swapping will not work.you have to insert it in its proper position by shifting all elements from b to a.

try this example

9 9 8 7 5 4 3 2

0 0 0 3 0 5 1 7

```
C++ SOLUTION
bool compare(pair<int, int>& a, pair<int, int>& b)
{
return a.first>b.first;
}
void swap(vector<pair<int, int>>& inp, int start, int count)
{
while (count--)
{
pair<int, int> temp = inp[start];
inp[start] = inp[start - 1];
inp[start - 1] = temp;
start = start - 1;
}
}
vector<int> arrangement(vector<int> &A, vector<int> &B, int n)
{
vector<pair<int, int>> inp;
for (int i = 0; i < n; i++)
{
inp.push_back(std::make_pair(A[i], B[i]));
}
std::sort(inp.begin(), inp.end(), compare);
for (int i = 0; i < n; i++)
{
if (inp[i].second != i)
{
swap(inp, i, (i - inp[i].second));
}
}
vector<int> res;
for (auto&x : inp)
{
res.push_back(x.first);// << " ";
}
return res;
}
```

You can sort the list of persons (person: height,numTallBeforePerson) using the following comparator:

```
class Comparison implements Comparator<Person>{
@Override
public int compare(final Person p1, final Person p2){
if (p1.numTallBeforePerson == p2.numTallBeforePerson){
if (p1.height < p2.height) {
return -1;
}
else{
return 1;
}
}
else if (p1.numTallBeforePerson < p2.numTallBeforePerson) {
if (p1.height < p2.height)
return -1;
}
else if (p1.numTallBeforePerson > p2.numTallBeforePerson) {
if (p1.height > p2.height)
return 1;
}
return -1;
}
}
```

The idea is that a shorter person standing after a taller one will have larger number of tall people before him than the taller person. Time complexity: O(n log n)

I don't think this problem can be solved in O(n log n). To indicate the bug in the above solution consider the following example. Assume people have heights from 1 to 20. Assume person with height 3 has rank 10 and person with height 5 has rank 9.

Then just by looking at 3 and 5 and their rankings you cannot conclude whether 3 is in front of 5 or 5 is in front of 3. It depends on where other elements are located. (You can actually construct two different examples where 3 is in front of 5 in one example and the other way around in the second example)

In two sequences below 5 and 3 have the same corresponding number in array B but their order is different. So the idea above is not correct (front of the array is the right side)

12435

12534

>> You can sort the list of persons (person: height,numTallBeforePerson)

Does this mean persons[i] = new Person(heights[i], count[i])? If it is the case, the solution is incorrect.

The simplest counter example:

Input:

A: [1, 2]

B: [0, 1]

The expected output should be:

[2, 1]

However, the solution outputs [1, 2]

Backtrack.

Let's say the first array is height array and the second is count array. Sort the count array from low to high (say [0,1,1]). Start from the first height 3 (corresponding to count 0), the root node of the backtrack tree is (3), then insert the second height 2, generating one child node (3,2). Then insert the third height 1, generating one child node (3,1,2). If a node does not generate any child node, then it is an dead end. In this case, backtrack to the upper level node to visit its next child node.

This way you can find all possible sequences satisfying the two arrays. And you can confidently know if there is no such sequence at all.

sort the person by the height

if the count is not zero, swap the person on the right who is higher until the count become zero

time: O(n^2)

example 1

235461

020004

sort

123456

402000

swap 1

234516

020000

swap 3

245316

000000

example 2

3 1 2 4

0 2 1 0

sort

1 2 3 4

2 1 0 0

swap 1

2 3 1 4

1 0 0 0

swap 2

3 2 1 4

0 0 0 0

My algorithm: Time -- O (N LOG N) & Space --O(N) .. please let me know your comments... it seems to work for all cases, let me know if I am missing something...

Approach:

(1) Sort the input in descending order of size -- O(N LOG N)

(2) Use a stack based approach -- O(N) : (find below)

Given:

A[] = {1,2,3,4,5}

b[]= {3,1,1,1,0}

Step 1: Sort A (and hence B) --> A[] = {5,4,3,2,1} B= {0,1,1,1,3} // Here, this is still O(N.LOG N)

Step 2: Stack based algorithm (Say have 2 stacks: S1->stack.new, S2->stack.new)

```
for index in a:
if (s1.isEmpty())
s1.push(a[index])
continue
while(s1.size > b[index])
s2.push(s1.pop())
s1.push(a[index])
while(! s2.isEmpty()) s1.push(s2.pop())
```

Isn't the question incorrect: if the heights are 3,2,1 in some height-units, shouldn't the array be 0,1,2 - representing no one in front of 3, 1 guy in front of 2 and 2 guys in front of 1. Or maybe i am missing something that rest everyone is not - pls enlighten

The second array doesn't just indicate how many guys are standing in front of a particular guy, but specifically the number guys standing in front who are of *greater height*. So, even though guy of height 2 has two guys in front of him, there's only 1 guy in front of him of greater height.

I found that the max element is at the rightmost position(call pos) whose value is zero in the array b, so everytime I insert the max element of the remaining elements, and all the elements on the right of pos in b should decrement by one, because one max element is eliminated on the left, and carry on untill no elements left in a, and here is my code:(O(n^2), I think my algorithm supports duplicate heights)

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
//time complexity is n^2
void rank( int a[], int b[], int n )
{
std::vector<int> c( n, -1 );
std::sort( a, a+n, std::greater<int>() );
int j;
for( int i = 0; i < n; ++i )
{
j = n - 1;
for( ; j >= 0; --j )
if( b[j] == 0 && c[j] == -1 ) break;
for( int k = j + 1; k < n; ++k ) --b[k];
c[j] = a[i];
}
for( int i = 0; i < n; ++i ) std::cout << c[i] << " ";
std::cout << std::endl;
}
int main( int argc, char* argv[] )
{
/*int a[] = { 3, 2, 1 };
int b[] = { 0, 1, 1 };
int n = 3;*/
int a[] = { 7, 4, 5, 9, 8, 1, 4, 3 };
int b[] = { 0, 0, 2, 2, 2, 4, 2, 2 };
int n = 8;
rank( a, b, n );
return 0;
}
```

How about next idea.

The last element of second array - let call it array of inversions in following, is always that we have in desc order. For example.

3 2 1. 2

0 1 1 - is element with index 1 in desc order. so it must be placed the in that way:

* * 2

0 1 *

so 1 - is element with 1 index in desc order without 2. it must be placed there

* 1 2

and following

3 1 2

We process array from right to left. element i must be placed with element from first array without already processed element in desc order.

Use an order stastisc tree:

- Insert all the heights into an order statistic tree

- for i from B.length -1 to 0:

- what is the B[i] order statistic value in the order statistic tree

- remove that value from the tree and insert it into the results array at i

Time is nlogn (n queries for order statistics)

Space is n (order statistic tree size)

Another O(n logn) time and O(n) space solution. Please correct me if there are issues.

```
package heighttallinfront;
import java.util.LinkedList;
import java.util.Collections;
import java.util.Comparator;
public class Main {
/**
* Data structure to hold the necessary values
*/
private static class PersonData {
int height, tallPersonsInFront;
public PersonData(int height, int tallPersonsInFront) {
this.height = height;
this.tallPersonsInFront = tallPersonsInFront;
}
public String toString() {
return "[" + height + ", " + tallPersonsInFront + "]";
}
}
/**
* O(n) for building the data structure that holds both height and number of taller persons ahead of him
* @param heights
* @param tallPersonsInFront
* @return
*/
private static LinkedList<PersonData> buildPersonDataList(int[] heights, int[] tallPersonsInFront) {
final LinkedList<PersonData> personDataList = new LinkedList<PersonData>();
for (int i = 0; i < heights.length; i++) {
personDataList.add(new PersonData(heights[i], tallPersonsInFront[i]));
}
return personDataList;
}
/**
* O(n logn) Sorting of Java (merge sort)
* @param personDataList
*/
private static void sortPersonDataListByHeight(final LinkedList<PersonData> personDataList) {
Collections.sort(personDataList, new Comparator<PersonData>() {
@Override
public int compare(PersonData p1, PersonData p2) {
// If the heights are the same
// The one with the less taller persons in front of him should be come before the other
// Since the person behind should have at least the same number of taller persons in front of him
if (p1.height == p2.height) {
return p1.tallPersonsInFront - p2.tallPersonsInFront;
}
return p1.height - p2.height;
}
});
}
/**
* O(n) since it visits all the nodes from right to left (inserting each element into their "appropriate" places)
* The idea is to move each person to the right by the number of taller persons in front of him.
* Remember that the list is currently sorted in increasing order so moving each person to the right means you're
* moving at the back of a person taller than you.
* @param personDataList
*/
private static void sortPersonDataListByTallPersonsInFront(final LinkedList<PersonData> personDataList) {
final int personDataListSize = personDataList.size();
for (int i = personDataListSize - 1; i >= 0; i--) {
PersonData p = personDataList.get(i);
insertNode(personDataList, i, i + p.tallPersonsInFront + 1);
}
}
/**
* Assume O(1) since it's a linked list
* @param personDataList
* @param a
* @param b
*/
private static void insertNode(final LinkedList<PersonData> personDataList, int a, int b) {
PersonData person = personDataList.get(a);
personDataList.add(b, person);
personDataList.remove(a);
}
/**
* O(n) to rearrange the two arrays
* @param personDataList
* @param heights
* @param tallPersonsInFront
*/
private static void buildArrangedHeightsAndTallPersonsInFront(final LinkedList<PersonData> personDataList, int[] heights, int[] tallPersonsInFront) {
for (int i = 0; i < heights.length; i++) {
final PersonData p = personDataList.get(i);
heights[i] = p.height;
tallPersonsInFront[i] = p.tallPersonsInFront;
}
}
/**
* O(n logn) given the operations present in this method
* Actual is O(n (logn + 3))
* @param heights
* @param tallPersonsInFront
*/
public static void sortInput(int[] heights, int[] tallPersonsInFront) {
if (heights == null || tallPersonsInFront == null || heights.length != tallPersonsInFront.length) {
System.out.println("Invalid input.");
} else if (heights.length == 0) {
System.out.println("No person in line.");
} else if (heights.length == 1) {
System.out.println("Only one person in line.");
}
final LinkedList<PersonData> personDataList = buildPersonDataList(heights, tallPersonsInFront); // O(n)
sortPersonDataListByHeight(personDataList); // O(n logn)
sortPersonDataListByTallPersonsInFront(personDataList); // O(n)
buildArrangedHeightsAndTallPersonsInFront(personDataList, heights, tallPersonsInFront); // O(n)
}
public static void main(String[] args) {
int[] heights = new int[] { 3, 2, 1, 1 };
int[] tallPersonsInFront = new int[] { 0, 1, 2, 1};
sortInput(heights, tallPersonsInFront);
printArray(heights);
printArray(tallPersonsInFront);
}
public static void printArray(int[] input) {
printArray(input, 0, input.length - 1);
}
public static void printArray(int[] input, int start, int end) {
for (int i = start; i <= end; i++) {
System.out.print("+--+");
}
System.out.println();
for (int i = start; i <= end; i++) {
System.out.print("|" + String.format("%02d", input[i]) + "|");
}
System.out.println();
for (int i = start; i <= end; i++) {
System.out.print("+--+");
}
System.out.println();
}
}
```

One solution: Every time, select the smallest number with front[] = 0.

e.g. height[] = {3, 1, 2, 4}, front[] = {0, 2, 1, 0}

1) Find the smallest number from height[] that has 0 in front[], in this case it is 3, then 3 is 1st element in the queue.

2) For rest of the elements i in height[], if it is smaller than 3, then front[i] - 1, otherwise keep front[i] the same.

Go back to 1)

This is pretty much like topological sorting; each time remove the node with indegree == 0.

Observe that in any arrangement of heights, the smallest element can have one and only one spot to go.

eg.

{ 3, 1, 2, 4 }

{1, 2, 2, 0}

1 is the smallest element and needs to have 2 elements ahead of it. All other elements are larger, so it must only be able to go into ar[2]. After placing 1 in ar[2], count 2 empty spaces, skip 2 because it's taken and place 2 into ar[3]. 3 needs 1 empty space and goes into ar[1] and 4 into ar[0].

Fail if there are no available spots. Collisions or cases like

{ 3, 1, 2, 4, 1 }

{1, 2, 2, 0, 2}

are handled elegantly by the space counting.

Unoptimized this is O(n^2).

Here is a python code that runs in O(n logn) time. If you use some sorting algorithm, say radix sort, that runs in O(n) time, then this algorithm will take O(n) time.

```
import copy
a = [int(i) for i in raw_input().split(' ')]
b = [int(i) for i in raw_input().split(' ')]
n = len(a)
shift = [0 for i in range(n)]
d = [0 for i in range(n)]
queue = [-1 for i in range(n)]
c = copy.deepcopy(a)
c.sort()
for i in range(n):
temp = c.index(a[i])
d[temp] = b[i]
for i in range(n):
queue[d[i]+shift[d[i]]] = c[i]
shift[d[i]] += 1
print queue
```

Consider line[] array where people have to be placed.

Assumption : all people have distinct height from 0 to N-1. so sort A and hence B array (along with A) in increasing order.

Now A=[0,1,2,3,4...].

So, now we can ignore A[] and only consider B[] ans array where B[i] is = number of people with greater height in front that person of height i.

Now, in line[], 0th person will be at index B[0] since there are exactly B[0] person > than 0th person. For second largest person if B[1] < B[0] 1 ahead of 0th person in line[]. else after 0th person. Eg

if B=[3,2,....] line = [--10-------] - is space to be taken by others. 0th person took 4th free seat. 1st took 3rd free

if B=[3,3,....] line = [---01------] => 0th person took 4th free seat. 1st took 4th free seat, after 0 took its seat. so 1 basically took 5th seat

notice how 1 after 0 in line.

So basically you have a set of free seats and each person comes and takes whatever is left.

So Algo : put 0th person at index B[0] in line[]. remove B[0] index from line[] from free seat list. next for ith person, traverse whatever free spaces are left in line[] from index 0 and place them there.

pseudo code :

```
for(i=0;i<N;i++)
{
c=0;
for(j=0;j<N;j++)
{
if(line[j]==free)
c++;
if(c==B[i])
break; //after skipping B[i] "free" seats in line, make ith height person settle down.
}
line[j]=B[i]; //settle down
}
```

Above is O(N*N)

can be reduced to O(N) is we can find out in O(1) which seat index a person will get currently if he has to skip x seats

O(nlogn) : Consider line as a skip linked list. node has value 0 to N-1. for each person , given x seats to skip - find xth node using bin search on skip list. delete that node. update skip list.

O(nlogn) : See line as a balanced BST. nodes have value of index 0 to N-1. each node also has the value 'number of nodes in this tree' in tree rooted at it.

construct N node such balanced BST in O(N) (yes, find out how this can be constructed in O(N) yourself) (or to simplify , make in O(logn))

Sort A hence B in inc order. Take B[i] for ith smallest person. Delete B[i]th "number" (not value) of node from the tree. this nodes value = persons index in line. Also update 'number of nodes in this tree' for all nodes effected by delete - O(logn) per person. total nlogn.

My take on this

1. we need to arrange the numbers based on the index difference given

{3,2,1}->{0,1,1} means

{3} has none taller in front, {2} has 1 taller, {1} has 1 taller

so {3}>{1}>{2} or (3 greater than 1 greater than 2)

2. {5,4,3,2,1}->{0,0,0,0,0} means

{5} has none taller in front, {4} has none taller in front, {3} has none taller in front, ...

so {1}>{2}>{3}>{4}>{5}

3. {5,4,3,2,1}->{0,1,2,3,4} means

{5}>{4}>{3}>{2}>{1}

4. looking at the options above we can easily build an iteration to move the person to the index on the second array, taken the example {3,2,1}->{0,1,1}, steps are

-move {3} to position 0 - nothing to do

-move {2} to position 1 - nothing to do

-move {1} to position 1 - move {1} to position 1, {2} will need to move 1 position down

algorithm is quite simple

```
public int[] orderTallPerson(int[] heights, int[] tallerThen) {
for (int i=0; i<tallerThen.length; i++) {
if (tallerThen[i] != i) {
int height = heights[i];
int pos = tallerThen[i];
for (int j=i; j>pos; j--) {
//move person height forward to back of queue
heights[j] = heights[j-1];
//move taller index to back of the queue
tallerThen[j] = tallerThen[j-1];
}
heights[pos] = height;
}
}
return heights;
}
```

Below should be true

```
int heights[] = {6,5,4,3,2,1};
int tallerThen[] = {0,0,0,2,2,4};
int result[] = {4,5,2,3,1,6};
int heights[] = { 7, 4, 5, 9, 8, 1, 4, 3 };
int tallerThen[] = { 0, 0, 2, 2, 2, 4, 2, 2 };
int result[] = {4,7,3,4,8,9,1,5};
int heights[] = { 7, 4, 5, 9, 8, 1, 4, 3 };
int tallerThen[] = { 0, 1, 1, 0, 1, 5, 4, 6 };
int result[] = {5,1,9,8,4,3,7,4};
int heights[] = { 5,4,3,2,1 };
int tallerThen[] = { 0,0,0,0,0 };
int result[] = {1,2,3,4,5};
int heights[] = { 5,4,3,2,1 };
int tallerThen[] = { 0,1,2,3,4 };
int result[] = {5,4,3,2,1};
```

My solution is in O(2n)

```
public int follow(int startNumber, Map<Integer, Pair<Boolean, Integer>> pairMap) {
Pair<Boolean, Integer> currentPair = pairMap.get(startNumber);
if (currentPair == null) {
return 0;
} else {
if (currentPair.getFirst()) {
return currentPair.getSecond();
} else {
currentPair.setFirst(true);
int result = follow(startNumber + 1, pairMap) + 1;
currentPair.setSecond(result);
return result;
}
}
}
public void q1() {
int[] ints = {7,6,5,4,2,3,1};
// first integer , in the pair first is vis9ted, second is the score
Map<Integer, Pair<Boolean, Integer>> pairMap = new HashMap<Integer, Pair<Boolean, Integer>>();
for (Integer i : ints) {
pairMap.put(i, new Pair<Boolean, Integer>(false, 1));
}
int[] results = new int[ints.length];
for (int i = 0; i < ints.length; i++) {
int result = follow(ints[i], pairMap);
results[i] = result;
System.out.println(ints[i] +":"+result);
}
}
```

```
class person {
int h;
int r;
public person(int h1, int r1) {
h = h1;
r = r1;
}
public int getH() { return h;}
public int getR() { return r;}
}
public static void arrangHeight(int height[], int rank[]) {
ArrayList <person> p = new ArrayList <person> ();
int i;
int n = height.length;
for(i = 0; i < n; i++) {
person p1 = new person(height[i], rank[i]);
p.add(p1);
}
Collections.sort(p, new comparator() {
public int compare(person p1, person p2) {
return p2.getH - p1.getH;
}
});
// height[] = {3,1,2,4}
// pos[] = {0,2,1,0}
// op -> [4, 3, 2, 1]
// op [0, 0, 1, 2]
ArrayList <Integer> out = new ArrayList<Integer>();
out.add(p.get(0).getH());
for (i = 1; i < n; i++) {
person p1 = p.get(i);
int pos = p1.getR();
out.add(pos, p1.getH());
}
System.out.println(out);
}
```

O(n^2)

1. sort persons by height and num greater before

2. find place for each person (from short to high)

```
class Person{
public int Height;
public int Greater;
public static bool operator > (Person p1, Person p2){
return p1.Height > p2.Height || p1.Height == p2.Height && p1.Greater > p2.Greater;
}
public static bool operator < (Person p1, Person p2){
return p1.Height < p2.Height || p1.Height == p2.Height && p1.Greater < p2.Greater;
}
public static bool operator == (Person p1, Person p2){
return p1.Height == p2.Height && p1.Greater == p2.Greater;
}
}
int[] HeightSort(int[] heights, int[] greaters){
if(heights == null || greaters == null || heights.Length != greaters.Length){
return null;
}
int len = heights.Length;
Person[] ps = new Person[len];
for(int i = 0; i < len; ++i){
ps[i] = new Person{Height = heights[i], Greater = greaters[i]};
}
QuickSort(ps);
int[] ret = new int[len];
for(int i = 0; i < len; ++i){ret[i] = -1;}
for(int i = 0; i < len; ++i){
int j = 0;
for(int idx = 0; idx < len; ++idx){
if(j == ps[i].Greater){
break;
}
if(ret[idx] == -1){
++j;
}
}
if(idx == len){
return null;
}
ret[idx] = ps[i].Height;
}
return ret;
}
```

O(n^2)

1. sort persons by height and num greater before

2. find place for each person (from short to high)

```
class Person{
public int Height;
public int Greater;
public static bool operator > (Person p1, Person p2){
return p1.Height > p2.Height || p1.Height == p2.Height && p1.Greater > p2.Greater;
}
public static bool operator < (Person p1, Person p2){
return p1.Height < p2.Height || p1.Height == p2.Height && p1.Greater < p2.Greater;
}
public static bool operator == (Person p1, Person p2){
return p1.Height == p2.Height && p1.Greater == p2.Greater;
}
}
int[] HeightSort(int[] heights, int[] greaters){
if(heights == null || greaters == null || heights.Length != greaters.Length){
return null;
}
int len = heights.Length;
Person[] ps = new Person[len];
for(int i = 0; i < len; ++i){
ps[i] = new Person{Height = heights[i], Greater = greaters[i]};
}
QuickSort(ps);
int[] ret = new int[len];
for(int i = 0; i < len; ++i){ret[i] = -1;}
for(int i = 0; i < len; ++i){
int j = 0;
for(int idx = 0; idx < len; ++idx){
if(j == ps[i].Greater){
break;
}
if(ret[idx] == -1){
++j;
}
}
if(idx == len){
return null;
}
ret[idx] = ps[i].Height;
}
return ret;
}
```

I think an elegant solution to this problem would be to sort the array of heights and also put array B in that order O(nlogn)

Make another array of size n as our position array.

Then get the element of the smallest height and see how many people are in front of him and place him into the index of that our position array.

Keep taking the next smallest element with x people in front of him. Start from the beginning of the array and count x non filled spaces in the array and place it there.

This is because the non filled spaces in the array will have height greater than that of our element while the filled spaces will have height less than our element so we can ignore those elements.

So our overall complexity is O(nlogn)

With checking each element of the array if it has filled or not for all n elements would take O(n^2). could someone think of a way to make checking filled spaces O(logn)?

checking every position in the new array will make the algorithm O(n^2).

we can find the correct position of every person in O(logn)

create a c++ set 's' (balanced BST) from the number 0 to n-1.

A number in the s denotes that this position is currently vacant in the final queue.

for every person taken in non-decreasing order of height, if cnt is the number of people which should be taller than him, then this person should be placed at index=lower_bound of cnt in the set.

This would denote the earliest position in queue such that we can accommodate cnt person before him, now delete this index from the set.

total O(nlogn)

I have a very simple O(nlogn) solution I'm finding difficult to explain

Calculate a prefix big enough so that it's bigger than every other number

prefix = pow(10, ciel(log10(n)) + 1))

now create an array where each cell's value is

height + prefix * number_heigher_infront

Now, sort the new array ascending and remove from each number (prefix * number_heigher_infront)

Voila!

My solution in C++. The list of (Heights, Count of people in front) is sorted based on the height. Then each person is added - in order - at the position given by the count of people in front of him. We maintain a "jump" table at each step in order to jump over position occupied by a smaller person. The algorithm time complexity is O(n log n). Reviews are welcome :

```
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Person {
int height;
int count;
bool operator<(const Person other) const {
return (height < other.height);
}
};
vector<int> arrange(vector<int> Heights, vector<int> Counts) {
vector<int> arranged(Heights.size(), -1);
vector<int> jump(Heights.size(), -1);
vector<Person> Persons;
for (int i = 0; i < Heights.size(); ++i) {
Persons.push_back((Person){Heights[i], Counts[i]});
}
sort(Persons.begin(), Persons.end());
int pos;
for (vector<Person>::iterator it = Persons.begin(); it != Persons.end(); ++it) {
pos = (jump[it->count] == -1) ? it->count : jump[it->count];
arranged[pos] = it->height;
jump[it->count] = (jump[pos + 1] == -1) ? pos + 1 : jump[pos + 1];
}
return arranged;
}
int main(int argc, char** argv) {
vector<int> Heights;
Heights.push_back(3);
Heights.push_back(2);
Heights.push_back(1);
vector<int> Counts;
Counts.push_back(0);
Counts.push_back(1);
Counts.push_back(1);
vector<int> arranged = arrange(Heights, Counts);
for (vector<int>::iterator it = arranged.begin(); it != arranged.end(); ++it) {
cout << *it << endl;
}
return 0;
}
```

There is a bug in my previous answer in the way the jump list is maintained. Here is a better solution using a binary search tree to maintain the available positions set (I used a C++ set<int> which relies on a BST). This solution has O(n log n) time complexity.

```
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
struct Person {
int height;
int count;
bool operator<(const Person other) const {
return (height < other.height);
}
};
vector<int> arrange(vector<int> Heights, vector<int> Counts) {
vector<int> arranged(Heights.size(), -1);
vector<Person> Persons;
set<int> availableSlots;
for (int i = 0; i < Heights.size(); ++i) {
Persons.push_back((Person){Heights[i], Counts[i]});
availableSlots.insert(i);
}
sort(Persons.begin(), Persons.end());
set<int>::iterator pos;
for (vector<Person>::iterator it = Persons.begin(); it != Persons.end(); ++it) {
pos = availableSlots.lower_bound(it->count);
arranged[*pos] = it->height;
availableSlots.erase(pos);
}
return arranged;
}
int main(int argc, char** argv) {
vector<int> Heights;
Heights.push_back(3);
Heights.push_back(2);
Heights.push_back(1);
vector<int> Counts;
Counts.push_back(0);
Counts.push_back(1);
Counts.push_back(1);
vector<int> arranged = arrange(Heights, Counts);
for (vector<int>::iterator it = arranged.begin(); it != arranged.end(); ++it) {
cout << *it << endl;
}
return 0;
}
```

for the case

vector<int> Heights;

Heights.push_back(6);

Heights.push_back(1);

Heights.push_back(11);

Heights.push_back(5);

Heights.push_back(10);

Heights.push_back(4);

vector<int> Counts;

Counts.push_back(2);

Counts.push_back(4);

Counts.push_back(0);

Counts.push_back(1);

Counts.push_back(0);

Counts.push_back(0);

your ans return 4,5,6,10,1,11; but the right answer is 4,10,5,11,1,6.

I solved it by recursive form.

These are persudo code.

```
vector<int> answer;
sort(A.begin(), A.end())
void sol( list<int> A, list<int> B) {
if( A.empty() == true ) return;
int cnt = count_number_of_0(B);
answer.push_back(A[A.length()-cnt]);
A.erease(A.length()-cnt);
B.pop_front;
for( x in B ) if(x>0) x--;
}
```

solution:

create a binary tree using following steps:

consider second array the one with no of peoples having more height as a priority for the first array..

now move one by one in array 1 and insert elements like this

1.if priority is greater move to right or less move to left

2.if priority is same move to right if height is greater else move left

3.balance the tree

O(nlogn) .......

inorder is the answer...

I'm using LinkedList for the this. Sort the tallCount[] in ascending order and accordingly re-position the items in heights[]. This is capable of handling the duplicate elements also.

```
public class FindHeightOrder {
public int[] findOrder(final int[] heights, final int[] tallCount) {
if (heights == null || heights.length == 0 || tallCount == null
|| tallCount.length == 0 || tallCount.length != heights.length) {
return null;
}
LinkedList list = new LinkedList();
list.insertAtStart(heights[0]);
for (int i = 1; i < heights.length; i++) {
if (tallCount[i] == 0) {
Link temp = list.getHead();
while (temp != null && temp.getData() <= heights[i]) {
temp = temp.getLink();
}
if (temp != null) {
if (temp.getData() <= heights[i]) {
list.insertAfterElement(temp.getData(), heights[i]);
} else {
list.insertAtStart(heights[i]);
}
} else {
list.insertAtEnd(heights[i]);
}
} else {
Link temp = list.getHead();
int pos = tallCount[i];
while (temp != null
&& (temp.getData() <= heights[i] || pos-- > 0)) {
temp = temp.getLink();
}
if (temp != null) {
if (temp.getData() <= heights[i]) {
list.insertAfterElement(temp.getData(), heights[i]);
} else {
list.insertBeforeElement(temp.getData(), heights[i]);
}
} else {
list.insertAtEnd(heights[i]);
}
}
}
Link fin = list.getHead();
int i = 0;
while (fin != null) {
heights[i++] = fin.getData();
fin = fin.getLink();
}
return heights;
}
public class Link {
private int data;
private Link link;
public Link(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Link getLink() {
return link;
}
public void setLink(Link link) {
this.link = link;
}
@Override
public String toString() {
return this.data + " -> "
+ (this.link != null ? this.link : "null");
}
}
public class LinkedList {
private Link head;
public Link getHead() {
return head;
}
public void insertAtStart(int data) {
if (head == null) {
head = new Link(data);
head.setLink(null);
} else {
Link link = new Link(data);
link.setLink(head);
head = link;
}
}
public void insertAtEnd(int data) {
if (head != null) {
Link temp = head;
while (temp != null && temp.getLink() != null) {
temp = temp.getLink();
}
temp.setLink(new Link(data));
} else {
head = new Link(data);
}
}
public void insertAfterElement(int after, int data) {
if (head != null) {
Link temp = head;
while (temp != null) {
if (temp.getData() == after) {
Link link = new Link(data);
link.setLink(temp.getLink());
temp.setLink(link);
break;
} else {
temp = temp.getLink();
}
}
}
}
public void insertBeforeElement(int before, int data) {
if (head != null) {
Link current = head;
Link previous = null;
Link ins = new Link(data);
while (current != null) {
if (current.getData() == before) {
ins.setLink(current);
break;
} else {
previous = current;
current = current.getLink();
if (current != null && current.getData() == before) {
previous.setLink(ins);
ins.setLink(current);
break;
}
}
}
}
}
@Override
public String toString() {
return "LinkedList [head=" + this.head + "]";
}
}
}
```

1) sort the (height, #number of greater values in front) pair by using height as a key

This can be done by using std::map

let this map be map1

2) have an empty sorted list1 with the #number of greater and the height as lexical key

for (auto &pair: map1) {

list1.insert(pair.second, pair.first);

}

3) list1 is the result.

If B = [0, 0, 0, ..., 0, 0], then the output should be a sorted list. From there, we can think of each element of B as a derangement of that sorted order. Going from right to left (highest to lowest) over B, every element of b is, by definition, the number of greater numbers that come before the element in the same position in the result list R. So we take the B[i]-th greatest element from A (that is, A[B[i]], where A is sorted) and place it in R[i], then *remove it from A*.

Here's the program:

```
def reorder(a, b):
a.sort()
r = []
for i in b[::-1]:
r.append(a[-i])
del a[-i]
return r
def main():
a = [3, 2, 1]
b = [0, 1, 1]
print reorder(a, b)
if __name__ == "__main__":
main()
```

Here is my simple solution.

Requires sorting then traversing the list of persons once.

1) Sort persons by multiple indexes : First index is height, second index is their B value (how many taller people are standing in front of them)

2) Traverse that sorted list in reversed order. If a person's B value is b > 0 ,

shift the person's position in the list b steps to the right (i.e. towards the taller people's direction).

Python code:

```
def sort_people(A, B):
sorted_persons = sorted(zip(A, B))
for idx, person in reversed(list(enumerate(sorted_persons))):
if person[1] > 0:
sorted_persons.pop(idx)
sorted_persons.insert(idx + person[1], person)
return zip(*sorted_persons)[0]
print sort_people([3, 2, 1], [0, 1, 1])
```

list pop() and insert() are O(n), so this solution is probably O(n²)

This is my code and this code can be used in any amount of integers in an array

public class class2 {

public static void main(String args[]){

int arr1[]={3,5,1,6,7};

int arr2[]={0,1,1,2,3};

for(int i=0;i<arr1.length;i++){

for(int j=i+1;j<arr1.length;j++){

if(arr1[i]<arr1[j]){

int n=0;

n=arr1[i];

arr1[i]=arr1[j];

arr1[j]=n;

}

}

}

int arr3[]=new int[arr1.length];

int k=1;

while(k<=arr3.length){

arr3[arr3.length-k]=arr1[arr2[arr3.length-k]];

arr1[arr2[arr3.length-k]]=0;

for(int i=0;i<arr1.length;i++){

if(arr1[i]==0){

for(int j=i;j<arr1.length-1;j++){

arr1[j]=arr1[j+1];

}

arr1[arr1.length-k]=0;

break;

}

}

k++;

}

for(int s=0;s<arr3.length;s++){

System.out.println(arr3[s]);

}

}

}

I get a O(N^3) algorithm. The idea is just search all possible arrangements, upon number of taller violation, backtrack.

```
public class PersonNode {
int height;
int numTaller;
public SearchNode(int h, int n) {
this.height = h;
this.numTaller = n;
}
}
public List<PersonNode> arrangePerson(List<PersonNode> unarranged) {
List<PersonNode> result = new ArrayList();
if(doArrange(result, unarranged)) {
return result;
} else {
return null;
}
}
private boolean doArrange(List<PersonNode> arranged, List<PersonNode> unarranged) {
if(unarranged.isEmpty()) {
return true;
}
if(!checkOrderViolation(arranged)) {
return false;
}
for(PersonNode p: arranged) {
List<PersonNode> attemptArranged = Arrays.copy(arranged);
attempArranged.append(p);
List<PersonNode> attemptUnarranged = Arrays.copy(unarranged);
attemptUnarranged.remove(p);
if(doArrange(attempArranged, attemptUnarranged)) {
arranged = attempArranged;
unarranged = attemptUnarranged;
return true;
}
}
return false;
}
// O(n^2)
private boolean checkOrderViolation(List<PersonNode> persons) {
for(int i = 0; i < persons.size(); i++) {
PersonNode p = persons.get(i);
int height = p.height;
int numActuallTaller = 0;
for(int j = 0; j < i; j ++) {
if(persons.get(j).height > height) numActuallTaller++;
}
if (numActuallTaller != p.numTaller) return false;
}
return true;
}
```

int main (int arc, char * argv[])

{

int arrHeight[] = {3,2,1};

int arrKeyGiven[] = {0, 1, 1};

int i, j, temp = 0, length = 0;

length = 3;//4;

/** LOGIC FOR RESETING THE POSITION ACCORING TO THE KEY GIVEN

if Current position < keyPostion then

: do one swap with teh previous one :)

else

: do one swap with the next one :)

**/

for (i = 0; i < length; i++)

{

if ( arrKeyGiven[i] < i)

{

temp = arrHeight[i];

arrHeight[i] = arrHeight[i-1];

arrHeight[i-1] = temp;

}

}

printf("REPOSITIONED ARRAY IS \n");

for (i = 0; i < length; i ++)

printf("%d\t", arrHeight[i]);

return 0;

}

THIS IS THE MODIFIED LOGIC:----- WORKS WELLL :) please have one try by assigning some logically correct values to arrHeight, and arrKeyGiven and see the result...if any issues plz revert to jitu059@gmail.com

U need to edit, arrHeight/arrKeyGiven and length to test more problems

#################################

int main (int arc, char * argv[])

{

int arrHeight[] = {3,1,2};

int arrKeyGiven[] = {0, 2, 1};

int i, j, temp = 0, length = 0;

length = 3;//4;

/** LOGIC FOR RESETING THE POSITION ACCORING TO THE KEY GIVEN

if keyPosition < Current Position then

: do one swap with teh previous one :)

else if keyPosition > Current Position then

: do one swap with the next one :)

else : DO NOTHING......current position is desired one :)

**/

for (i = 0; i < length; i++)

{

if ( arrKeyGiven[i] < i)

{ printf("Swaping in process\n");

temp = arrHeight[i];

arrHeight[i] = arrHeight[i-1];

arrHeight[i-1] = temp;

}

else if( arrKeyGiven[i] > i)

{

temp = arrHeight[i];

arrHeight[i] = arrHeight[i+1];

arrHeight[i+1] = temp;

}

}

printf("REPOSITIONED ARRAY IS \n");

for (i = 0; i < length; i ++)

printf("%d\t", arrHeight[i]);

return 0;

}

C++

```
int* ArrangePeople(int height[], int front[], int n)
{
for(int i = 0; i < n; i++)
{
int temp = height[i];
for(int j = i; j > front[i]; j--)
{
height[j] = height[j-1];
}
height[front[i]] = temp;
}
for(int i = 0; i < n; i++)
cout<<height[i]<<" ";
return height;
}
int heights[5] ={5,4,3,2,1};
int rank[5] ={0, 1, 0, 1, 2};
ArrangePeople(heights, rank, 5);
output: 3 2 1 5 4
```

This can be solved using rope data structure.

- Anonymous Coward August 06, 2013It's like a binary tree except that each node maintains the number of nodes in the left subtree+1 for itself. Whenever a new number is inserted, if the value is smaller than the node's number it goes to the left otherwise right. When it goes to the right, the value of the node is decreased by the value of the branch node.

Ex Nodes: 6 5 4 3 2 1

values: 0 0 0 2 2 4

1. Make 6 as the root of the tree, its value = 1;

2. Insert 5. Value of 5(0) < value of 6(1) so it goes to the left. New value of 6 = 2, value of 5=1;

3. Insert 4, value of 4 < value of 6 so goes to the left; again goes to the left of 5. New values of 4 = 1, value of 5 = 2, value of 6 = 3

4. Insert 3, goes to the left of 6 but to the right of 5. New values 6 = 4, value of 3 = 1, rest unchanged

5. Insert 2, goes to the left of 6, right of 5 (value of 2 is decreased by value of 5 so its now 0), left of 3. New values of 3 = 2, value of 2 = 1, value of 6 = 5

6. Insert 1, goes to the left of 6, right of 5, right of 3.

Do an in-order traversal of tree. It is imperative to insert the nodes in decreasing order