Terminated due to timeout for my hacker rank solution

Question

Hello all please check the problemHackerRank Problem Statement

This is my solution for the above problem(link)

static int migratoryBirds(List<Integer> arr) {
    int ar[]=new int[arr.size()];
    for(int i=0;i<arr.size();i++){
        ar[i] = Collections.frequency(arr,arr.get(i));
        // ar[i] = obj.occuranceOfElement(arr,arr.get(i));
    }
    int maxAt = 0;
    for (int i = 0; i < ar.length; i++) {
        maxAt = ar[i] > ar[maxAt] ? i : maxAt;
    }
    return arr.get(maxAt);
}

my code is unable to handle when the array size is bigger,example 17623 elements in array.

Terminated due to timeout

The problem is in the second for loop which iterates over the array and gives me the index of the largest number in the array.Is there any other way that I could increase the performance.

Answer 1

Your problem is in this part:

for(int i = 0; i < arr.size(); i++)
    ar[i] = Collections.frequency(arr, arr.get(i));

This is O(N²): Collections.frequency() iterates over whole list to calculate frequency for only one element. Manually, you can iterate over the list to calculate frequencey for all elements.

Moreover, ther're only 5 birds, so you need only 5 length array.

static int migratoryBirds(int[] arr) {
    int max = 1;
    int[] freq = new int[6];

    for (int val : arr)
        freq[val]++;

    for (int i = 2; i < freq.length; i++)
        max = freq[i] > freq[max] ? i : max;

    return max;
}

Answer 2

Your problem is the call to Colletions.frequency, which is an O(N) operation. When you call it from inside a loop it becomes O(N²) and that consumes all your time.

Also, are you sure which implmentation of List you receive? You call list.get(i) which might also be O(N) if the implementation is a LinkedList.

The target of this exercise is to calculate the frequency of each value in one pass over the input. You need a place where you store and increase the number of occurrences for each value and you need to store the largest value of the input.

You have also skipped over a crucial part of the specification. The input has limits which makes solving the problem easier than you now think.