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 < k; i++) {
            //minHeap.enqueue(nums[i]): Adds the element nums[i] to the min-heap.
            minHeap.enqueue(nums[i]);
        }

        // Iterate through the remaining elements
        for (let i = k; i < nums.length; i++) {
            //minHeap.front().element: Retrieves the smallest element in the min-heap without removing it.
            if (minHeap.front().element < nums[i]) {
                // minHeap.dequeue(): Removes the smallest element from the min-heap.
                minHeap.dequeue();
                // Add the current element
                minHeap.enqueue(nums[i]);
            }
        }

        // The root of the heap is the kth largest element
        return minHeap.front().element;
    };

Explanation:

1. Initial Array: [2, 1, 6, 3, 5, 4]
2. k = 3: We need to find the 3rd largest element.

Step 1: Add the first k elements to the min-heap

• 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 < pivotIndex
        right := pivotIndex - 1
     else
        left := pivotIndex + 1
  

  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 < high; i++) {
          if (nums[i] <= pivot) {
              [nums[i], nums[pointer]] = [nums[pointer], nums[i]];
              pointer++;
          }
      }
  
      // Place the pivot element in its correct position
      [nums[pointer], nums[high]] = [nums[high], nums[pointer]];
      return pointer;
  }
  

  Explanation:

  1. Initial Array: [3, 2, 1, 5, 6, 4]
  2. k = 2: We need to find the 2nd largest element.

  Step 1: Partition the array

  • 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) < Target index (4): 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!