ℹ️ Select 'Choose Exercise', or randomize 'Next Random Exercise' in selected language.

Choose Exercise:
Timer 00:00
WPM --
Score --
Acc --
Correct chars --

Find Kth Largest Element in an Unsorted Array

Dart

Goal -- WPM

Ready
Exercise Algorithm Area
1int findKthLargest(List<int> nums, int k) {

2if (nums.isEmpty || k <= 0 || k > nums.length) {

3throw ArgumentError('Invalid input: array is empty or k is out of bounds.');

4}

5// The problem asks for the k-th LARGEST element. This is equivalent to finding the (n-k)-th SMALLEST element.

6// We adjust k to work with a standard partition that finds the k-th smallest element.

7int targetIndex = nums.length - k;

8return quickSelect(nums, 0, nums.length - 1, targetIndex);

9}

10

11int quickSelect(List<int> nums, int left, int right, int kSmallestIndex) {

12if (left == right) {

13return nums[left];

14}

15

16// Choose a pivot index. A simple choice is the rightmost element.

17// For better average performance, a random pivot or median-of-three could be used.

18int pivotIndex = right;

19

20// Partition the array around the pivot.

21pivotIndex = partition(nums, left, right, pivotIndex);

22

23// Check if the pivot is the k-th smallest element.

24if (kSmallestIndex == pivotIndex) {

25return nums[kSmallestIndex];

26} else if (kSmallestIndex < pivotIndex) {

27// If k-th smallest is to the left of the pivot, recurse on the left subarray.

28return quickSelect(nums, left, pivotIndex - 1, kSmallestIndex);

29} else {

30// If k-th smallest is to the right of the pivot, recurse on the right subarray.

31return quickSelect(nums, pivotIndex + 1, right, kSmallestIndex);

32}

33}

34

35// Partitions the subarray nums[left..right] around the pivot at pivotIndex.

36// Elements smaller than the pivot are moved to its left, and larger elements to its right.

37// Returns the final index of the pivot after partitioning.

38int partition(List<int> nums, int left, int right, int pivotIndex) {

39int pivotValue = nums[pivotIndex];

40// Move pivot to the end for easier partitioning.

41swap(nums, pivotIndex, right);

42int storeIndex = left;

43

44// Iterate through the subarray (excluding the pivot now at the end).

45for (int i = left; i < right; i++) {

46if (nums[i] < pivotValue) {

47swap(nums, storeIndex, i);

48storeIndex++;

49}

50}

51

52// Move pivot to its final sorted place.

53swap(nums, storeIndex, right);

54return storeIndex;

55}

56

57void swap(List<int> nums, int i, int j) {

58int temp = nums[i];

59nums[i] = nums[j];

60nums[j] = temp;

61}
Algorithm description viewbox

Find Kth Largest Element in an Unsorted Array

Algorithm description:

This function finds the k-th largest element in an unsorted list of integers using the QuickSelect algorithm. QuickSelect is a selection algorithm that finds the k-th smallest (or largest) element in an unordered list. It is related to the QuickSort sorting algorithm. A common use case is in competitive programming or scenarios where you need to efficiently find a specific order statistic without fully sorting the entire list.

Algorithm explanation:

The QuickSelect algorithm works by recursively partitioning the input list. It's a modification of QuickSort. The core idea is to pick a pivot element and partition the array around it, such that all elements smaller than the pivot are to its left, and all elements greater are to its right. After partitioning, if the pivot's index is exactly k (or n-k for k-th largest), we've found our element. If k is smaller than the pivot's index, we recurse on the left subarray; otherwise, we recurse on the right. This process has an average time complexity of O(n), where n is the number of elements in the list, because on average, we discard about half of the remaining elements in each recursive step. In the worst case, if the pivot is always chosen poorly (e.g., the smallest or largest element), the complexity can degrade to O(n^2). The space complexity is O(log n) on average due to recursion stack depth, and O(n) in the worst case. Edge cases include an empty list, k being out of bounds (less than 1 or greater than list length), and lists with duplicate elements. The correctness relies on the partition step correctly placing the pivot and the recursive calls narrowing down the search space effectively.

Pseudocode:

function findKthLargest(nums, k):
  if nums is empty or k is invalid:
    throw error
  targetIndex = nums.length - k
  return quickSelect(nums, 0, nums.length - 1, targetIndex)

function quickSelect(nums, left, right, kSmallestIndex):
  if left == right:
    return nums[left]

  pivotIndex = choose_pivot(nums, left, right)
  pivotIndex = partition(nums, left, right, pivotIndex)

  if kSmallestIndex == pivotIndex:
    return nums[kSmallestIndex]
  else if kSmallestIndex < pivotIndex:
    return quickSelect(nums, left, pivotIndex - 1, kSmallestIndex)
  else:
    return quickSelect(nums, pivotIndex + 1, right, kSmallestIndex)

function partition(nums, left, right, pivotIndex):
  pivotValue = nums[pivotIndex]
  swap(nums, pivotIndex, right)
  storeIndex = left
  for i from left to right - 1:
    if nums[i] < pivotValue:
      swap(nums, storeIndex, i)
      storeIndex = storeIndex + 1
  swap(nums, storeIndex, right)
  return storeIndex

function swap(nums, i, j):
  temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp