Kth Largest Element in an Array - Leetcode 215

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

Рет қаралды 3,303

Ай бұрын

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/gahogg/Leetcode-So...
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 KZfaq 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.net/P0E3J6
My Favorite Courses:
Data Structures & Algorithms:
- UCalifornia San Diego DSA: imp.i384100.net/LP31oV
- Stanford Algorithms: imp.i384100.net/vNBoxd
- Python Data Structures: imp.i384100.net/NkZn47
- Meta Coding Interview Prep: imp.i384100.net/Y96rBJ
Python:
- UMichigan Python for Everybody: imp.i384100.net/QOLM73
- Python Mastery from MLNOW.ai: mlnow.ai/course-material/python/
- Google IT Automation w/ Python: imp.i384100.net/5g6Xyj
Web Dev / Full Stack:
- Meta Front-End Developer: imp.i384100.net/q4Jemy
- IBM Full Stack Developer: imp.i384100.net/Gj9dMn
- Meta Back-End Developer: imp.i384100.net/xkW0r5
- John Hopkins HTML, CSS & JS: imp.i384100.net/QyoRAA
- IBM DevOps: imp.i384100.net/kjd2r0
Cloud Development:
- AWS Fundamentals: imp.i384100.net/anqBjZ
- GCP Cloud Engineer: imp.i384100.net/g1jvqB
- Microsoft Azure Fundamentals: imp.i384100.net/EKm5O4
Game Development:
- Michigan State Unity Development: imp.i384100.net/6eOBnr
- UColorado C++ for Unreal Engine: www.coursera.org/specializati...
SQL & Data Science:
- SQL by MLNOW.ai: mlnow.ai/course-material/sql/
- Python for Data Science by MLNOW.ai: mlnow.ai/course-material/data...
- Google Data Analytics: imp.i384100.net/1rkWAR
- IBM Data Science: imp.i384100.net/P0ZRL6
- IBM Data Engineer: imp.i384100.net/4PbZyZ
Machine Learning & AI:
- ML Mastery at MLNOW.ai: mlnow.ai/course-material/ml/
- ML w/ Andrew Ng: www.coursera.org/specializati...
- Deep Learning w/ Andrew Ng: imp.i384100.net/a1kjJj

Пікірлер: 10

@GregHogg 4 күн бұрын

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

@ew2430 Ай бұрын

You have a talent for explaining, great video!

@GregHogg Ай бұрын

Thank you very much 😊

@rojo_pes75 10 күн бұрын

U are so good man🤟

@na50r24 Ай бұрын

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)

@amitamar9852 Ай бұрын

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.

@thisisactuallyhilarious2575 Ай бұрын

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 Ай бұрын

Interesting idea

@idannadi6451 29 күн бұрын

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)