# Problem Understanding\n\nIn the "Kth Largest Element in an Array" problem, we are provided with an array of integers `nums` and an integer `k`. The objective is to determine the `k`th largest element in this array.\n\nFor example, with the array `nums = [3,2,1,5,6,4]` and `k = 2`, the expected answer is `5` since `5` is the second largest element in the array.\n\n---\n\n# Approaches to Finding the k-th Largest Element\n\nFinding the $$k$$-th largest element in an array is a classic problem in computer science, and over the years, multiple algorithms and techniques have been developed to tackle it efficiently. Let\'s explore three of these approaches:\n\n## **Approach 1/3: Sort and Select**\nThe most intuitive method, this approach involves sorting the entire array in descending order and then simply picking the $$k$$-th element. Though straightforward, it may not be the most efficient for very large arrays due to the sorting step.\n\n![sort_per.png](https://assets.leetcode.com/users/images/8dcc67a2-2321-4bca-b302-c2ea6fdf1fdf_1691975899.2193816.png)\n\n### Live Coding & Explenation - Sort and Select\nhttps://youtu.be/yiUjLay-ocI\n\n## **Approach 2/3: Min-Heap**\nRather than sorting the entire array, this method utilizes a min-heap to maintain the $$k$$-th largest elements. The heap allows us to efficiently compare each new element with the smallest of the $$k$$-th largest elements seen so far. By the end of the iteration, the top of the heap will contain our desired $$k$$-th largest element.\n\n![heap_apr.png](https://assets.leetcode.com/users/images/ccfd16f0-c9dc-4fb4-afb4-bf6b48442c83_1691976313.6851792.png)\n\n### Live Coding & Explenation - Min-Heap\nhttps://youtu.be/h3GivLJBUTk\n\n## **Approach 3/3: QuickSelect Algorithm**\nInspired by the QuickSort algorithm, QuickSelect is a divide-and-conquer technique. It partitions the array around a pivot and recursively searches for the $$k$$-th largest element in the appropriate partition. When the pivot is chosen randomly, the algorithm tends to have a linear average-case time complexity, making it faster than the sorting approach for large datasets.\n\n![qs2.png](https://assets.leetcode.com/users/images/bc5ab983-34a4-4d23-9e32-5cf0474483de_1691978591.9641573.png)\n\n### Live Coding & Explenation - QuickSelect\nhttps://youtu.be/q6A3_mTixvE\n\n## Comparison of Tree Approaches across Languages\n\nThe bar chart below provides a comparative analysis of the runtime performance of three different algorithms \u2013 the Sorting Approach, Min Heap Approach, and the QuickSelect Approach \u2013 across seven popular programming languages. Each language\'s performance is measured in milliseconds (ms) for each approach, with lower values indicating faster execution times.\n\n![3n.png](https://assets.leetcode.com/users/images/6741bc59-2cea-46bb-9a4c-e08687d09064_1691978724.4083834.png)\n\n---\n\n# Approaches\n\nEach of these approaches has its own strengths and trade-offs. Depending on the specific scenario, constraints, and size of the input, one might be more suitable than the others. It\'s always beneficial to have multiple tools (approaches) in your algorithmic toolbox!\n\n# Approach 1/3: Sort and Select\n\nThis approach is quite straightforward: sort the numbers in descending order and pick the $$k$$-th element.\n\n## Key Data Structures:\n- **List/Array**: We use Python\'s built-in list for this approach. The list is sorted in descending order to get the $$k$$-th largest element.\n\n## Step-by-step Breakdown:\n\n1. **Initialization**:\n - Use built-in `sorted` function to sort the list `nums` in reverse order (i.e., in descending order).\n \n2. **Selection**:\n - Select the $$k$$-th element from the sorted list (keeping in mind the zero-based indexing of lists).\n\n3. **Result**:\n - The $$k$$-th element in the sorted list is the $$k$$-th largest element in the original list.\n\n# Complexity:\n\n**Time Complexity:** $$O(N \\log N)$$\n- Sorting a list of $$N$$ elements requires $$O(N \\log N)$$ time.\n\n**Space Complexity:** $$O(1)$$\n- The space used is constant since we are only sorting the original list and selecting an element from it without utilizing any additional data structures.\n\n# Performance:\n\nThis solution is simple and works effectively for smaller lists. However, for very large lists, other approaches that avoid sorting the entire list might be more efficient.\n\n| Language | Runtime (ms) | Runtime Beat (%) | Memory (MB) | Memory Beat (%) |\n|------------|--------------|------------------|-------------|-----------------|\n| **Java** | 22 | 88.35% | 54.2 | 79.52% |\n| **Rust** | 25 | 21.43% | 3.4 | 5.61% |\n| **C++** | 74 | 96.10% | 45.6 | 74.16% |\n| **Go** | 101 | 51.2% | 7.9 | 85.3% |\n| **JavaScript** | 143 | 60.17% | 51.5 | 56.57% |\n| **C#** | 164 | 85.88% | 51.1 | 41.99% |\n| **Python3** | 410 | 98.33% | 29.5 | 72.41% |\n\n# Code 1/3\n\n``` Python []\nclass Solution:\n def findKthLargest(self, nums, k):\n return sorted(nums, reverse=True)[k-1]\n```\n``` C++ []\nclass Solution {\npublic:\n int findKthLargest(std::vector& nums, int k) {\n std::sort(nums.begin(), nums.end(), std::greater());\n return nums[k-1];\n }\n};\n```\n``` Java []\npublic class Solution {\n public int findKthLargest(int[] nums, int k) {\n Arrays.sort(nums);\n return nums[nums.length - k];\n }\n}\n```\n``` Rust []\nimpl Solution {\n pub fn find_kth_largest(nums: Vec, k: i32) -> i32 {\n let mut sorted_nums = nums.clone();\n sorted_nums.sort();\n sorted_nums[(nums.len() - k as usize)]\n }\n}\n```\n``` Go []\nimport "sort"\n\nfunc findKthLargest(nums []int, k int) int {\n sort.Ints(nums)\n return nums[len(nums)-k]\n}\n```\n``` JavaScript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar findKthLargest = function(nums, k) {\n nums.sort((a, b) => b - a);\n return nums[k-1];\n};\n```\n``` C# []\npublic class Solution {\n public int FindKthLargest(int[] nums, int k) {\n Array.Sort(nums);\n return nums[nums.Length - k];\n }\n}\n```\n---\n\n# Approach 2/3: Min-Heap\n\nThe main idea of this solution is to use a min-heap with a maximum size of `k`. By doing this, we ensure that the smallest of the `k` largest elements is always on the top of the heap.\n\n## Key Data Structures:\n\n- **`heap`**:\n This is a min-heap containing the first `k` elements of `nums`. As we progress, we will modify this heap to ensure it contains the `k` largest elements.\n\n### Step-by-step Breakdown:\n\n1. **Initialization**:\n - Create a heap with the first `k` elements of `nums`.\n - Transform this list into a min-heap.\n\n2. **Iterate through the List**:\n - For each of the remaining elements in `nums`:\n - If the element is larger than the smallest element in the heap (i.e., the top of the heap):\n - Remove the top element from the heap.\n - Insert the current element into the heap.\n\n3. **Result**:\n - After processing all elements in `nums`, the top of the heap will contain the `k`th largest element. Return this element.\n\n# Example:\n\nConsider the list `nums = [3,2,1,5,6,4]` with `k = 2`.\n\nHere\'s the evolution of the `heap`:\n\n**Initial State**:\n- `heap`: [3,2]\n\n**After processing index 2 (element = 1)**:\n- `heap` remains unchanged as `1` is not larger than `2`.\n\n**After processing index 3 (element = 5)**:\n- `heap`: [3,5]\n\n**After processing index 4 (element = 6)**:\n- `heap`: [5,6]\n\n**After processing index 5 (element = 4)**:\n- `heap`: [5,6]\n\nThe final state of the `heap` shows that the `k`th largest element is `5`.\n\n# Complexity\n\n**Time Complexity:** $$O(n \\log k)$$\nEach of the `n` elements is processed once. However, heap operations take $$O(\\log k)$$ time, leading to an overall complexity of $$O(n \\log k)$$.\n\n**Space Complexity:** $$O(k)$$\nThe solution uses a heap with a maximum of `k` elements.\n\n# Performance\n\nThis solution is both time and space-efficient. By focusing only on the `k` largest elements and using the properties of a heap, it ensures optimal runtime for a wide range of inputs. The controlled space usage ensures that even for large `k`, the memory overhead remains minimal.\n\n| Language | Runtime (ms) | Runtime Beat (%) | Memory (MB) | Memory Beat (%) |\n|------------|--------------|------------------|-------------|-----------------|\n| **Rust** | 13 | 77.55% | 3.1 | 46.94% |\n| **Java** | 37 | 59.27% | 54.1 | 86.2% |\n| **C++** | 76 | 94.84% | 46.5 | 68.16% |\n| **Go** | 91 | 62.6% | 8.6 | 30.67% |\n| **JavaScript** | 98 | 87.2% | 51.7 | 47.64% |\n| **C#** | 152 | 95.49% | 51.7 | 16.25% |\n| **Python3** | 407 | 98.75% | 29.5 | 72.41% |\n\n# Code\n``` Python []\nclass Solution:\n def findKthLargest(self, nums: List[int], k: int) -> int:\n heap = nums[:k]\n heapq.heapify(heap)\n \n for num in nums[k:]:\n if num > heap[0]:\n heapq.heappop(heap)\n heapq.heappush(heap, num)\n \n return heap[0]\n```\n``` C++ []\nclass Solution {\npublic:\n int findKthLargest(std::vector& nums, int k) {\n std::priority_queue, std::greater> min_heap(nums.begin(), nums.begin() + k);\n \n for (int i = k; i < nums.size(); i++) {\n if (nums[i] > min_heap.top()) {\n min_heap.pop();\n min_heap.push(nums[i]);\n }\n }\n \n return min_heap.top();\n }\n};\n```\n``` Rust []\nuse std::collections::BinaryHeap;\nuse std::cmp::Reverse;\n\nimpl Solution {\n pub fn find_kth_largest(nums: Vec, k: i32) -> i32 {\n let mut heap: BinaryHeap> = nums.iter().take(k as usize).map(|&x| Reverse(x)).collect();\n \n for &num in nums.iter().skip(k as usize) {\n if num > heap.peek().unwrap().0 {\n heap.pop();\n heap.push(Reverse(num));\n }\n }\n \n heap.peek().unwrap().0\n }\n}\n```\n``` Go []\nimport "container/heap"\n\nfunc findKthLargest(nums []int, k int) int {\n h := IntHeap(nums[:k])\n heap.Init(&h)\n \n for _, num := range nums[k:] {\n if num > h[0] {\n heap.Pop(&h)\n heap.Push(&h, num)\n }\n }\n \n return h[0]\n}\n\ntype IntHeap []int\n\nfunc (h IntHeap) Len() int { return len(h) }\nfunc (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }\nfunc (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }\n\nfunc (h *IntHeap) Push(x interface{}) {\n *h = append(*h, x.(int))\n}\n\nfunc (h *IntHeap) Pop() interface{} {\n old := *h\n n := len(old)\n x := old[n-1]\n *h = old[0 : n-1]\n return x\n}\n```\n``` Java []\npublic class Solution {\n public int findKthLargest(int[] nums, int k) {\n PriorityQueue minHeap = new PriorityQueue<>();\n for (int i = 0; i < k; i++) {\n minHeap.offer(nums[i]);\n }\n \n for (int i = k; i < nums.length; i++) {\n if (nums[i] > minHeap.peek()) {\n minHeap.poll();\n minHeap.offer(nums[i]);\n }\n }\n \n return minHeap.peek();\n }\n}\n```\n``` JavaScript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\n class MinHeap {\n constructor() {\n this.heap = [];\n }\n push(val) {\n this.heap.push(val);\n this.bubbleUp();\n }\n pop() {\n const max = this.heap[0];\n const end = this.heap.pop();\n if (this.heap.length > 0) {\n this.heap[0] = end;\n this.bubbleDown();\n }\n return max;\n }\n peek() {\n return this.heap[0];\n }\n bubbleUp() {\n let idx = this.heap.length - 1;\n const element = this.heap[idx];\n while (idx > 0) {\n let parentIdx = Math.floor((idx - 1) / 2);\n let parent = this.heap[parentIdx];\n if (element >= parent) break;\n this.heap[parentIdx] = element;\n this.heap[idx] = parent;\n idx = parentIdx;\n }\n }\n bubbleDown() {\n let idx = 0;\n const length = this.heap.length;\n const element = this.heap[0];\n while (true) {\n let leftChildIdx = 2 * idx + 1;\n let rightChildIdx = 2 * idx + 2;\n let leftChild, rightChild;\n let swap = null;\n if (leftChildIdx < length) {\n leftChild = this.heap[leftChildIdx];\n if (leftChild < element) {\n swap = leftChildIdx;\n }\n }\n if (rightChildIdx < length) {\n rightChild = this.heap[rightChildIdx];\n if (\n (swap === null && rightChild < element) || \n (swap !== null && rightChild < leftChild)\n ) {\n swap = rightChildIdx;\n }\n }\n if (swap === null) break;\n this.heap[idx] = this.heap[swap];\n this.heap[swap] = element;\n idx = swap;\n }\n }\n}\nvar findKthLargest = function(nums, k) {\n let heap = new MinHeap();\n for (let i = 0; i < k; i++) {\n heap.push(nums[i]);\n }\n for (let i = k; i < nums.length; i++) {\n if (nums[i] > heap.peek()) {\n heap.pop();\n heap.push(nums[i]);\n }\n }\n return heap.peek();\n};\n```\n``` C# []\npublic class Solution {\n public int FindKthLargest(int[] nums, int k) {\n MinHeap minHeap = new MinHeap(k);\n for (int i = 0; i < k; i++) {\n minHeap.Insert(nums[i]);\n }\n \n for (int i = k; i < nums.Length; i++) {\n if (nums[i] > minHeap.Peek()) {\n minHeap.Pop();\n minHeap.Insert(nums[i]);\n }\n }\n \n return minHeap.Peek();\n }\n}\n\npublic class MinHeap {\n private int[] heap;\n private int size;\n\n public MinHeap(int capacity) {\n heap = new int[capacity];\n size = 0;\n }\n\n public void Insert(int val) {\n heap[size] = val;\n size++;\n BubbleUp();\n }\n\n public int Peek() {\n return heap[0];\n }\n\n public int Pop() {\n int poppedValue = heap[0];\n heap[0] = heap[size - 1];\n size--;\n BubbleDown();\n return poppedValue;\n }\n\n private void BubbleUp() {\n int index = size - 1;\n while (index > 0 && heap[index] < heap[Parent(index)]) {\n Swap(index, Parent(index));\n index = Parent(index);\n }\n }\n\n private void BubbleDown() {\n int index = 0;\n while (HasLeftChild(index) && (heap[index] > LeftChild(index) || HasRightChild(index) && heap[index] > RightChild(index))) {\n int smallerChildIndex = LeftChildIndex(index);\n if (HasRightChild(index) && RightChild(index) < LeftChild(index)) {\n smallerChildIndex = RightChildIndex(index);\n }\n Swap(index, smallerChildIndex);\n index = smallerChildIndex;\n }\n }\n\n private int Parent(int index) { return (index - 1) / 2; }\n private int LeftChildIndex(int index) { return 2 * index + 1; }\n private int RightChildIndex(int index) { return 2 * index + 2; }\n\n private bool HasLeftChild(int index) { return LeftChildIndex(index) < size; }\n private bool HasRightChild(int index) { return RightChildIndex(index) < size; }\n\n private int LeftChild(int index) { return heap[LeftChildIndex(index)]; }\n private int RightChild(int index) { return heap[RightChildIndex(index)]; }\n\n private void Swap(int indexOne, int indexTwo) {\n int temp = heap[indexOne];\n heap[indexOne] = heap[indexTwo];\n heap[indexTwo] = temp;\n }\n}\n```\n\n---\n\n\n# Approach 3/3: QuickSelect Algorithm\n\nThe QuickSelect algorithm is an efficient method to find the $$k$$-th smallest (or largest) element in an unordered list without sorting the entire list. It works similarly to the QuickSort algorithm but only recurses into one half of the data.\n\n## Key Data Structures:\n\n- **List/Array**: We use Python\'s built-in list for this approach. The algorithm modifies the list in place.\n- **Pivot**: An element chosen from the list, around which the list gets partitioned.\n\n## Step-by-step Breakdown:\n\n1. **Initialization**:\n - Set the `left` boundary to the beginning of the list and the `right` boundary to the end of the list.\n\n2. **Pivot Selection**:\n - Randomly select a pivot index between the `left` and `right` boundaries.\n\n3. **Partitioning**:\n - Move all elements smaller than the pivot to its left and all larger elements to its right.\n - Return the final position of the pivot after the partitioning.\n\n4. **Check Pivot Position**:\n - If the position of the pivot is the desired $$k$$-th largest index, return the pivot.\n - If the pivot\'s position is greater than the desired index, adjust the `right` boundary and repeat.\n - If the pivot\'s position is lesser than the desired index, adjust the `left` boundary and repeat.\n\n5. **Result**:\n - The function will eventually return the $$k$$-th largest element in the original list.\n\n# Example:\n\nLet\'s walk through the QuickSelect algorithm using the list `nums = [3,2,1,5,6,4]` and \$ k = 2 \$ to find the 2nd largest element.\n\n**Initial List:** \n`[3,2,1,5,6,4]`\n\n1. **Iteration 1:** \n - Chosen pivot: `3` (at index 0)\n - After partitioning, the list becomes: `[2, 1, 3, 5, 6, 4]`\n - The new pivot index is 2. Since we\'re looking for the 2nd largest element (index 4 in 0-indexed list), and the current pivot index is less than this, we know the desired element is to the right of the current pivot.\n \n2. **Iteration 2:**\n - Chosen pivot: `6` (at index 4)\n - After partitioning, the list becomes: `[2, 1, 3, 4, 5, 6]`\n - The new pivot index is 4, which matches our target index for the 2nd largest element.\n \n**Result:** \nThe 2nd largest element in the list is `5`.\n\nThis example demonstrates the behavior of the QuickSelect algorithm. By iteratively selecting a pivot and partitioning the list around that pivot, it efficiently narrows down the search space until it locates the kth largest element.\n\n# Complexity:\n\n**Time Complexity**: \n- Best and Average Case: $$O(N)$$\n- Worst Case: $$O(N^2)$$\n \n The average performance is linear. However, in the worst case (very rare, especially with randomized pivot), the algorithm can degrade to $$O(N^2)$$.\n\n**Space Complexity**: $$O(1)$$\n- The space used is constant. The algorithm modifies the original list in place and doesn\'t utilize any significant additional data structures. The recursive stack calls (in the worst case) are also bounded by the depth of the list, making it $$O(\\log N)$$, but this is typically considered as $$O(1)$$ space complexity in QuickSelect.\n\n# Performance:\n\nThis solution is efficient for larger lists, especially when the pivot is chosen randomly, which greatly reduces the chance of the worst-case scenario. The QuickSelect algorithm allows for finding the desired element without sorting the entire list, making it faster than the sorting approach for large datasets.\n\n| Language | Runtime (ms) | Runtime Beat (%) | Memory (MB) | Memory Beat (%) |\n|------------|--------------|------------------|-------------|-----------------|\n| **Java** | 4 | 97.78% | 54.2 | 79.52% |\n| **Rust** | 12 | 83.16% | 3.4 | 5.61% |\n| **Go** | 56 | 100% | 8.3 | 46.37% |\n| **C++** | 63 | 98.85% | 45.5 | 86.52% |\n| **JavaScript** | 80 | 94.94% | 51.8 | 38.99% |\n| **C#** | 146 | 98.46% | 50.6 | 90.98% |\n| **Python3** | 427 | 94.80% | 29.6 | 55.40% |\n\n# Code 3/3\n``` Python []\nclass Solution:\n def findKthLargest(self, nums, k):\n left, right = 0, len(nums) - 1\n while True:\n pivot_index = random.randint(left, right)\n new_pivot_index = self.partition(nums, left, right, pivot_index)\n if new_pivot_index == len(nums) - k:\n return nums[new_pivot_index]\n elif new_pivot_index > len(nums) - k:\n right = new_pivot_index - 1\n else:\n left = new_pivot_index + 1\n\n def partition(self, nums, left, right, pivot_index):\n pivot = nums[pivot_index]\n nums[pivot_index], nums[right] = nums[right], nums[pivot_index]\n stored_index = left\n for i in range(left, right):\n if nums[i] < pivot:\n nums[i], nums[stored_index] = nums[stored_index], nums[i]\n stored_index += 1\n nums[right], nums[stored_index] = nums[stored_index], nums[right]\n return stored_index\n```\n``` C++ []\nclass Solution {\npublic:\n int findKthLargest(std::vector& nums, int k) {\n int left = 0, right = nums.size() - 1;\n while (true) {\n int pivot_index = rand() % (right - left + 1) + left;\n int new_pivot_index = partition(nums, left, right, pivot_index);\n if (new_pivot_index == nums.size() - k) {\n return nums[new_pivot_index];\n } else if (new_pivot_index > nums.size() - k) {\n right = new_pivot_index - 1;\n } else {\n left = new_pivot_index + 1;\n }\n }\n }\n\nprivate:\n int partition(std::vector& nums, int left, int right, int pivot_index) {\n int pivot = nums[pivot_index];\n std::swap(nums[pivot_index], nums[right]);\n int stored_index = left;\n for (int i = left; i < right; i++) {\n if (nums[i] < pivot) {\n std::swap(nums[i], nums[stored_index]);\n stored_index++;\n }\n }\n std::swap(nums[right], nums[stored_index]);\n return stored_index;\n }\n};\n```\n``` Rust []\nuse rand::Rng;\n\nimpl Solution {\n pub fn find_kth_largest(nums: Vec, k: i32) -> i32 {\n let mut nums = nums;\n let mut left = 0;\n let mut right = nums.len() - 1;\n let mut rng = rand::thread_rng();\n loop {\n let pivot_index = rng.gen_range(left, right + 1);\n let new_pivot_index = Self::partition(&mut nums, left, right, pivot_index);\n if new_pivot_index == nums.len() - k as usize {\n return nums[new_pivot_index];\n } else if new_pivot_index > nums.len() - k as usize {\n right = new_pivot_index - 1;\n } else {\n left = new_pivot_index + 1;\n }\n }\n }\n\n fn partition(nums: &mut Vec, left: usize, right: usize, pivot_index: usize) -> usize {\n let pivot = nums[pivot_index];\n nums.swap(pivot_index, right);\n let mut stored_index = left;\n for i in left..right {\n if nums[i] < pivot {\n nums.swap(i, stored_index);\n stored_index += 1;\n }\n }\n nums.swap(right, stored_index);\n stored_index\n }\n}\n```\n``` Go []\nimport (\n\t"math/rand"\n)\n\nfunc findKthLargest(nums []int, k int) int {\n\tleft, right := 0, len(nums)-1\n\tfor {\n\t\tpivotIndex := left + rand.Intn(right-left+1)\n\t\tnewPivotIndex := partition(nums, left, right, pivotIndex)\n\t\tif newPivotIndex == len(nums)-k {\n\t\t\treturn nums[newPivotIndex]\n\t\t} else if newPivotIndex > len(nums)-k {\n\t\t\tright = newPivotIndex - 1\n\t\t} else {\n\t\t\tleft = newPivotIndex + 1\n\t\t}\n\t}\n}\n\nfunc partition(nums []int, left int, right int, pivotIndex int) int {\n\tpivot := nums[pivotIndex]\n\tnums[pivotIndex], nums[right] = nums[right], nums[pivotIndex]\n\tstoredIndex := left\n\tfor i := left; i < right; i++ {\n\t\tif nums[i] < pivot {\n\t\t\tnums[i], nums[storedIndex] = nums[storedIndex], nums[i]\n\t\t\tstoredIndex++\n\t\t}\n\t}\n\tnums[right], nums[storedIndex] = nums[storedIndex], nums[right]\n\treturn storedIndex\n}\n```\n``` Java []\npublic class Solution {\n public int findKthLargest(int[] nums, int k) {\n int left = 0, right = nums.length - 1;\n Random rand = new Random();\n while (true) {\n int pivot_index = left + rand.nextInt(right - left + 1);\n int new_pivot_index = partition(nums, left, right, pivot_index);\n if (new_pivot_index == nums.length - k) {\n return nums[new_pivot_index];\n } else if (new_pivot_index > nums.length - k) {\n right = new_pivot_index - 1;\n } else {\n left = new_pivot_index + 1;\n }\n }\n }\n\n private int partition(int[] nums, int left, int right, int pivot_index) {\n int pivot = nums[pivot_index];\n swap(nums, pivot_index, right);\n int stored_index = left;\n for (int i = left; i < right; i++) {\n if (nums[i] < pivot) {\n swap(nums, i, stored_index);\n stored_index++;\n }\n }\n swap(nums, right, stored_index);\n return stored_index;\n }\n\n private void swap(int[] nums, int i, int j) {\n int temp = nums[i];\n nums[i] = nums[j];\n nums[j] = temp;\n }\n}\n```\n``` JavaScript []\n/**\n * @param {number[]} nums\n * @param {number} k\n * @return {number}\n */\nvar findKthLargest = function(nums, k) {\n const partition = (left, right, pivotIndex) => {\n const pivot = nums[pivotIndex];\n [nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];\n let storedIndex = left;\n for (let i = left; i < right; i++) {\n if (nums[i] < pivot) {\n [nums[storedIndex], nums[i]] = [nums[i], nums[storedIndex]];\n storedIndex++;\n }\n }\n [nums[right], nums[storedIndex]] = [nums[storedIndex], nums[right]];\n return storedIndex;\n };\n \n let left = 0, right = nums.length - 1;\n while (true) {\n const pivotIndex = left + Math.floor(Math.random() * (right - left + 1));\n const newPivotIndex = partition(left, right, pivotIndex);\n if (newPivotIndex === nums.length - k) {\n return nums[newPivotIndex];\n } else if (newPivotIndex > nums.length - k) {\n right = newPivotIndex - 1;\n } else {\n left = newPivotIndex + 1;\n }\n }\n};\n```\n``` C# []\npublic class Solution {\n public int FindKthLargest(int[] nums, int k) {\n int left = 0, right = nums.Length - 1;\n Random rand = new Random();\n while (true) {\n int pivot_index = left + rand.Next(right - left + 1);\n int new_pivot_index = Partition(nums, left, right, pivot_index);\n if (new_pivot_index == nums.Length - k) {\n return nums[new_pivot_index];\n } else if (new_pivot_index > nums.Length - k) {\n right = new_pivot_index - 1;\n } else {\n left = new_pivot_index + 1;\n }\n }\n }\n\n private int Partition(int[] nums, int left, int right, int pivot_index) {\n int pivot = nums[pivot_index];\n Swap(nums, pivot_index, right);\n int stored_index = left;\n for (int i = left; i < right; i++) {\n if (nums[i] < pivot) {\n Swap(nums, i, stored_index);\n stored_index++;\n }\n }\n Swap(nums, right, stored_index);\n return stored_index;\n }\n\n private void Swap(int[] nums, int i, int j) {\n int temp = nums[i];\n nums[i] = nums[j];\n nums[j] = temp;\n }\n}\n```\n\nIn the dynamic world of algorithms, there\'s no \'one-size-fits-all\'. Each solution we\'ve explored offers unique strengths and comes with its own set of trade-offs. Some shine brightest with smaller inputs, while others stand resilient in the face of massive datasets. The beauty lies in understanding and judiciously applying them based on the constraints and requirements at hand.\n\nRemember, every challenge you face is an opportunity to apply and expand your understanding. By mastering multiple approaches, you not only diversify your algorithmic toolbox but also enhance your adaptability in solving real-world problems. Keep pushing the boundaries, keep exploring, and most importantly, keep coding! The journey of algorithms is vast and rewarding, and every problem you solve is a stepping stone towards becoming a more skilled and confident coder. Embrace the learning, and let the world of algorithms inspire and empower you!

Kth Largest Element in an Array

Problem Description

Problem Description

Answer Panel