Kth Largest Element in an Array - Leetcode 215 - Heaps (Python)

Подписаться 186 тыс.

Просмотров 5 тыс.

50% 1

Master Data Structures & Algorithms for FREE at AlgoMap.io/
Code solutions in Python, Java, C++ and JS for this can be found at my GitHub repo here: github.com/gah...
Complete DSA Pathway Zero to Hero: • Data Structures & Algo...
Please check my playlists for free DSA problem solutions:
• Fundamental DSA Theory
• Array & String Questions
• 2 Pointers Questions
• Sliding Window Questions
• Binary Search Questions
• Stack Questions
• Linked List Questions
• Tree Questions
• Heap Questions
• Recursive Backtracking...
• Graph Questions
• Dynamic Programming (D...
My Data Science & ML RU-vid Playlist: • Greg's Path to Become ...
Learn Python and Data Science FASTER at mlnow.ai :)
Support the content: / @greghogg
Follow me on Instagram: / greghogg5
Connect with me on LinkedIn: / greghogg
Follow me on TikTok: / greghogg5
Coursera Plus: imp.i384100.ne...
My Favorite Courses:
Data Structures & Algorithms:
- UCalifornia San Diego DSA: imp.i384100.ne...
- Stanford Algorithms: imp.i384100.ne...
- Python Data Structures: imp.i384100.ne...
- Meta Coding Interview Prep: imp.i384100.ne...
Python:
- UMichigan Python for Everybody: imp.i384100.ne...
- Python Mastery from MLNOW.ai: mlnow.ai/cours...
- Google IT Automation w/ Python: imp.i384100.ne...
Web Dev / Full Stack:
- Meta Front-End Developer: imp.i384100.ne...
- IBM Full Stack Developer: imp.i384100.ne...
- Meta Back-End Developer: imp.i384100.ne...
- John Hopkins HTML, CSS & JS: imp.i384100.ne...
- IBM DevOps: imp.i384100.ne...
Cloud Development:
- AWS Fundamentals: imp.i384100.ne...
- GCP Cloud Engineer: imp.i384100.ne...
- Microsoft Azure Fundamentals: imp.i384100.ne...
Game Development:
- Michigan State Unity Development: imp.i384100.ne...
- UColorado C++ for Unreal Engine: www.coursera.o...
SQL & Data Science:
- SQL by MLNOW.ai: mlnow.ai/cours...
- Python for Data Science by MLNOW.ai: mlnow.ai/cours...
- Google Data Analytics: imp.i384100.ne...
- IBM Data Science: imp.i384100.ne...
- IBM Data Engineer: imp.i384100.ne...
Machine Learning & AI:
- ML Mastery at MLNOW.ai: mlnow.ai/cours...
- ML w/ Andrew Ng: www.coursera.o...
- Deep Learning w/ Andrew Ng: imp.i384100.ne...

Опубликовано:

9 сен 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 13

@GregHogg Месяц назад

Master Data Structures & Algorithms For FREE at AlgoMap.io!

@EverAfterBreak2 17 дней назад

The min heap solution explanation is so good, heaps can be used to solve a lot of “k or kth” problems

@ew2430 2 месяца назад

You have a talent for explaining, great video!

@GregHogg 2 месяца назад

Thank you very much 😊

@thisisactuallyhilarious2575 2 месяца назад

You actually don't need to negate your values. Instead of finding the kth largest number, you can find the (len(nums) - k + 1)th smallest number if that makes sense. For example if I had a list of numbers [1, 2, 3, 4, 5] and wanted to find the 2nd largest number which in this case is 4, I could technically find the (5-3+1) = 4th smallest number which is also 4.

@GregHogg 2 месяца назад

Interesting idea

@hamadrehman853 13 дней назад

this is so good.

@idannadi6451 2 месяца назад

There is actually a better solution, which takes O(N + klog(k)) which is much better than O(Nlogk), but it takes O(k) space instead of O(1). It goes like this: 1. transform the given array into max heap. Call it A. 2. build a new empty max-heap (or rather priority queue) of size k + 1. Call it B a. in this heap we will keep all the candidate "next largest" items. b. every item in this heap will be tuple of value and index/pointer to that value in A. c. the heap propity will be according to the value field of the tuple 3.insert (A[0], 0) to B. now we will use this algorithm: for i in range(k-1): m = B.extractMax() # insert it's children, the only new candidates of the next largest number left_child_index = A.left_child(m[1]) right_child_index = A.right_child(m[1]) B.insert(tuple(A[left_child_index], left_child_index)) B.insert(tuple(A[right_child_index], right_child_index)) # end for # return the vaule of the k'th largest: return m[0] using this, when we "extract" form A, we dont fix it so we dont have to pay O(logn) each time, but rather by the log of size of B: O(log(1) + log(2) + log(3) +... + log(k)) < O(klogk) add the building of A max heap, ehih is O(n) we get O(n + klogk)

@KermitDominicano 6 дней назад

I didn't realize heapify only takes O(n) time! Good to know. I always assumed that it was O(nlogn)

@amitamar9852 2 месяца назад

Great video! But there is a better solution that is running in linear time with O(1) memory, which is better than O(nlogk) with O(k) space. This algorithm is called the “Selection Algorithm”, which was invented in 1973.

@rojo_pes75 Месяц назад

U are so good man🤟

@na50r24 2 месяца назад

Weird question If you use heapSort but k times, wouldn't that work too or does that count as sorting? It's strictly less than sorting the whole array and getting the kth largest element, since I only sort it k times with the outer loop rather than n. So it'd be O(k log n)