Sunday, June 28, 2015

Gas Station

There are N gas stations along a circular route, where the amount of gas at stationi 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.
Have you met this question in a real interview? 
Yes
Example
Given 4 gas stations with gas[i]=[1,1,3,1], and thecost[i]=[2,2,1,1]. The starting gas station's index is 2.
Note
The solution is guaranteed to be unique.

Challenge
O(n) time and O(1) extra space
public class Solution {
    /**
     * @param gas: an array of integers
     * @param cost: an array of integers
     * @return: an integer
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // write your code here
        int count = 0;
        int idx = 0;
        for(int i = 0; i < gas.length; i++){
            count += gas[i] - cost[i];
            if(count < 0){
                count = 0;
                idx = i+1;
            }  
        }
       
        for(int i = 0; i < idx; i++){
            count += gas[i] - cost[i];
        }
        return count >= 0 ? idx : -1;
    }
}

No comments:

Post a Comment