Task Scheduler - LeetCode 621 - Python [O(n) time and O(1) Space!]
If this HELPED at all, check out my channel for even **MORE VIDEOS**!!:)) https://www.youtube.com/c/DEEPTITALES...
Explaining how to solve Task Scheduler in Python - LeetCode 621!
(Typo @5:40: should be adding D E F G to the end for output = 10!)
The time complexity for this solution will be O(n). We first iterate through the entire list to keep counts (O(n)). Then, we sort based on the values which typically comes out to O(nlogn) BUT we know that we are only ever sorting 26 letters maximum, so we only need 26 elements to sort and so our n = 26. This makes sorting a constant time operation = 26log26 = constant number not dependent on n, therefore, O(1). After, we iterate again to count how many max values we have that are also our maximum, and this again should be order O(n), but we are only iterating over 26 elements, so we know our while loop will terminate after 26 elements since len(lst) is bounded by 26. And finally, we do constant time calculations, so our overall time complexity is just O(n).
Our space complexity is also O(1) since we only need a dictionary with 26 keys.
** We will never have more than 26 letters so the keys in our dictionary are bound by 26 and therefore so is the length of the lst we maintain.
Music: Bensound
Code: https://github.com/deepti-talesra/Lee...
Lemme know if y'all got questions/comments!!
Watch video Task Scheduler - LeetCode 621 - Python [O(n) time and O(1) Space!] online without registration, duration hours minute second in high quality. This video was added by user DEEPTI TALESRA 20 October 2019, don't forget to share it with your friends and acquaintances, it has been viewed on our site 15,448 once and liked it 283 people.