Time complexity is O(klogk) which is probably the best possible?
private static int[] problem(int[] arr, int k) {
int length = arr.length;
List<Integer> nextDenominatorIndex = new ArrayList<>();
PriorityQueue<Integer> indexQueue = new PriorityQueue<>(
(x, y) -> Integer.compare(arr[x]*arr[nextDenominatorIndex.get(y)], arr[y]*arr[nextDenominatorIndex.get(x)]));
nextDenominatorIndex.add(arr.length - 1);
indexQueue.add(0);
int index = 0;
int nextIndex = 1;
for(int repeat = 0; repeat < k; repeat++) {
index = indexQueue.peek();
if(arr[index]*arr[length - 1] > arr[nextIndex]*arr[nextDenominatorIndex.get(index)]) {
nextDenominatorIndex.add(length - 1);
indexQueue.add(nextIndex);
Comment too long. Click here to view the full text.