-2

I want to be able to find the Kth largest item/element in a subarray.

For example: list: 3 15 19 7 14 lower bound: 2 upper bound: 4 K: 2

The program would output 15

Example 2: list: 3 15 19 7 14 lower bound: 1 upper bound: 2 K: 2

The program would output 3

What I've done so far is loop through the subarray itself. I then stored a sorted subarray in another array and located the Nth largest item from there.

int l = 4
int r = 2
int k = 2
int[] temp = new int[1+r-l];
for(int j = l-1; j < r; j++) {
    temp[j-l+1] = arr[j];
}
Arrays.sort(temp);
System.out.println(temp[temp.length-k]);

I believe that there is a much faster way of solving this problem.

TimothyW553
  • 57
  • 6
  • I'm having trouble understanding wherethe upperbound and lower bound come into play. Does upper and lower bounding specify a sub-array of the original list? – vpaladino778 Oct 11 '19 at 20:15
  • @vpaladino778 yes, it is the upper and lower bound of the array to form the subarray. 1th indexed. – TimothyW553 Oct 11 '19 at 20:16
  • Will there be multiple queries on the *same* array? – trincot Oct 11 '19 at 20:18
  • @trincot yes, multiple queries on the same array – TimothyW553 Oct 11 '19 at 20:28
  • 2
    Possible duplicate of [How to find the kth largest element in an unsorted array of length n in O(n)?](https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on) – Prune Oct 11 '19 at 21:07

1 Answers1

0

I can think of 3 possible solutions:

1. Sorting

This is the solution you gave. The time complexity would be O(n*log(n)), where n is the number of elements between lower bound and upper bound.

2. Heap

Quite similar to the first solution, but this would decrease time complexity a bit. The whole point is to create a priority queue and add elements from lower bound to upper bound, while maintaining the size of the priority queue as K. When the size overflows, just dequeue the smallest element. Then, what's left in the priority queue would be K largest elements within the bound. Polling the smallest element from that priority queue would give Kth largest element. The time complexity would be O(n*log(k)), since poll takes up log(k) time due to maintained size of K.

    PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
    for (int j = l-1; j < r; j++) {
        pq.add(arr[j]);
        if (pq.size() > k) pq.poll();
    }
    System.out.println(pq.poll());

3. Quickselect

This is known as Hoare's selection algorithm, quite similar to Quicksort. Time complexity would be O(n) on average, but O(n^2) in the worst case. Here is Wikipedia page you can refer to: https://en.wikipedia.org/wiki/Quickselect

wWw
  • 147
  • 9