1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/**
 * Sorting Approach
 * Time Complexity: O(n log n) - Dominated by the sorting operation
 * Space Complexity: O(1) - Assuming in-place sort
 * 
 * @param {number[]} nums - Array of numbers
 * @param {number} k - Position of the element to find
 * @return {number} - The kth largest element
 */
function findKthLargestSorting(nums, k) {
  // Sort the array in descending order
  nums.sort((a, b) => b - a);
  
  // Return the kth largest element
  return nums[k - 1];
}
 
/**
 * Min Heap Approach
 * Time Complexity: O(n log k) - Where n is the length of the array
 * Space Complexity: O(k) - For storing the heap of size k
 * 
 * Note: JavaScript doesn't have a built-in heap, so we'll implement a simple min heap
 * 
 * @param {number[]} nums - Array of numbers
 * @param {number} k - Position of the element to find
 * @return {number} - The kth largest element
 */
function findKthLargestMinHeap(nums, k) {
  // Create a min heap of size k
  const heap = [];
  
  // Helper function to maintain heap property
  const heapify = (i) => {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let smallest = i;
    
    if (left < heap.length && heap[left] < heap[smallest]) {
      smallest = left;
    }
    
    if (right < heap.length && heap[right] < heap[smallest]) {
      smallest = right;
    }
    
    if (smallest !== i) {
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      heapify(smallest);
    }
  };
  
  // Add element to heap
  const addToHeap = (num) => {
    heap.push(num);
    let i = heap.length - 1;
    let parent = Math.floor((i - 1) / 2);
    
    while (i > 0 && heap[i] < heap[parent]) {
      [heap[i], heap[parent]] = [heap[parent], heap[i]];
      i = parent;
      parent = Math.floor((i - 1) / 2);
    }
  };
  
  // Remove top element from heap
  const pollFromHeap = () => {
    const top = heap[0];
    heap[0] = heap[heap.length - 1];
    heap.pop();
    heapify(0);
    return top;
  };
  
  // Process all elements
  for (const num of nums) {
    addToHeap(num);
    
    if (heap.length > k) {
      pollFromHeap();
    }
  }
  
  // Return the top of the heap (the kth largest element)
  return heap[0];
}
 
/**
 * QuickSelect Approach
 * Time Complexity: O(n) average, O(n²) worst case
 * Space Complexity: O(1) - In-place partitioning
 * 
 * @param {number[]} nums - Array of numbers
 * @param {number} k - Position of the element to find
 * @return {number} - The kth largest element
 */
function findKthLargest(nums, k) {
  // QuickSelect algorithm
  return quickSelect(nums, 0, nums.length - 1, k - 1);
}
 
function quickSelect(nums, left, right, k) {
  if (left === right) {
    return nums[left];
  }
  
  // Choose pivot (rightmost element)
  const pivotIndex = partition(nums, left, right);
  
  if (pivotIndex === k) {
    return nums[pivotIndex];
  } else if (pivotIndex < k) {
    return quickSelect(nums, pivotIndex + 1, right, k);
  } else {
    return quickSelect(nums, left, pivotIndex - 1, k);
  }
}
 
function partition(nums, left, right) {
  // Choose pivot (rightmost element)
  const pivot = nums[right];
  let i = left;
  
  // Partition around pivot
  for (let j = left; j < right; j++) {
    if (nums[j] >= pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  
  // Place pivot in its final position
  [nums[i], nums[right]] = [nums[right], nums[i]];
  return i;
}
 
// Test cases
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4