Leetcode. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null || gas.length == 0){
            return -1;
        }
        
        int start = 0;
        int fuel = 0;
        int tank = 0;
        
        for (int i = 0; i < gas.length; ++i){
            fuel += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0){ 
                tank = 0; start = i + 1; 
            } 
        } 
        return fuel >= 0 ? start : -1;
        
    }
}

Go
Time complexity: O(N)
Space complexity: O(1)

func canCompleteCircuit(gas []int, cost []int) int {
    if gas == nil || len(gas) == 0{
        return -1;
    }
    var fuel, tank, start int = 0, 0, 0
    
    for i := 0; i < len(gas); i++ {
        fuel += gas[i] - cost[i]
        tank += gas[i] - cost[i]
        if tank < 0{
            tank = 0
            start = i + 1
        }
    }
    
    if fuel < 0{
        return -1
    } else{
        return start;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s