K-th Largest element in an array

Heaps Theory and Implementation Medium Go Ad-Free - ₹20/mo

Given an array nums, return the k^th largest element in the array.

Examples:

Input: nums = [1, 2, 3, 4, 5], k = 2

Output: 4

Input: nums = [-5, 4, 1, 2, -3], k = 5

Output: -5

Input: nums = [11, 9, 8, 7, 3, 1], k = 4

Constraints

1 <= nums.length <= 10⁵
-1000 <= nums[i] <= 1000
1 <= k <= nums.length

Hints

"Use a min-heap of size k. Insert the first k elements into the heap. The heap’s root (smallest in the heap) is the k-th largest element."
"Convert the entire array into a max-heap (O(n)). Extract k elements using heapify-down (O(k log n)). The k-th extracted element is the k-th largest."

Company Tags

Epic Games Cloudflare Optum Johnson & Johnson Cerner Broadcom Target Pinterest Salesforce Mastercard Medtronic Snowflake Stripe Texas Instruments Electronic Arts KPMG Byju's Rockstar Games Swiggy Qualcomm Morgan Stanley Zoho Goldman Sachs Bain & Company DoorDash Google Microsoft Amazon Meta Apple Netflix Adobe

Editorial

              document.body.innerHTML = '';
              const iframeHTML = `
                <div style="padding-top:56.25%;position:relative;">
                  <iframe 
                    src="https://app.tpstreams.com/embed/atsjxr/99XDcbhjkcX/?access_token=33e345b1-9f22-4382-8c5c-7e49a75d8027" 
                    style="border:0;max-width:100%;position:absolute;top:0;left:0;height:100%;width:100%;" 
                    allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" 
                    allowfullscreen="" 
                    frameborder="0">
                  </iframe>
                </div>
              `;
              document.body.innerHTML = iframeHTML;
              
              const script = document.createElement('script');
              script.src = 'https://static.testpress.in/static/js/player.js';
              document.head.appendChild(script);
              
              script.onload = () => {
                const iframe = document.querySelector('iframe');
                const player = new Testpress.Player(iframe);
              
                player.loaded().then(() => {
                  console.log('Player is ready now');
                });
              
                player.on('play', () => {
                  console.log('Played the video');
                });
              };

Striver and the team have worked tirelessly over the past few days to bring this to you. Please bear with us a little more as we finalize everything.

Frequently Occurring Doubts

Q: Why use a min-heap for k-th largest instead of max-heap?

A: A min-heap of size k tracks the top k largest elements, making extraction O(1). A max-heap stores everything, requiring O(k log n) extraction.

Interview Followup Questions

Q: What changes for k-th largest in a BST instead of an array?

A: Perform reverse inorder traversal, counting elements until reaching k. Time Complexity: O(h + k) ≈ O(log n + k) for balanced BSTs.

Q: How does QuickSelect compare to Median of Medians for selection problems?

A: QuickSelect is O(n) on average but O(n²)` worst case. Median of Medians ensures O(n) worst case but is more complex to implement.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories