215. Kth Largest Element in an Array
Problem Description
The given problem presents us with a scenario where we need to find the k(^{th}) largest element in a provided integer array nums
. Unlike finding the maximum or minimum element, this task requires us to identify the value that would be placed at the k(^{th}) largest position if the array were sorted. However, the twist in this problem is that duplicates are allowed, and each instance counts for the position. For example, if nums = [3,2,3,1,2,4,5,5,6]
and k = 4
, the fourth largest element is 4
.
Moreover, the problem poses an additional challenge: it hints at the possibility of finding the solution without sorting the entire array, which might suggest that there are more optimal ways to solve this especially when we consider time complexity.
Intuition
To solve this problem within the constraint of not fully sorting the array, we can draw on strategies from the concept of Quick Select, which is a selection algorithm based on the partitioning logic of Quick Sort.
Quick Sort operates by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The pivotal insight here is that once we position a pivot during partitioning, its final sorted position is fixed in the array.
We use this characteristic of Quick Sort to our advantage. By performing partitioning, if we position a pivot at index p, and p is the n-k
position in a 0-indexed array (the position where our kth largest element would be if the array were sorted in ascending order), then we have our answer: the element at index p. If p is less than n-k
, it implies the kth largest element is to the right, so we only need to partition the sub-array to the right of p. Conversely, if p is larger than n-k
, we only need to partition to the left of p.
Using this approach, the algorithm short-circuits the sorting process, only partially sorting the elements around the k
(^{th}) largest value until it is positioned correctly. In the best case, this results in linear time complexity, although in the worst case (which can be mitigated by good pivot selection), it can reach quadratic complexityāit's still generally more optimal than fully sorting the array.
Learn more about Divide and Conquer, Sorting and Heap (Priority Queue) patterns.
Solution Approach
To implement the solution based on the intuition described earlier, the Reference Solution Approach uses the Quick Select algorithm, which is inspired by the partition process of Quick Sort.
Here's a step-by-step explanation of the algorithm in the given solution:
- Define a helper function
quick_sort
which will handle the partitioning and the recursive search. - Within
quick_sort
, calculate a pivot valuex
as the element in the middle index ofnums
āthis is computed asnums[(left + right) >> 1]
where>> 1
is a bit-shift operation equivalent to integer division by 2. This pivot is arbitrary, and different selection methods can be used to optimize the algorithm. - Set two pointers,
i
starting from the left boundleft - 1
andj
from the right boundright + 1
. Then incrementi
and decrementj
until an element greater than or equal tox
is found from the left and an element less than or equal tox
is found from the right. - If
i < j
which means elements are on the wrong side of the pivot, swap them. Repeat this process untili
is not less thanj
. - After the loop,
j
will be at the partition point. Ifj
is less than the index we're interested in (k
), we know our kth largest element is on the right ofj
hence callquick_sort
recursively for the right sub-array. - If
j
is greater or equal tok
, the kth largest element is on the left side or atj
. - Invoke this helper function with the entirety of the input array's bounds and
n - k
as the target position, starting the process.
The algorithm's success hinges on the partitioning step, which ensures that after each pass, at least one element (the pivot) is in its final sorted position. By targeting the n - k
index, we aim to put the kth largest element (which is the k
th from the last in sorted order) in its correct position.
To visualize this algorithm with an example, let's consider nums = [3,2,1,5,6,4]
and k = 2
. The steps would be:
- Pick a pivot (let's say it's
3
). - After one partitioning step, the array could look like
[2, 1, 3, 5, 6, 4]
. 3
is now in its correct sorted position (index 2). We're looking for the index4
(n - k
), which is to the right of our pivot. Therefore, we'll now focus on the sub-array[5, 6, 4]
.- The algorithm will then repeat these steps on the sub-array until the element at the
n-k
place is positioned correctly, at which point it will return as the kth largest element.
By performing this targeted partitioning, we avoid the need to sort the entire array, which gives us a quicker path to the desired kth largest element.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. We will use the array nums = [3, 2, 1, 5, 6, 4]
and k = 2
, meaning we want to find the 2nd largest element.
- We need to find the
n-k
th element in the sorted order, which translates to6 - 2 = 4
in 1-indexed or3
in 0-indexed notation in our array. - We pick a pivot, let's use the median value of
3
as an example. Thequick_sort
function is then called with the entire array along with indices of the bounds0
and5
. - Partition the array around the pivot
3
. One possible way the array could be partitioned is[2, 1, 3, 5, 6, 4]
. After partitioning, the pivot3
is positioned at its correct sorted index2
. - Since our target index
3
is greater than the pivot's index2
, we ignore the left part of the array including our pivot, and focus on the right part:[5, 6, 4]
. - We repeat the process on this sub-array. We pick a new pivot, say
5
. Partitioning this sub-array might result in[4, 5, 6]
. - The pivot
5
lands at index1
of the sub-array (4
in the original array, due to0
-indexing). Now the position of5
is the same as our target index4
(n-k
), which means it's thek
th largest element.
The second-largest element in this array is 5
, and thus is the output of our algorithm using Quick Select. This process saved time by not having to sort the whole array and instead focused on finding the specific k
th element directly.
Solution Implementation
1class Solution:
2 def findKthLargest(self, nums: List[int], k: int) -> int:
3 # Helper method to perform the quickselect algorithm
4 def quick_select(start, end, k_smallest):
5 # If the list contains only one element,
6 # return that element
7 if start == end:
8 return nums[start]
9 pivot_index = (start + end) // 2 # Choose the middle element as the pivot
10 pivot_value = nums[pivot_index]
11 left, right = start - 1, end + 1
12
13 # Partition the list such that all elements greater than
14 # the pivot are to the left and all elements less than
15 # are to the right
16 while left < right:
17 # Increment left index until finding an element less than the pivot
18 while True:
19 left += 1
20 if nums[left] >= pivot_value:
21 break
22 # Decrement right index until finding an element greater than the pivot
23 while True:
24 right -= 1
25 if nums[right] <= pivot_value:
26 break
27 # Swap elements from both sides if needed
28 if left < right:
29 nums[left], nums[right] = nums[right], nums[left]
30
31 # If the partitioning index is less than k_smallest, we know that
32 # the kth largest element must be in the right partition.
33 # If it's greater than or equal to k_smallest, the element will
34 # be in the left partition.
35 if right < k_smallest:
36 return quick_select(right + 1, end, k_smallest)
37 return quick_select(start, right, k_smallest)
38
39 # Calculate the 'k_smallest' index based on the 'kth largest' requirement
40 n = len(nums)
41 k_smallest = n - k
42 # Call the quick_select helper function to find the kth largest element
43 return quick_select(0, n - 1, k_smallest)
44
45# Note: The variable names 'start', 'end', 'k_smallest', 'pivot_index', 'pivot_value',
46# 'left', and 'right' were chosen to improve clarity and adhere to standard naming conventions.
47
1class Solution {
2 // Function to find the kth largest element in the array
3 public int findKthLargest(int[] nums, int k) {
4 int n = nums.length;
5 // Find the (n-k)th smallest element because the kth largest is also the (n-k)th smallest when sorted in ascending order
6 return quickSelect(nums, 0, n - 1, n - k);
7 }
8
9 // Helper function to perform quick select
10 private int quickSelect(int[] nums, int left, int right, int kSmallest) {
11 // When the left and right pointers meet, we've found the kSmallest element
12 if (left == right) {
13 return nums[left];
14 }
15
16 // Initialize two pointers for the partitioning step
17 int i = left - 1;
18 int j = right + 1;
19 // Choose pivot as the middle element
20 int pivot = nums[(left + right) >>> 1];
21
22 while (i < j) {
23 // Move i right past any elements less than the pivot
24 do {
25 i++;
26 } while (nums[i] < pivot);
27
28 // Move j left past any elements greater than the pivot
29 do {
30 j--;
31 } while (nums[j] > pivot);
32
33 // Swap elements at i and j if they are out of order with respect to the pivot
34 if (i < j) {
35 swap(nums, i, j);
36 }
37 }
38
39 // After partitioning, the pivot is now at index j
40 // If we found the kSmallest element, return it
41 if (j >= kSmallest) {
42 return quickSelect(nums, left, j, kSmallest);
43 }
44
45 // Otherwise, continue the search in the right partition
46 return quickSelect(nums, j + 1, right, kSmallest);
47 }
48
49 // Swap function to swap two elements in the array
50 private void swap(int[] nums, int i, int j) {
51 int temp = nums[i];
52 nums[i] = nums[j];
53 nums[j] = temp;
54 }
55}
56
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 // Public method to find the k-th largest element in the array.
7 int findKthLargest(vector<int>& nums, int k) {
8 int n = nums.size();
9 // The k-th largest is the (n - k)-th smallest, adjust and use quick select.
10 return quickSelect(nums, 0, n - 1, n - k);
11 }
12
13private:
14 // Utility method to perform quick select.
15 int quickSelect(vector<int>& nums, int left, int right, int k) {
16 if (left == right) { // If the sub-array has only one element, return that element.
17 return nums[left];
18 }
19
20 int pivotIndex = left + (right - left) / 2; // Choose the middle element as pivot.
21 int pivotValue = nums[pivotIndex];
22 int i = left, j = right;
23
24 // Partition the array around the pivot.
25 while (i <= j) {
26 // Find leftmost element greater than or equal to the pivot.
27 while (nums[i] < pivotValue) {
28 i++;
29 }
30 // Find rightmost element less than or equal to the pivot.
31 while (nums[j] > pivotValue) {
32 j--;
33 }
34 // Swap elements to ensure all elements on left are less than pivot
35 // and all on right are greater than pivot.
36 if (i <= j) {
37 swap(nums[i], nums[j]);
38 i++;
39 j--;
40 }
41 }
42
43 // After partitioning, the pivot is at its final sorted position,
44 // check if this position is the one we're looking for.
45 if (k <= j) {
46 // If k is in the left partition, recursively search in the left part.
47 return quickSelect(nums, left, j, k);
48 } else {
49 // If k is in the right partition, recursively search in the right part.
50 return quickSelect(nums, i, right, k);
51 }
52 }
53};
54
1function findKthLargest(nums: number[], k: number): number {
2 // Helper function to swap elements at indices i and j within nums array
3 const swapElements = (i: number, j: number) => {
4 [nums[i], nums[j]] = [nums[j], nums[i]];
5 };
6
7 // Helper function to implement Quick Select algorithm
8 const quickSelect = (left: number, right: number) => {
9 // Return early if the partition size is smaller than the kth element we are looking for
10 if (left >= right || left + 1 > k) {
11 return;
12 }
13
14 // Randomly select a pivot and move it to the start
15 swapElements(left, left + Math.floor(Math.random() * (right - left)));
16 const pivot = nums[left];
17 let pivotIndex = left;
18
19 // Partition the array around the pivot
20 for (let i = left + 1; i < right; i++) {
21 // If the current element is greater than the pivot, swap it with the element
22 // at the pivotIndex and increment pivotIndex
23 if (nums[i] > pivot) {
24 pivotIndex++;
25 swapElements(i, pivotIndex);
26 }
27 }
28
29 // Put the pivot element at its correct position
30 swapElements(left, pivotIndex);
31
32 // Recursively apply the same logic to the left and right partitions
33 quickSelect(left, pivotIndex);
34 quickSelect(pivotIndex + 1, right);
35 };
36
37 // Start the quick select process on the entire array
38 quickSelect(0, nums.length);
39
40 // Return the kth largest element
41 return nums[k - 1];
42}
43
Time and Space Complexity
The implemented function findKthLargest
uses the QuickSelect algorithm, which is a variation of the QuickSort algorithm, to find the k
th largest element in the list.
Time Complexity
The average time complexity of the QuickSelect algorithm is O(n)
, where n
is the number of elements in the list. This is because it generally only needs to recursively partition one side of the pivot, effectively reducing the problem size by about half each time.
However, in the worst-case scenario, the time complexity degrades to O(n^2)
. This happens when the pivot selected is always the smallest or largest element in each recursion, causing the algorithm to partition around each element one by one. In practice, with a good pivot selection strategy (such as using the median-of-medians algorithm), the worst-case complexity can be improved, but this code uses a simple middle element pivot, so it remains vulnerable to the worst-case behavior.
Space Complexity
The space complexity of the QuickSelect algorithm used here is O(log n)
on average due to the recursion stack. It requires additional space proportional to the depth of the recursion tree which, on average, has a depth of log n
.
In the worst case, where the smallest or largest element is always chosen as the pivot, the recursive calls can go up to n
levels deep resulting in a space complexity of O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Want a Structured Path to Master System Design Too? Donāt Miss This!