**I just announced the new ***Spring 5* modules in REST With Spring:

*Spring 5*modules in REST With Spring:

**1. Introduction**

In this article, we’ll present various solutions for finding the *k*th largest element in a sequence of unique numbers. We’ll use an array of integers for our examples.

We’ll also talk about each algorithm’s average and worst-case time complexity.

**2. Solutions**

Now let’s explore a few possible solutions — one using a plain sort, and two using the Quick Select algorithm derived from Quick Sort.

**2.1. Sorting**

When we think about the problem, perhaps **the most obvious solution that comes to mind is** **to sort the array**.

Let’s define the steps required:

- Sort the array in ascending order
- As the last element of the array would be the largest element, the
*k*th largest element would be at*xth*index, where*x = length(array) – k*

As we can see, the solution is straightforward but requires sorting of the entire array. Hence, the time complexity will be *O(n*logn)*:

public int findKthLargestBySorting(Integer[] arr, int k) { Arrays.sort(arr); int targetIndex = arr.length - k; return arr[targetIndex]; }

An alternative approach is to sort the array in descending order and simply return the element on *(k-1)*th index:

public int findKthLargestBySortingDesc(Integer[] arr, int k) { Arrays.sort(arr, Collections.reverseOrder()); return arr[k-1]; }

**2.2. QuickSelect**

This can be considered an optimization of the previous approach. In this, we pick the QuickSort for sorting. Analyzing the problem statement, we realize that **we don’t actually need to sort the entire array — we only need to rearrange its contents so that the kth element of the array is the kth largest or smallest.**

In QuickSort, we pick a pivot element and move it to its correct position. We also partition the array around it. **In QuickSelect, the idea is to stop at the point where the pivot itself is the kth largest element.**

We can optimize the algorithm further if we don’t recur for both left and right sides of the pivot. We only need to recur for one of them according to the position of the pivot.

Let’s look at the basic ideas of the QuickSelect algorithm:

- Pick a pivot element and partition the array accordingly
- Pick the rightmost element as pivot
- Reshuffle the array such that pivot element is placed at its rightful place — all elements less than the pivot would be at lower indexes, and elements greater than the pivot would be placed at higher indexes than the pivot

- If pivot is placed at the
*k*th element in the array, exit the process, as pivot is the*k*th largest element - If pivot position is greater than
*k,*then continue the process with the left subarray, otherwise, recur the process with right subarray

We can write generic logic which can be used to find the *k*th smallest element as well. We’ll define a method *findKthElementByQuickSelect() *which will return the *k*th element in the sorted array.

If we sort the array in ascending order, the *k*th element of an array will be the *k*th smallest element. To find the *k*th largest element, we can pass *k= length(Array) – k. *

Let’s implement this solution:

public int findKthElementByQuickSelect(Integer[] arr, int left, int right, int k) { if (k >= 0 && k <= right - left + 1) { int pos = partition(arr, left, right); if (pos - left == k) { return arr[pos]; } if (pos - left > k) { return findKthElementByQuickSelect(arr, left, pos - 1, k); } return findKthElementByQuickSelect(arr, pos + 1, right, k - pos + left - 1); } return 0; }

Now let’s implement the *partition *method, which picks the rightmost element as a pivot, puts it at the appropriate index, and partitions the array in such a way that elements at lower indexes should be less than the pivot element.

Similarly, elements at higher indexes will be greater than the pivot element:

public int partition(Integer[] arr, int left, int right) { int pivot = arr[right]; Integer[] leftArr; Integer[] rightArr; leftArr = IntStream.range(left, right) .filter(i -> arr[i] < pivot) .map(i -> arr[i]) .boxed() .toArray(Integer[]::new); rightArr = IntStream.range(left, right) .filter(i -> arr[i] > pivot) .map(i -> arr[i]) .boxed() .toArray(Integer[]::new); int leftArraySize = leftArr.length; System.arraycopy(leftArr, 0, arr, left, leftArraySize); arr[leftArraySize+left] = pivot; System.arraycopy(rightArr, 0, arr, left + leftArraySize + 1, rightArr.length); return left + leftArraySize; }

There’s a simpler, iterative approach to achieve the partitioning:

public int partitionIterative(Integer[] arr, int left, int right) { int pivot = arr[right], i = left; for (int j = left; j <= right - 1; j++) { if (arr[j] <= pivot) { swap(arr, i, j); i++; } } swap(arr, i, right); return i; } public void swap(Integer[] arr, int n1, int n2) { int temp = arr[n2]; arr[n2] = arr[n1]; arr[n1] = temp; }

This solution works in *O(n)* time on average. However, in the worst case, the time complexity will be *O(n^2)*.

**2.3. QuickSelect with Randomized Partition**

This approach is a slight modification of the previous approach. If the array is almost/fully sorted and if we pick the rightmost element as a pivot, the partition of left and right subarrays will be highly uneven.

This method suggests **picking the initial pivot element in a random manner.** We don’t need to change the partitioning logic though.

Instead of calling *partition*, we call the *randomPartition *method, which picks a random element and swaps it with the rightmost element before finally invoking the *partition *method.

Let’s implement the *randomPartition* method:

public int randomPartition(Integer arr[], int left, int right) { int n = right - left + 1; int pivot = (int) (Math.random()) % n; swap(arr, left + pivot, right); return partition(arr, left, right); }

This solution works better than the previous case in most cases.

The expected time complexity of randomized QuickSelect is *O(n)*.

However, the worst time complexity still remains *O(n^2)*.

**3. Conclusion**

In this article, we discussed different solutions to find the *k*th largest (or smallest) element in an array of unique numbers. The simplest solution is to sort the array and return the *k*th element. This solution has a time complexity of *O(n*logn)*.

We also discussed two variations of Quick Select. This algorithm isn’t straightforward but it has a time complexity of *O(n)* in average cases.

As always, the complete code for the algorithm can be found over on GitHub.

## Leave a Reply

Be the First to Comment!