Queue Reconstruction by Height | Leetcode

This video explains a very important programming interview problem which is to reconstruct a given queue based on height and rank parameters.This is a very good hybrid sorting and searching problem.We need to sort the array using a comparator function which sorts based on both height and rank.After sorting, we need to place all the persons starting from least height to their correct position and queue which results in the proper answer queue reconstructed from the given input queue.I have explained the intuition and approach using examples and at the end of the video,i have also shown the code walkthrough. CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
=================================================================
INSTAGRAM: / surya.pratap.k
LinkedIn: / surya-pratap-kahar-47b...
=================================================================
CODE LINK: gist.github.co...
OTHER PROBLEM:-
Implement Queue using Stack (with Example): • Implement Queue using ...
Candy distribution problem: • Candy distribution pro...

[@rishabhkumar8115]

Time: O(n^2) it enough for the interview but we can also solve it in O(nlogn) by using binary indexed tree.

[@codingwithanonymous890]

how?

[@ashishm8850]

Excellent explanation. It's a pity I did not discover your channel sooner!

[@techdose4u]

Thanks

[@thiyagarajanr225]

Solving a problem needs a great idea not only programming skills . A great approach to a problem + Programming skills caring about time and space complexities makes us happy people !!! You showed in every aspect bro!!

[@techdose4u]

Thanks bro :)

[@yitingg7942]

It's very hard to grasp this concept.. I am just not smart enough. sigh...

[@techdose4u]

Even after watching the video ?

[@yitingg7942]

@@techdose4u Yes Sir, for some reason today is extremely hard.

[@techdose4u]

@@yitingg7942 then let me know in msg. I will help you :)

[@ГеоргийМай-т3в]

Unfortunately I gave up on my own decision :( thank you for great explanation. It seems equal-height elements we can sort in descending order (for k value), so that while insertion in new array people with equal height won't meet each other so lines 26-33 can look just a little bit more simple: if (ans[j][0] == -1) { if (count == 0) { ans[j] = people[i]; break; } else --count; }

[@techdose4u]

Welcome

[@sahilchoudhary1473]

sir your content is amazing and easy to learn cloud you please make videos on leetcode weekly and Biweekly contests this will help us a lot to learn more

[@techdose4u]

Bro I am busy with this leetcode contest. I want to quickly get this over with 😅

[@gauravmasand]

Ok better optimal solution class Solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: people = sorted(people, key=lambda x: (-x[0], x[1])) ans = [] for person in people: ans.insert(person[1], person) return ans Try this with O(N log N) time complexity and easy to do in cpp also try it by ur self

[@ashishchoksi8501]

insted of this for simplicty of code we traverse array from end and use arr.insert(arr.begin()+pos[i], height[i]);

[@shwetanksingh5438]

I wait for your editorials to get deep insight.

[@techdose4u]

Nice :)

[@praveenchouhan6388]

even same case with me, excellent workkkk!!!!!!

[@kSERITIKGupta]

Can anyone explain why this condition was added *else if(ans[j][0]==-1 || ans[j][0]>=people[i][0]) count-=1;*

[@PurpleDaemon_]

Thanks for the explanation! But I must warn the rest of the viewers, that there is a much more optimal and compact solution with sorting in descending order and a simple push (insert in Python or a linked list in Java).

[@harinaaraayans3453]

nice explanation .. we can solve it with the same time complexity by starting from the tallest persons first and using a linked list

[@techdose4u]

Yes correct :)

[@MrKB_SSJ2]

I LITERALLY TRIED THE SAME APPROACH DAMMIT BUT YET GOT INCORRECT ANSWERS.

[@akshatjain6854]

Bro make a video on Minimum Swaps To Make Sequences Increasing

[@techdose4u]

This month I am busy with leetcode discussions bro.

[@akshatjain6854]

@@techdose4u This leetcode 30 days challenge will keep on coming. But pls make a video on some very imp problems

[@spetsnaz_2]

you can check this one : www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/ or www.geeksforgeeks.org/minimum-number-of-swaps-required-to-sort-an-array-set-2/?ref=rp

[@indraalapati989]

Java solution - public int[][] reconstructQueue(int[][] people) { /* Step1 - sort people based on heights in descending order, if heights are equal sort on basis of position in ascending order. Step2 - after sorting, arrange people at output index based on their position */ Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]); List list = new ArrayList(); for(int[]p : people){ list.add(p[1], p); } int n = people.length; return list.toArray(new int[n][2]); }

[@techdose4u]

👍

[@Safar_Ayushi_Ka]

How can I improve the concepts on time and space complexities? Let me know plz

[@techdose4u]

Please solve MCQ questions on time and space or else read some codes and try to figure out the time and space and then see the editorial answer. This way you will learn. Follow geeks. They have time and space mentioned for each code at the end.

[@Safar_Ayushi_Ka]

@@techdose4u thanks

[@akshatjain6854]

was waiting for your video

[@techdose4u]

👍 Solved already?

[@akshatjain6854]

@@techdose4u No it was kind of hard, I sorted it and didn't get what to do next

[@techdose4u]

Okay...now you do :)

[@kishankumargupta4200]

​@@techdose4u Even if I solve the problem, I come to watch your videos for optimized version or new approach. Your approach to solve the problems are very helpful. Keep making videos :)

[@techdose4u]

Thanks bro :)

[@nishantsharma3100]

i solved this one using new array . by placing the smallent the smallest first and then placing the second smallest and so on . worked fast too.

[@techdose4u]

Yes. This is the same approach given in hint and I explained it too :)

[@namanjain9094]

@@techdose4u Bro you should always post the optimized approach as by this approach interviewer will not be happy and will ask to optimized it and then what we will do ..... so you should always post optimized approach (in this case using segment tree) and thus not make fool of students following you. Hope you take this seriously as this is serious because there would be absolutely no gain In seeing your approach as the interviewer will definitely want an optimized approach and we would be stuck there. So please consider this seriously.

[@thunderbolt8632]

Absolutely love your work sir!👍 Btw do you work at FAANG?

[@techdose4u]

No

[@thunderbolt8632]

@@techdose4u Oh got u,SAMS😅

[@techdose4u]

🤣

[@willturner3440]

@@techdose4u but you have good knowledge of dsa

[@AbhishekKumar-gg6ox]

How did you you understood the goal of the question ??There was nothing mentioned in the problem statement.

[@techdose4u]

If you read the question repeatedly with given example then you can figure it out. I also tried some inputs and saw the expected output. That's another technique on leetcode.

[@Learner010]

sorry , to say but i don't get it fully with reasons of why! maybe more illustration is good for this kind of problem.

[@techdose4u]

I explained it well enough. You should try to rewatch it attentively. Actually we are sorting because when we are processing from shortest height and we are putting elements at correct position. While doing so, we are skipping some blank spaces on the basis of how many will be greater than the given element. We know that all the future elements will be >= curr element and so we can make the decision of whether to skip the current blank space of not. That's the reason :)

[@siddharthsingh9409]

i'am new with coding and don't know where to start......guide me where i can start solving problem and some time when i stuck its really feel bad so tell me where i can see solution>> nice explanation of above videos.

[@techdose4u]

You can start with reading editorials for easy level problems and try to solve them or implement the read idea. Once you get confident in easy level questions, move ahead.

[@pwnweb5734]

Greedy problems are just ;/

[@spetsnaz_2]

Very good explanation... Earlier I couldn't figure out why people were using count. Now it makes sense

[@techdose4u]

👍

[@abhishekkumardwivedi3817]

Thanks a lot, your videos are lot more helpful and explanation is also awesome and the choice of questions is also very good please do solve some more questions of the same or more hard level.

[@techdose4u]

👍

[@rohitbose405]

please do with segment tree

[@tejaswigutta9017]

@TECH DOSE when we solve a particular problem,how can we find similar questions applying similar logic with little modifications?

[@techdose4u]

Leetcode will recommend otherwise I don't know the correct method to find very specific type problem.

[@nishantsharma3100]

in the problem description there is a option below the question saying similar questions .

[@manojg4451]

Beautiful Explanation!

[@techdose4u]

Thanks

[@toekneema]

This should be a HARD question

[@techdose4u]

Right

[@bhaskary2362]

If we sort the elements with same heights in descending order of no. of people ahead of them then we don't need to check count for >= we would only need to count empty spaces.

[@TheTatsi100]

It is the best explanation, very clear. Thanks

[@techdose4u]

Thanks :)

[@faangsde]

While (publishing_video): print(" Awesome videos! Thanks 🌟🌟🌟")

[@nagajaswanth831]

solved it in python:)) class Solution(object): def reconstructQueue(self, people): people.sort() x=[0 for i in range(len(people))] for i in people: h=i[0] k=i[1] c=0 for j in range(len(x)): if x[j]==0: c+=1 elif x[j][0]==h: c+=1 if c==k+1: x[j]=[h,k] break return x

[@RitikKumar-cx5wf]

Sir, please help me to solve this question(when I use -1 for intialize for front and rear(-1) then it give me error but when I use (0) for intialize front and rear then it give me right answer ) // find largest multiplication of 3 no. Of array like {8,1,9}=>{9, 8,1}; Sir, please check my code // find largest multiplication of 3 by queue #include #include struct queue{ int front; int rear; int capacity; int *array; }; void enqueue(struct queue** q, int data){ if((*q)->rear+1==(*q)->capacity) return; else{ (*q)->array[(*q)->rear]=data; // printf(" %d",(*q)->array[(*q)->rear]); (*q)->rear=(*q)->rear+1; } } int dequeue(struct queue** q) { if((*q)->front==-1&&(*q)->rear==-1) return; int data=(*q)->array[(*q)->front]; for(int i=(*q)->front;irear-1;i++) (*q)->array[i]=(*q)->array[i+1]; (*q)->rear=(*q)->rear-1; // printf(" %d",(*q)->rear-1); // printf(" Dequeue=%d",data); return data; } int front(struct queue** q){ if((*q)->rear==-1&&(*q)->front==-1) return; return((*q)->array[(*q)->front]); } void push(struct queue** q,int data){ int extract; if((*q)->front==-1&&(*q)->rear==-1){ (*q)->front=0;(*q)->rear=0; enqueue(q, data); return; } else{ int temp=front(q); if(datafront;indexrear;index++) printf(" %d",q->array[index]); } struct queue* createqueue(int cap){ struct queue* q=(struct queue*)malloc(sizeof(struct queue)); q->rear=-1;q->front=-1; q->capacity=cap; q->array=(int*)malloc(cap*sizeof(int)); return q; } void main(){ int arr[3]={8,9,1};int index;int n=3; struct queue *q=createqueue(3); // q1.rear=-1;q.front=-1;q.capacity=-1; for(index=0;index

[@harshpatel1385]

Always great explanation. Can you explain bride hunting problem? .which is asked in tcs codevita. It is my request. I am watching your regular.

[@techdose4u]

This month I am busy with this leetcode discussions. I will see that bride hunting problem. Is it accessible to everyone?

[@harshpatel1385]

@@techdose4u yes .it is accessible to everyone.

[@harshpatel1385]

I know you putting to much effort. Next month codvita will be conducted.from all over India lots of student participated in it.if you put previously asked questions's solution then it beneficial for them to clear exam and they can get good package . This my suggestion sir .

[@techdose4u]

Yes I want to help everyone. But if I do that then I will miss this leetcode where I have already committed. That is why I am not able to add anything else 😅 I will try to do it if possible.

[@spetsnaz_2]

Can you share the code link here :-)

[@randomrandom316]

For someone looking for Python solution: def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]: n = len(people) people.sort(key=lambda x:x[0]) ans = [None]*n for pair in people: counter = pair[1] for index, item in enumerate(ans): if item is None: if counter==0: break else: counter-=1 else: if item[0]>=pair[0]: if counter==0: break else: counter-=1 ans[index] = pair return ans *This is not an optimum way of doing this rather a brute force approach.*

[@thallapakuteja2350]

are u giving solutions on ur own ? where do u work

[@techdose4u]

On my own means? Please follow linkedIn

[@thallapakuteja2350]

@@techdose4u thinking solution with ur brain without other help ur linked in id

[@techdose4u]

Check video description or else channel page.

[@dheerajpoonia2175]

[@techdose4u]

[@shabarishthamme445]

Sir why can't we sort based on values after storing given 2D array in map.

[@ShaliniNegi24]

Can We have more efficient algorithm ?

[@mohdaasimqureshi7115]

Great Explanation 🙌🙌

[@babbarutkarsh7770]

Best explaination ever !!!

[@techdose4u]

Thanks babbar :)

[@namanjain9094]

@@techdose4u Bro you should always post the optimized approach as by this approach interviewer will not be happy and will ask to optimized it and then what we will do ..... so you should always post optimized approach (in this case using segment tree) and thus not make fool of students following you. Hope you take this seriously as this is serious because there would be absolutely no gain In seeing your approach as the interviewer will definitely want an optimized approach and we would be stuck there. So please consider this seriously.

[@cocoarecords]

best thanks

[@avikmallick2493]

Can't it be done in O(n) or O(nlogn)?

[@namanjain9094]

@TECH DOSE Bro you should always post the optimized approach as by this approach interviewer will not be happy and will ask to optimized it and then what we will do ..... so you should always post optimized approach (in this case using segment tree) and thus not make fool of students following you. Hope you take this seriously as this is serious because there would be absolutely no gain In seeing your approach as the interviewer will definitely want an optimized approach and we would be stuck there. So please consider this seriously.

[@namanjain9094]

Yes this approach is fully wrong there is much optimization that could be done (use segment tree) See gfg

[@shrad6611]

question ka link daal diya karo bhai

[@techdose4u]

Question number is already present.

[@shrad6611]

but it is easy for your user to go and solve it first if url is present btw great video sir

[@priyankahegde6441]

Sir, can't we sort it based on number of people to be on left side, and if it's equal then sorting based on the height?

[@techdose4u]

I don't think this will work because a person with lower height doesn't effect the one with higher height

[@anuragtiwari5396]

i took the opposite approach of starting with the tallest person. My approach works because of the fact that if you insert a smaller person to the left of a tall person then it won't affect the order . class Solution { public: vector reconstructQueue(vector& people) { sort(people.begin(),people.end(),compareInterval); //sort the vector vector res; for(int i=0;ibrr[0])? true:(arr[0]==brr[0])?((arr[1]

[@CollectConnectDots]

Java Solution - github.com/neeraj11789/tech-interview-problems/blob/db63845ae0a24835f9edc8703e268d146cfa56d4/src/main/java/leetcode/junechallenge/QueueReconstructionByHeight.java

[@BoobalanMunusamy]

Coming up with your own solution is good, but people will raise the concerns when it is not an optimized one. After, submit your solution in leetcode, you may check with other's answers before making the video. Otherwise, you may lose the subscribers. This can be solved in O(nlogn +n) class Solution { public int[][] reconstructQueue(int[][] people) { List result = new ArrayList(); Arrays.sort(people, new Comparator() { @Override public int compare(int[] x, int[] y) { return x[0] == y[0] ? x[1] - y[1] : y[0] - x[0]; } }); for(int[] person : people) { result.add(person[1], person); } return result.toArray(new int[result.size()][]); } }

[@techdose4u]

Your solution is N2. Adding elements to dynamic array is O(N) per element (don't know about java but it is true for C++) and no solution on Leetcode discussions is below N2. They did not consider the dynamic array insertion time which is O(N).

[@vishalambhore4508]

​ TECH DOSE I agree this not nlogn solution but yes there is solution which run in o(nlogn) .

[@anujraj6370]

Time complexity can be significantly reduced to N*log^2N by using a Fenwick tree and doing a binary search.