Saltar al contenido principal

Kth Largest Element in an Array

Given an array of integers, nums, and a value k, return the kth largest element.

Example(s)​

Example 1:

Input: nums = [1, 2, 3], k = 1
Output: 3
Explanation:
Sorted: [1, 2, 3]
1st largest = 3

Example 2:

Input: nums = [9, 2, 1, 7, 3, 2], k = 5
Output: 2
Explanation:
Sorted: [1, 2, 2, 3, 7, 9]
5th largest = 2

Example 3:

Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
Explanation:
Sorted: [1, 2, 3, 4, 5, 6]
2nd largest = 5

Solution​

There are multiple approaches:

  1. Sorting: Sort array and return kth from end - O(n log n)
  2. Min Heap: Maintain heap of size k - O(n log k)
  3. Quickselect: Partition-based selection - O(n) average

JavaScript Solution - Sorting

/**
* Find kth largest element using sorting
* @param {number[]} nums - Input array
* @param {number} k - Kth largest position
* @return {number} - Kth largest element
*/
function findKthLargest(nums, k) {
// Sort in descending order
nums.sort((a, b) => b - a);

// Return kth element (0-indexed, so k-1)
return nums[k - 1];
}

// Test cases
console.log('Example 1:', findKthLargest([1, 2, 3], 1)); 
// 3

console.log('Example 2:', findKthLargest([9, 2, 1, 7, 3, 2], 5)); 
// 2

console.log('Example 3:', findKthLargest([3, 2, 1, 5, 6, 4], 2)); 
// 5
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Min Heap)​

Here's a more efficient approach using a min heap:

/**
 * Min heap approach - O(n log k) time, O(k) space
 */
function findKthLargestHeap(nums, k) {
  // Min heap of size k
  const heap = [];
  
  for (const num of nums) {
    if (heap.length < k) {
      heap.push(num);
      heapifyUp(heap, heap.length - 1);
    } else if (num > heap[0]) {
      // Replace smallest element
      heap[0] = num;
      heapifyDown(heap, 0);
    }
  }
  
  return heap[0]; // Root is kth largest
}

// Min heap helpers
function heapifyUp(heap, index) {
  while (index > 0) {
    const parent = Math.floor((index - 1) / 2);
    if (heap[parent] <= heap[index]) break;
    [heap[parent], heap[index]] = [heap[index], heap[parent]];
    index = parent;
  }
}

function heapifyDown(heap, index) {
  while (true) {
    let smallest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    
    if (left < heap.length && heap[left] < heap[smallest]) {
      smallest = left;
    }
    if (right < heap.length && heap[right] < heap[smallest]) {
      smallest = right;
    }
    if (smallest === index) break;
    [heap[index], heap[smallest]] = [heap[smallest], heap[index]];
    index = smallest;
  }
}

Alternative Solution (Quickselect)​

Here's the optimal average-case solution using quickselect:

/**
 * Quickselect approach - O(n) average, O(n²) worst case
 */
function findKthLargestQuickselect(nums, k) {
  // Convert to 0-indexed: kth largest = (n-k)th smallest
  const targetIndex = nums.length - k;
  
  function quickselect(left, right, targetIndex) {
    if (left === right) {
      return nums[left];
    }
    
    const pivotIndex = partition(left, right);
    
    if (pivotIndex === targetIndex) {
      return nums[pivotIndex];
    } else if (pivotIndex < targetIndex) {
      return quickselect(pivotIndex + 1, right, targetIndex);
    } else {
      return quickselect(left, pivotIndex - 1, targetIndex);
    }
  }
  
  function partition(left, right) {
    const pivot = nums[right];
    let i = left;
    
    for (let j = left; j < right; j++) {
      if (nums[j] <= pivot) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
      }
    }
    [nums[i], nums[right]] = [nums[right], nums[i]];
    return i;
  }
  
  return quickselect(0, nums.length - 1, targetIndex);
}

Complexity​

  • Time Complexity:
    • Sorting: O(n log n) - Sort the entire array
    • Min Heap: O(n log k) - Process n elements, heap operations are O(log k)
    • Quickselect: O(n) average, O(n²) worst case
  • Space Complexity:
    • Sorting: O(1) or O(n) depending on sorting algorithm
    • Min Heap: O(k) - Heap of size k
    • Quickselect: O(1) - In-place partitioning

Approach​

Sorting Approach:​

  1. Sort array: Sort in descending order
  2. Return kth element: Return element at index k-1

Min Heap Approach:​

  1. Maintain heap of size k: Keep k largest elements
  2. Min heap property: Root is the smallest of k largest
  3. Process elements: For each element, if larger than root, replace root
  4. Return root: Root is the kth largest

Quickselect Approach:​

  1. Partition: Use pivot to partition array
  2. Recurse: Recursively search in the correct partition
  3. Target index: kth largest = (n-k)th smallest
  4. Average O(n): Each partition eliminates half on average

Key Insights​

  • Sorting is simple: Easy to implement, O(n log n)
  • Min heap is efficient: O(n log k), better when k << n
  • Quickselect is optimal: O(n) average case
  • Kth largest = (n-k)th smallest: Useful for quickselect
  • Heap size k: Only need to track k largest elements

Step-by-Step Example​

Let's trace through Example 1: nums = [1, 2, 3], k = 1

Sorting Approach:
  Original: [1, 2, 3]
  Sorted (descending): [3, 2, 1]
  k = 1, so return index 0: 3

Min Heap Approach (k = 1):
  Process 1: heap = [1]
  Process 2: 2 > 1, replace: heap = [2]
  Process 3: 3 > 2, replace: heap = [3]
  Return heap[0] = 3

Quickselect Approach:
  targetIndex = 3 - 1 = 2 (2nd smallest = 1st largest)
  Partition [1, 2, 3] with pivot 3:
    Elements <= 3: [1, 2, 3]
    pivotIndex = 2
    pivotIndex == targetIndex? Yes
    Return nums[2] = 3

Visual Representation​

Example 1: nums = [1, 2, 3], k = 1

Sorted (descending): [3, 2, 1]
                      ↑
                   1st largest = 3

Example 2: nums = [9, 2, 1, 7, 3, 2], k = 5

Sorted (descending): [9, 7, 3, 2, 2, 1]
                     1  2  3  4  5  6
                                    ↑
                                 5th largest = 2

Edge Cases​

  • k = 1: Return maximum element
  • k = n: Return minimum element
  • k = n/2: Return median
  • All same elements: Returns that element
  • Duplicates: Works correctly (kth largest, not kth distinct)

Important Notes​

  • Kth largest: Not kth distinct largest
  • 1-indexed: k = 1 means largest, k = 2 means second largest
  • Duplicates count: [2, 2, 1] with k=2 returns 2
  • Sorting modifies array: May need to copy if original needed
  • Heap is efficient: Better when k is small

Comparison of Approaches​

ApproachTimeSpaceBest For
SortingO(n log n)O(1)Simple, small arrays
Min HeapO(n log k)O(k)When k << n
QuickselectO(n) avgO(1)When k ≈ n/2
  • Kth Smallest Element: Similar problem
  • Top K Frequent Elements: Different problem
  • Find Median: Special case (k = n/2)
  • K Closest Points: Different selection problem

Takeaways​

  • Sorting is simplest but O(n log n)
  • Min heap is efficient when k is small
  • Quickselect provides optimal average case
  • Kth largest = (n-k)th smallest for quickselect
  • Choose based on constraints and k value