K-th Largest element in an array

Heaps Theory and Implementation Medium

The concept underlying the "kth largest element" problem is widely used in real-time analytics applications and Big Data processing, where one might need to find the top k values out of massive streams of data
This concept is used in systems used by massive social media platforms where they need to identify the top trending topics, hashtags, or posts at any given time
Similarly, this same principle is used in music streaming apps to find the top k most listened songs out of millions of songs available

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.

Code

Problem List