CODEWITHSUNDEEP
javaarraysperformancecollections
rahul uday
rahul uday

Reputation: 131

Terminated due to timeout for my hacker rank solution

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.

Upvotes: 2

Views: 1708

Answers (4)

LuCio
LuCio

Reputation: 5173

We can determine the type number of the most common bird in one loop. This has the time complexity O(n).

static int migratoryBirds(int[] arr) {
    int highestFrequency = 0;
    int highestFrequencyBirdType = 0;
    int[] frequencies = new int[5]; // there are 5 bird types

    for (int birdType : arr) {
        int frequency = ++frequencies[birdType - 1];
        if (frequency > highestFrequency) {
            highestFrequency = frequency;
            highestFrequencyBirdType = birdType;
        } else if (frequency == highestFrequency && birdType < highestFrequencyBirdType) {
            highestFrequencyBirdType = birdType;
        }
    }

    return highestFrequencyBirdType;
}

For each element in the array arr we update the overall highestFrequency and are storing the corresponding value representing the highestFrequencyBirdType . If two different bird types have the highest frequency the lower type (with the smallest ID number) is set.

Upvotes: 1

Oleg Cherednik
Oleg Cherednik

Reputation: 18245

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;
}

Upvotes: 4

Maurice Perry
Maurice Perry

Reputation: 9650

Here's another one:

static int migratoryBirds(List<Integer> arr) {
    int freq[]=new int[6];
    for(int i=0;i<arr.size();i++){
        ++freq[arr.get(i)];
    }
    int maxAt = 1;
    for (int i = 2; i < freq.length; i++) {
        if (freq[i] > freq[maxAt]) {
            maxAt = i;
        }
    }
    return maxAt;
}

Upvotes: 1

Torben
Torben

Reputation: 3913

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.

Upvotes: 4

Related Questions