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.

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:

  1. Define a helper function quick_sort which will handle the partitioning and the recursive search.
  2. Within quick_sort, calculate a pivot value x as the element in the middle index of nums—this is computed as nums[(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.
  3. Set two pointers, i starting from the left bound left - 1 and j from the right bound right + 1. Then increment i and decrement j until an element greater than or equal to x is found from the left and an element less than or equal to x is found from the right.
  4. If i < j which means elements are on the wrong side of the pivot, swap them. Repeat this process until i is not less than j.
  5. After the loop, j will be at the partition point. If j is less than the index we're interested in (k), we know our kth largest element is on the right of j hence call quick_sort recursively for the right sub-array.
  6. If j is greater or equal to k, the kth largest element is on the left side or at j.
  7. 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 kth 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 index 4 (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.

💪
Level Up Your
Algo Skills

Example 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.

  1. We need to find the n-k th element in the sorted order, which translates to 6 - 2 = 4 in 1-indexed or 3 in 0-indexed notation in our array.
  2. We pick a pivot, let's use the median value of 3 as an example. The quick_sort function is then called with the entire array along with indices of the bounds 0 and 5.
  3. 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 pivot 3 is positioned at its correct sorted index 2.
  4. Since our target index 3 is greater than the pivot's index 2, we ignore the left part of the array including our pivot, and focus on the right part: [5, 6, 4].
  5. 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].
  6. The pivot 5 lands at index 1 of the sub-array (4 in the original array, due to 0-indexing). Now the position of 5 is the same as our target index 4 (n-k), which means it's the kth 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 kth element directly.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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 kth 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).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫