LeetCode Entry

134. Gas Station

7.01.2023 medium 2023 kotlin

fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {

134. Gas Station medium

https://t.me/leetcode_daily_unstoppable/78

blog post

    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        var sum = 0
        var minSum = gas[0]
        var ind = -1
        for (i in 0..gas.lastIndex) {
            sum += gas[i] - cost[i]
            if (sum < minSum) {
                minSum = sum
                ind = (i+1) % gas.size
            }
        }
        return if (sum < 0) -1 else ind
    }

We can start after the station with the minimum decrease in gasoline. image.png Calculate running gasoline volume and find the minimum of it. If the total net gasoline is negative, there is no answer.

Space: O(1), Time: O(N)