Kth Largest Element in an Array

#️⃣ Array, Priority Queue, Quick Select

https://leetcode.com/problems/kth-largest-element-in-an-array/description

? Understand Problem

If the array is [8, 6, 12, 9, 3, 4] and k is 2, you need to find the 2nd largest element in this array. First, you will sort the array: [3, 4, 6, 8, 9, 12] The output will be 9 because it is the second-largest element.

✅ Bruteforce

var findKthLargest = function(nums, k) {
    // Sort the array in ascending order
    nums.sort((a, b) => a - b);

    // Return the kth largest element
    return nums[nums.length - k];
};

Explanation:

1. Sorting the Array: The array is sorted in ascending order using the sort method.
2. Finding the kth Largest Element: The kth largest element is found by accessing the element at the index nums.length - k.

Time Complexity:

• Sorting: The time complexity of sorting an array is (O(nlog n)), where (n) is the length of the array.
• Accessing the Element: Accessing an element in an array is O(1).

So, the overall time complexity is O(n log n).

Space Complexity:

• In-Place Sorting: The sort method sorts the array in place, so the space complexity is O(1) for the sorting operation.
• Overall: Since we are not using any additional data structures, the overall space complexity is O(1).

✅ Better

var findKthLargest = function(nums, k) {
        // Create a min-heap using a priority queue
        let minHeap = new MinPriorityQueue();

        // Add the first k elements to the heap
        for (let i = 0; i 



<h4>
  
  
  Explanation:
</h4>

<ol>
<li>
<strong>Initial Array</strong>: [2, 1, 6, 3, 5, 4]
</li>
<li>
<strong>k = 3</strong>: We need to find the 3rd largest element.</li>
</ol>

<h4>
  
  
  Step 1: Add the first k elements to the min-heap
</h4>

• Heap after adding 2: [2]
• Heap after adding 1: [1, 2]
• Heap after adding 6: [1, 2, 6]

Step 2: Iterate through the remaining elements

• Current element = 3

  • Heap before comparison: [1, 2, 6]
  • Smallest element in heap (minHeap.front().element): 1
  • Comparison: 3 > 1
  • Action: Remove 1 and add 3
  • Heap after update: [2, 6, 3]

• Current element = 5

  • Heap before comparison: [2, 6, 3]
  • Smallest element in heap (minHeap.front().element): 2
  • Comparison: 5 > 2
  • Action: Remove 2 and add 5
  • Heap after update: [3, 6, 5]

• Current element = 4

  • Heap before comparison: [3, 6, 5]
  • Smallest element in heap (minHeap.front().element): 3
  • Comparison: 4 > 3
  • Action: Remove 3 and add 4
  • Heap after update: [4, 6, 5]

Final Step: Return the root of the heap

• Heap: [4, 6, 5]
• 3rd largest element: 4 (the root of the heap)

Time Complexity:

• Heap Operations: Inserting and removing elements from the heap takes O(log k) time.
• Overall: Since we perform these operations for each of the n elements in the array, the overall time complexity is O(n log k).

Space Complexity:

• Heap Storage: The space complexity is O(k) because the heap stores at most k elements.

✅ Best

Note: Even though Leetcode restricts quick select, you should remember this approach because it passes most test cases

//Quick Select Algo

function quickSelect(list, left, right, k)

   if left = right
      return list[left]

   Select a pivotIndex between left and right

   pivotIndex := partition(list, left, right, 
                                  pivotIndex)
   if k = pivotIndex
      return list[k]
   else if k 





<pre class="brush:php;toolbar:false">var findKthLargest = function(nums, k) {
    // Call the quickSelect function to find the kth largest element
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
};

function quickSelect(nums, low, high, index) {
    // If the low and high pointers are the same, return the element at low
    if (low === high) return nums[low];

    // Partition the array and get the pivot index
    let pivotIndex = partition(nums, low, high);

    // If the pivot index is the target index, return the element at pivot index
    if (pivotIndex === index) {
        return nums[pivotIndex];
    } else if (pivotIndex > index) {
        // If the pivot index is greater than the target index, search in the left partition
        return quickSelect(nums, low, pivotIndex - 1, index);
    } else {
        // If the pivot index is less than the target index, search in the right partition
        return quickSelect(nums, pivotIndex + 1, high, index);
    }
}

function partition(nums, low, high) {
    // Choose the pivot element
    let pivot = nums[high];
    let pointer = low;

    // Rearrange the elements based on the pivot
    for (let i = low; i 



<h4>
  
  
  Explanation:
</h4>

<ol>
<li>
<strong>Initial Array</strong>: [3, 2, 1, 5, 6, 4]
</li>
<li>
<strong>k = 2</strong>: We need to find the 2nd largest element.</li>
</ol>

<h4>
  
  
  Step 1: Partition the array
</h4>

• Pivot element = 4
• Array after partitioning: [3, 2, 1, 4, 6, 5]
• Pivot index = 3

Step 2: Recursive Selection

• Target index = 4 (since we need the 2nd largest element, which is the 4th index in 0-based indexing)
• Pivot index (3) : Search in the right partition [6, 5]

Step 3: Partition the right partition

• Pivot element = 5
• Array after partitioning: [3, 2, 1, 4, 5, 6]
• Pivot index = 4

Final Step: Return the element at the target index

• Element at index 4: 5

Time Complexity:

• Average Case: The average time complexity of Quickselect is O(n).
• Worst Case: The worst-case time complexity is O(n^2), but this is rare with good pivot selection.

Space Complexity:

• In-Place: The space complexity is O(1) because the algorithm works in place.

The above is the detailed content of Kth Largest Element in an Array. For more information, please follow other related articles on the PHP Chinese website!