My take on Migratory Bird is failing one case

Question

Update: I completely overlooked the complexity added by arr.sort() method. So in Kotlin for array of Int, It compiles to use java.util.DualPivotQuicksort see this which in turn has complexity of O(n^2). see this. Other than that, this is also a valid approach.

I know It can be solved by keeping multiple arrays or using collections (which is what I ended up submitting), I want to know what I missed in the following approach

    fun migratoryBirds(arr: Array<Int>): Int {
        var maxCount = 0
        var maxType = 0
        var count = 0
        var type = 0

        arr.sort()
        println(arr.joinToString(" "))
        for (value in arr){

            if (type != value){
                if (count > maxCount){
                    maxCount = count
                    maxType = type
                }
                // new count values
                type = value
                count = 1
            } else {
                count++ 
            }
        }
        return maxType
    }

This code passes every scenario except for Test case 2 which has 73966 items for array. On my local machine, that array of 73k+ elements was causing timeout but I did test for array up-to 20k+ randomly generated value 1..5 and every time it succeeded. But I couldn't manage to pass Test case 2 with this approach. So even though I ended up submitting an answer with collection stream approach, I would really like to know what could I be missing in above logic.

I am running array loop only once Complexity should be O(n), So that could not be reason for failing. I am pre-sorting array in ascending order, and I am checking for > not >=, therefore, If two types end up having same count, It will still return the lower of the two types. And this approach is working correctly even for array of 20k+ elements ( I am getting timeout for anything above 25k elements).

Answer 1

The reason it is failing is this line

 arr.sort()

Sorting an array takes O(n logn) time. However using something like a hash map this can be solved in O(n) time.

Here is a quick python solution I made to give you the general idea

# Complete the migratoryBirds function below.
def migratoryBirds(arr):
    ans = -1
    count = -1
    dic = {}
    for x in arr:
        if x in dic:
            dic[x] += 1
        else:
            dic[x] = 1
        if dic[x] > count or dic[x] == count and x < ans:
            ans = x
            count = dic[x]
    return ans