Hi i have following problem

You are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex

A: 3 2 1

B: 0 1 1

It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them

Ouput should be.

3 1 2

My approach

1.Sort persons according to their frequency(no. of taller person).

2.Now fix the position of each person in appropriate position.

for example:

3 1 2 4

0 2 1 0

after sorting

3 4 2 1

0 0 1 2

now we see that first and second person are at right place so we move third person to it’s right position that is 2nd(base index 1) as he has only one taller before him.

3 2 4 1

0 1 0 2

now for 4th person we just place it at 3rd position

3 2 1 4

0 1 2 0

final answer.

I think it has O(n^2) complexity.Can we do better, and what about correctness of this algorithm?