DEV Community

Cover image for Kth Largest Element in an Array
Subham
Subham

Posted on

1

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];
};
Enter fullscreen mode Exit fullscreen mode

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;
    };
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode
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;
}
Enter fullscreen mode Exit fullscreen mode

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.

Sentry blog image

How to reduce TTFB

In the past few years in the web dev world, we’ve seen a significant push towards rendering our websites on the server. Doing so is better for SEO and performs better on low-powered devices, but one thing we had to sacrifice is TTFB.

In this article, we’ll see how we can identify what makes our TTFB high so we can fix it.

Read more

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay