dhiren.bhuyan
BAN USER@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.
- dhiren.bhuyan August 05, 2013Though 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)
Correct approach..
After looking at your solution, I found that people have provided the same solution in above posts but instead of writing the logic they just copied a bunch of code...thats why perhaps I saw your solution before looking at theirs..
1. Create an array of n elements, lets call it level[ ]
2. Find the root element index with value -1from node [ ], search(O(n))
3. Set the value of that index in level [ ] to 0
4. Traverse through the node [ ], for each index(lets say index 0), find its parent index value(parent index is 3, index 3's value in level[ ] is 0 and set the value in level[ ] to parent index value (here 0 ) + 1 = 1 This is also O(n)
e.g node[ ] = { 3, 3, 3, 3, -1, 2, 1, 0}
level[ ] = {1, 1, 1, 0, 2, 2, 2}
max value in level [ ] will be the height of the tree. find max is also o(n)
I am not sure if this is the approach, or I could explain my logic properly, any clarifications...welcome
- dhiren.bhuyan November 08, 2013This works in nlog(smaller array.length) time, where n is the position of the number we are trying to find
If someone could find any bug then welcome... :-)
a[] = { 1, 3, 4, 8 , 10}
b[] = {20, 22, 30 ,40}
1. create an array index[b.length] )sizeof the smaller array, value 0 for each element
2. index array will contain current index of array a, for each element of array b
3. Create a min heap of size b.length, to get the current min
4. insert sum of a[0] + b[i] into the min heap (20 + 1, 22 + 1, 30 + 1, 40 + 1)
5. Now until we get the nth element, do the following
6. extract the current min (in this case 20+1)
7. increament the corresponding index pointer in this case index of 20 will be increamented to 1 from 0
8. insert this new element in to the heap (in this case 20 + 3 will be inserted into the heap)
//so next time the comparision will be between 20 + 3, 22 + 1, 30 + 1, 40 + 1
9. one thing we need to take care of, like for the below case
a[] = {1,2,3,4,5}
b[] = {20, 60, 80, 100}
if index of an element exceeds the limit like in the above case, 20+1, 20+2, 20+3, 20+4, 20+5 and then it exceeds so insert INT_MAX into the heap,
so that the pointer of 20 will never get increamented again.
We can take care of the duplicate sum like 20+3, 22+1 case through this logic also, by maintaining a prev min and current extracted min.