Find location of three biggest numbers in an array

Question

This is a small algorithm within a larger leetcode question. If given an array, say [5,7,3,5,3,5,16,9], I want my code to return the location of the three biggest numbers of the array in order. With the mentioned array, the three biggest numbers would be 7, 16, and 9 with respect to their order from left to right. Thus, the method should return [1,6,7], or the indices where the three numbers are located.

I've been thinking through this for quite a while now, but I'm not sure how to do it. I've considered implementing HashMaps into the code to set a distinction between array value and location, but am not sure how to implement such a design. Any help would be appreciated, thank you!

EDIT

I found a solution to the problem. FindBig3 uses HashMap to keep a record of both the indexes in the given array and the value within it.

The code goes through the array from left to right with a for loop, and uses the following instructions

1. start with the first three array values as being "the big 3", stored within the lo3 Hashmap
2. find the smallest value within "the big 3" (uses findLeastValue method)
3. check if the i value in the for-loop is greater than the smallest value within "the big three", if so, then the smallest value is removed from lo3 and the i value is inserted.

The program then outputs the locations of the 3 biggest numbers (the key set of lo3)

public static String findBig3(ArrayList<Integer> array) {
    HashMap<Integer, Integer> lo3 = new HashMap<Integer, Integer>();
    lo3.put(0, array.get(0));
    lo3.put(1, array.get(1));
    lo3.put(2, array.get(2));

    for (int i = 3; i < array.size(); i++) {
        int leastLoc = findLeastValue(lo3);
        if (array.get(i) > lo3.get(leastLoc)) {
            lo3.put(i, array.get(i));
            lo3.remove(leastLoc);
        }
    }
    String loc = "";
    for (Integer location : lo3.keySet()) {
        loc += location + " ";
    }
    return loc;
}

//returns the KEY with the smallest number
public static int findLeastValue(HashMap<Integer,Integer> lo3) {
    int least = Integer.MAX_VALUE;
    int leastLoc = 0;
    for (Integer key : lo3.keySet()) {
        if (lo3.get(key) < least) {
            least = lo3.get(key);
            leastLoc = key;
        }
    }
    return leastLoc;
}

Answer 1

Use nth_element, not on the array of values, but on a separately constructed array of indices. nth_element moves the top (or least) K values to the right of all other values. A standard implementation of nth_element will not sort the whole array and give O(n) time complexity. And that is exactly what you need, you can later output the indices in fully sorted order, that would increase the complexity from O(n) to O(n + k.log(k)).

This C++ routines does the same. Similar to sorting, it takes a custom which orders the indices based on the value of the elements they point to, and moves the top K indices to position 0,...K-1.

#include <algorithm>

vector<int> TopKIndices(int k, vector<int32_t>& array) {
  vector<int> indices(array.size());
  int idx = 0;
  std::generate(indices.begin(), indices.end(), [&idx](){ return idx++; });
  if (k >= array.size()) {
    // All the indices are returned.
    return indices;
  }
  auto comp = [&array](const int ia, const int ib){
    return (array[ia] > array[ib]);
  };
  std::nth_element(indices.begin(), indices.begin() + k, indices.end(), comp);
  sort(indices.begin(), indices.begin() + k);
  return vector<int>(indices.begin(), indices.begin() + k);
}


// Test the code.
vector<int32_t> array = {5,7,3,5,3,5,16,9};
vector<int> ind = TopKIndices(3, array);
for (int i : ind) {
  printf("Top index = %d\n", i);
}

Answer 2

So you could make a class with two int variables: index and value of an element

Solution #1: implement the Comparable interface

Create a list of objects implementing the comparable interface. This interface can sort the list based on your implementation of compareTo function. You could sort the list based on the elements original value and then make a small algorithm to compare the indexes of the three highest. Learn more: https://docs.oracle.com/javase/tutorial/collections/interfaces/order.html

Solution #2: use a priority queue.

In a priority queue, an element with high priority is served before an element with low priority.

You could create a priority queue which would compare the objects based on the value of the element and pop the first three. Then just order them based on the index.

Check this question for an example implementation of a priority queue: How do I use a PriorityQueue?

Solution #3: Mix for portablity

Create a class implementing the Comparable interface with the two variables: index and value.

Push the contents of the array as the objects into a prioriy queue, where the original element value will be the priority of the element inside the queue. Pop as many as you like and put them in a list. Now you can sort the list using the comparable interface based on the original index. Your compare function should therefor compare based on the index of the element and return the lower one.