Optimise Time Complexity of a function - Kotlin

Viewed 347

I have a function below:

fun getTimess(time: Array<Int>, direction: Array<Int>): Array<Int> {

    //check for range of values
    if (time.size > 100_000 || direction.size > 100_000) return emptyArray()

    //ensure that direction values are between 0 and 1
    if (direction.max() !in (0..1) || direction.min() !in (0..1)) return emptyArray()

    val result = Array(time.size) { 0 }
    val endTime: Int = time.max() ?: 0

    //check for time range
    if (endTime > 1_000_000_000 || endTime < 0) return emptyArray()


    if (endTime == 0) return result
    val inQueue: Queue<Pair<Int, Int>> = LinkedList()
    val outQueue: Queue<Pair<Int, Int>> = LinkedList()

    var currentTime = 0 //current time

    //indicates who used the turnstile in the previous second,
    // -1 if non used the turnstile in the last sec.
    var turnstile = -1

    for (i in time.indices) {
        if (direction[i] == 1) {
            outQueue.add(Pair(time[i], i))
        } else {
            inQueue.add(Pair(time[i], i))
        }
    }

    while (outQueue.isNotEmpty() || inQueue.isNotEmpty()) {
        //checking fot exit
        if (outQueue.isNotEmpty()
            && outQueue.peek().first <= currentTime
            && (turnstile == 1 || turnstile == -1 || inQueue.isEmpty()
                    || (inQueue.peek().first > currentTime && turnstile == 0))
        ) {
            result[outQueue.poll().second] = currentTime
            turnstile = 1

        } else if (inQueue.isNotEmpty() && inQueue.peek().first <= currentTime) {
            result[inQueue.poll().second] = currentTime
            turnstile = 0
        } else {
            turnstile = -1
        }

        currentTime++
    }

    return result
}

It outputs correctly but the issue is that it does not execute within the time limits. How can I possibly optimise the function to execute faster? It only has one for loop and one while loop.

0 Answers
Related