Kth Largest Element in an Array

This content originally appeared on DEV Community and was authored by Subham

#️⃣ 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.

This content originally appeared on DEV Community and was authored by Subham

Print Share Comment Cite Upload Translate Updates

APA

Subham | Sciencx (2024-09-23T14:38:36+00:00) Kth Largest Element in an Array. Retrieved from https://www.scien.cx/2024/09/23/kth-largest-element-in-an-array-2/

MLA

" » Kth Largest Element in an Array." Subham | Sciencx - Monday September 23, 2024, https://www.scien.cx/2024/09/23/kth-largest-element-in-an-array-2/

HARVARD

Subham | Sciencx Monday September 23, 2024 » Kth Largest Element in an Array., viewed ,<https://www.scien.cx/2024/09/23/kth-largest-element-in-an-array-2/>

VANCOUVER

Subham | Sciencx - » Kth Largest Element in an Array. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/09/23/kth-largest-element-in-an-array-2/

CHICAGO

" » Kth Largest Element in an Array." Subham | Sciencx - Accessed . https://www.scien.cx/2024/09/23/kth-largest-element-in-an-array-2/

IEEE

" » Kth Largest Element in an Array." Subham | Sciencx [Online]. Available: https://www.scien.cx/2024/09/23/kth-largest-element-in-an-array-2/. [Accessed: ]

rf:citation

» Kth Largest Element in an Array | Subham | Sciencx | https://www.scien.cx/2024/09/23/kth-largest-element-in-an-array-2/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.