EMPLOYEE FREE TIME (Leetcode) - Code & Whiteboard

Time Complexity: O(NlogN), where N is the number of intervals (this is because of the sort on line 22).
Space Complexity: O(N) because of the intervals list being created!
Leetcode #759 - Employee Free Time, with an easy-to-understand explanation :)
Let me know if you have any questions down below, or if there's a question you'd like me to cover next!
leetcode.com/p...
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Let's connect on LinkedIn!
/ aleksmitrovic
Follow me on Medium!
/ mitrovic.aleksandar
Questions or suggestions for new videos? Email me!
[e-mail]

[@maxgera4870]

Thanks for the video. The time complexity for this problem is O( N log N), there is optimal solution with O(N log K) where K the number of employees.

[@jamjam3448]

i solved it in O(n) time by using the sliding window technique.

[@vatssv3006]

I had been looking for good solutions/explanations for this one. This is beautiful really. You somehow made it look pretty easy tbh.

[@babybear-hq9yd]

thanks bro glad you found what u were looking for :)

[@AlexBlack-xz8hp]

Your video took this from being pretty incomprehensible to me to being super trivial in 20 minuts. Thank you sooooo much for your very clear explanation. It was incredibly helpful.

[@babybear-hq9yd]

glad it helped bro!

[@saitmesutcanilhaner8850]

Best explanation I have seen. Thank you very much! The solution seems simple but it is not easy to come up with the solution on the spot especially given the limited amount of time in the interviews. I don't think I would be able to fully solve this myself in 20 minutes.

[@babybear-hq9yd]

simple != easy :)

[@CDJohnson]

Great explanation! Your solution is a lot more intuitive than the solutions on LC. Subscribed!

[@babybear-hq9yd]

Thanks Christian!! Super happy that it helped :)

[@jamjam3448]

Thanks bro. All i wanted was to understand the question and then solve it by myself which i did in O(n) time. You explained the question well.

[@babybear-hq9yd]

appreciate it buddy, happy it helped!!

[@ShivangiSingh-wc3gk]

Thank you for an awesome walkthrough and explaining the concept with pictures.

[@babybear-hq9yd]

My pleasure!

[@alifyamohamedali1002]

Thank you so much for your explanation :). Wow you made it seem so trivial in the end. Blows my mind

[@babybear-hq9yd]

LFG!!

[@M0ren025]

this was really well explained.... Thank you so much, I spent hours looking at this and your video finally helped me understand (:

[@VijayKumar-my7ye]

I think the key to this problem might be merging the sorted lists to get a final sorted list and then finding the free slots in that final list. The problem is tagged under Merging Intervals so maybe thats being tested here. Its also possible to find the free slots as we get a stream of sorted Intervals while doing the merging. No need to loop again on final list.

[@coding8000]

God level Explanation, best on youtube!. Thanks man., love from Seattle.

[@babybear-hq9yd]

thanks buddy! hope you're holding the fort down over there

[@coding8000]

Thanks., Watched all of ur videos, please keep uploading more videos, more frequently., thanks.

[@chair_smesh]

If you had a cooler thumbnail like Neetcode and covered all the questions from Grokking the Coding Interview Patterns, I guarantee your channel will blow up

[@MohamedMagdy-00]

Great explanation ! Thanks

[@rahulbawa3969]

That was a really nice and easy explanation 👍

[@sunginjung3854]

this is a great explanation

[@chair_smesh]

Thanks, Wolverine!

[@babybear-hq9yd]

HAHAHAH

[@shanjiang2078]

Great explanation! thank you so much!!

[@babybear-hq9yd]

Thanks Shan!! My pleasure :)

[@juanhernandez-up4pg]

Great teacher ☺️

[@babybear-hq9yd]

thx juan :)

[@harleenkaur4599]

Thank you for the video. Quick question - what if instead of busy time, free times are given for all the employees. How can I get optimal solution in that case?

[@TULKICK]

Do everything same till merge and sort. Then if there is an overlap, store [max of start times, min of end times].

[@pranabsarkar]

Thanks a lot Guru !

[@babybear-hq9yd]

pleasure's all mine :D

[@deionshall5446]

Awesome solution! I am a little confused about why we used lambda here? I was able to pass using the following code

[@deionshall5446]

//sort intervals intervals.sort() //find free time result = [] prevEnd = intervals[0][1] for start, end in intervals: if start > prevEnd: result.append(Interval(prevEnd, start)) prevEnd = max(prevEnd, end) print(result) return result

[@babybear-hq9yd]

@@deionshall5446 Hey Deion, I believe that by default when sorting a "list that is nested with multiple other lists" the built in sort function in Python (i.e. Timsort) will sort it by the first element of the nested lists. The reason I broke it out separately here was just because I think it may have made the logic a bit easier to follow (i.e. by strictly addressing the fact that we are sorting by start time). In some questions, we may also want to sort by end time, or other parameters in this list, in which case a lambda function would be necessary (you could see examples of this in the Vertical Traversal of a Binary Tree video, for instance). So, strictly speaking, you're right. We didn't necessary have to use a lambda function in this particular scenario :) Does this answer the question?

[@deionshall5446]

@@babybear-hq9yd awesome thanks for breaking that down. I see what you mean now. I never used lambda functions like that , but I realize how useful they can be in algos! Thanks for taking the time to explain that

[@sensen338]

Very well explained :)

[@davidlee588]

My JS solution is much intuitive, I wonder if this will pass the time complexity if I use flat(): const freetime = function (hours) { let copy = hours.flat().sort((a, b) => a[1] - b[1]); let result = []; let prev = copy[0]; for (let i = 1; i < copy.length; i++) { if (copy[i][0] - prev[1] > 0) result.push([prev[1], copy[i][0]]); prev = copy[i]; } return result; }; Thank you for your comment.

[@babybear-hq9yd]

no idea what the time complexity of the `flat` function is buddy sorry. It's probably good to mention in an interview that that's an option, though a follow-up question would be what the complexity is, and perhaps how to implement it manually if you needed to. Can't say for sure but just some thoughts that come to mind first

[@srinivasnisha03]

What would be the run time of the algorithm? I am thinking Time complexity would be O(NlogN) (N is it he number of intervals) and pace complexity is O(1) or maybe O(N) since we are creating the intervals list.

[@babybear-hq9yd]

You're correct! The time complexity would be O(NlogN) because of the sort on line 22, and space would be O(N) because of the interval's list :) I'll add this to the description of the problem as well for future reference.

[@srinivasnisha03]

Thank you for replying !

[@Vlad1998996]

you are great

[@goldfish8196]

Wow! So great. Thank you!

[@babybear-hq9yd]

welcome :D

[@tylercondon3453]

Has an interviewer ever asked you to solve this problem or any interval problem without first sorting the intervals?

[@babybear-hq9yd]

Nope! I’ve lucked out :’)

[@gurupreetsingh8347]

thanks good explanation but what about the Time complexity of nested LOOPS ? I guess its no of employees * no of intervals in another words - Each employee * intervals of each employee , am i right ? So I think for nested looping Time complexity would be O(K*N) only (here K is not constant actually, Can't be constant infact!! So we can ignore it by just treating like constant value) and for sorting Time complexity is O(N LOG N) and O(N LOG N ) is lesser than O(K*N) am I right ? So over all Time complexity would be O(K*N) right not O(N LOG N) ? Please correct me if I am wrong!! :)

[@TULKICK]

If N is the number of intervals and K is the number of employees, then on avg each employee will have N/K intervals each. So, for each employee, the inner loop will run N/K times. Thus, overall the entire nested loop will run K*(N/K) times, = N times. So, complexity will be O(N), for nested loop. Overall complexity is O(NlogN) only.

[@harvitech8871]

Nice explanation

[@babybear-hq9yd]

Happy to help! :)

[@goodpeople7615]

Baby bear great 🐨🔥 But is it making use of the fact that times are given in sorted order !!

[@babybear-hq9yd]

Thank you! It does not, because notice that it's the individual employee times that are in sorted order, not an overall collection of all possible times. In fact, that piece of information is a bit of a red herring. In lines 16-19 we group all the individual times into one big batch of times, which then needs to be sorted. Does that make sense? :)

[@goodpeople7615]

@@babybear-hq9yd I want to say that maybe sorted bcoz of some reason but ur approach seems easier to understand :)

[@adamsoliev6667]

Thanks

[@RohanPatel-xh2lc]

Subscribed.

[@babybear-hq9yd]

welcome :D

[@Zoronoa01]

great explanation, thank you!