Java Program getting failed with timeout for some test cases

Question

I was practising on Hackerrank. Well, the question is pretty much simple I have attached it over here with sample input. When I run into my local machine with custom input its working as expected. But while I am running on its online platform sometime 2 and sometimes 3 test cases getting failed with time out exception. Code is below here anyone can suggest what improvement is needed?

This is the solution

public static void main(String[] args) {
        int k = 3;
        List<Integer> marks = new ArrayList<Integer>();
        marks.add(20);
        marks.add(20);
        marks.add(40);
        marks.add(60);
        marks.add(20);
        marks.add(10);
        marks.add(0);
        marks.add(100);
        System.out.println(numofPrizes(k, marks));
    }
    public static int numofPrizes(int k, List<Integer> list) {
        // Write your code here
        Collections.sort(list, Collections.reverseOrder());
        List<Integer> str = new ArrayList<Integer>();
        AtomicInteger rank = new AtomicInteger(0);
        AtomicInteger count = new AtomicInteger(0);
        list.stream().forEach(x -> {
            if(!str.contains(x)){
                rank.getAndIncrement();
            }
            if(rank.get() <= k && x > 0){
                count.getAndIncrement();
            }
            str.add(x);
//          System.out.println("mark " + x + " rank " + rank.get() + " count " + count.get() );
        });
        return count.get();     
    }

Output :

mark 100 rank 1 count 1
mark 60 rank 2 count 2
mark 40 rank 3 count 3
mark 20 rank 4 count 3
mark 20 rank 4 count 3
mark 20 rank 4 count 3
mark 10 rank 5 count 3
mark 0 rank 6 count 3
3

Answer 1

When I just change the approach as below, It got worked.

public static void main(String[] args) {
    int k = 3;
    List<Integer> marks = new ArrayList<Integer>();
    marks.add(20);
    marks.add(20);
    marks.add(40);
    marks.add(60);
    marks.add(20);
    marks.add(10);
    marks.add(0);
    marks.add(100);
    System.out.println(numofPrizes(k, marks));
}
public static int numofPrizes(int k, List<Integer> list) {
              list.sort(Collections.reverseOrder());
      int number = 0,counter = 1;
      int[] mark = new int[list.size()],rank = new int[list.size()];
      Map<Integer,Integer> map  = new HashMap<Integer,Integer>();   
      for (int i = 0; i < list.size(); i++) {
              map.put(list.get(i), (map.get(list.get(i)) != null) ? map.get(list.get(i)) : counter);
              mark[i] = list.get(i);
              rank[i] = (int) map.get(list.get(i));
              counter++;
              if(mark[i] > 0 && k >= rank[i]){
                      number++;
              }
      }          
      return number;   
}

Answer 2

It can also be thought in this sense that if the input can be big in terms of size of input array/list, we should avoid performing sort on it if possible.

Here, since there can be only 100 uniques values for marks, we can use that fact and make a sorted map of Marks to number of occurrence. This will take O(n) time. or O(n log n) time to sort the map (only 100 entries max)

Key is to avoid sorting large datasets and creating new large datasets by copying larger ones.

Answer 3

Certain parts of the code that you can improve possibly in terms of readability and performance could be:

• you can use List.sort for the precise use of the API over elements of a List

  list.sort(Collections.reverseOrder());
  

• there is a costly method invocation involved in your code, which is generally an O(n²) operation and i.e.

  if(!str.contains(x))
  

  this operation could be efficient i.e. O(n) when performed over a HashSet but then you can also optimize slightly on the additional add overhead as:

  Set<Integer> str = new HashSet<>();
  
  if (str.add(x)) {
      rank++; // or the use of getAndIncrement
  }
  

• at the functional programming construct, you could rather think of counting the value while you sort them in reverse order and then limiting to the rank cut-off in the input while performing the sum of the corresponding counts

  private static int numofPrizes(int k, List<Integer> list) {
      Map<Integer, Integer> valueToCount = list.stream()
              .filter(mark -> mark != 0)
              .collect(Collectors.groupingBy(Function.identity(),
                      Collectors.collectingAndThen(Collectors.counting(), Long::intValue)));
  
      return valueToCount.entrySet().stream()
              .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
              .limit(k)
              .mapToInt(Map.Entry::getValue)
              .sum();
  }
  

  do note, that the groupingBy here is an O(n) operation again and this complete logic could me merge into a single pipeline as follows:

---

private static long numOfPrizes(int k, List<Integer> list) {
    return list.stream()
            .filter(mark -> mark != 0)
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
            .entrySet().stream()
            .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
            .limit(k)
            .mapToLong(Map.Entry::getValue)
            .sum();
}