This solution got accepted, but I think the problem needs some clarification.


  • 5
    Z

    Here's my code:

    public int canCompleteCircuit(int[] gas, int[] cost) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        int tank = 0;
        int counter = 0;
        int curIndex = 0;
        int ret = 0;
        boolean reset = true;
        while(tank >= 0 && counter < gas.length){
            if(reset){
                if(gas[curIndex]-cost[curIndex]>=0){
                    tank += gas[curIndex]-cost[curIndex];
                    counter++;
                    ret = curIndex;
                    reset = false;
                }
                else if(curIndex == gas.length-1) return -1;
                curIndex++;
            }
            else{
                tank+=gas[curIndex]-cost[curIndex];
                if(tank < 0){
                    if(ret == gas.length-1) return -1;
                    tank = 0;
                    counter = 0;
                    ret = curIndex;
                    reset = true;
                }
                else{
                    counter++;
                    curIndex++;
                }
            }
            if(curIndex == gas.length) curIndex = 0;
        }
        return ret;
    }
    

    The idea is if we start at any ith station, where ith station has positive gas-cost,and we fail at kth station(total gas < 0), starting from any station between ith and kth will not be possible. Thus, when we fail at k, next time we try to start at a station after k, where the station has positive gas-cost, and see if we can finish the circuit from there. If at the end of the gas/cost array the gas - cost value is still negative or starting at the end of the array is still not a valid solution, we return -1;

    In this way we can reduce the run time to linear time. Is there a better solution?

    I think the following two things might need some clarification in the problem:

    1. Since the gas stations are on a circle, can we travel backward? I did not count the case when traveling to the left direction of the array works but traveling to the right does not work. In my understanding, at ith station, the cost to travel to the right will be cost[i] but the cost to travel to the left will be cost[i-1].

    2. How do we define "complete the circuit"? It seems that the circuit is regarded as completed if we can start at ith station and arrive at ith station eventually, not just i-1th station. Initially I had this line:

      if(gas.length == 1) return 0;

    but it failed the test case "[4], [5]".


  • 1
    L
     public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            for(int i = 0; i < gas.size(); i++)
                gas[i] -= cost[i];
            int start = -1;
            int max = 0, sum = 0;
            for (int i = 0, j = 0; j < gas.size(); j++) {
                sum += gas[j];
                if (sum < 0) {
                    i = j + 1; //keep track of start
                    sum = 0;
                } else
                    start = i;
            }
            sum = 0;
            for (int i = start; i < gas.size(); i++) {
                sum += gas[i];
                if (sum < 0) {
                    start = -1;
                    break;
                }
            }
            if (start != -1) {
                for (int i = 0; i < start; i++) {
                    sum += gas[i];
                    if (sum < 0) {
                        start = -1;
                        break;
                    }
                }
            }
            return start; 
        }
    };
    

    if we can somehow travel the circle, we must have zero or more gas remained in the car. So we only need to record the station from which we can travel to the end station, then check if we can travel the circle starting at that station.


  • 0
    D

    Is this linear time. As per my understanding of the solution, the solution is starting at 0 and moving as long as total cost till that point is greater than total gas. Once we encounter total cost<total gas we reintialise both total(gas and cost,counter) to 0 and begin a fresh from the next gas station. Also in a circle means covering all the gas stations and returning it to where it started. In this case, we are traversing over the nodes repeatedly. Hence the time complexity is > N

    Correct me if I have mis understood the solution/problem


  • 0
    D

    here is my solution ,I think it is similar with some interview question.
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {

    	int i=0;
    	int start=0;
    	int dif=0;
    	int sum=0;
    	for(i=0;i<gas.size()&&i<cost.size();i++)
    	{
    		dif=gas[i]-cost[i];
    		
    		if(sum<0)
    		{
    			start=i;
    			sum=0;
    		}
    		sum+=dif;
    	}
    	if(sum<0)
    		return -1;
    	for(i=0;i<start;i++)
    		sum+=gas[i]-cost[i];
    	if(sum>=0)
    		return start;
    	else 
    		return -1;
    
      }

  • 0
    P

    we can double both gas and cost to avoid judging the circuit.

    public int canCompleteCircuit(int[] gas, int[] cost) {
        if (gas == null
            || cost == null
            || gas.length == 0
            || cost.length == 0
            || gas.length != cost.length) {
          return -1;
        }
        int length = gas.length;
        gas = doubleArray(gas);
        cost = doubleArray(cost);
    
        int start = 0;
        int tank = 0;
        
        for(int end = 1; end < gas.length; end ++) {
          tank += gas[end-1] - cost[end-1];
          if (tank < 0) {
            start = end;
            tank = 0;
          }
          if (end - start == length) {
            return start;
          }
        }
        
        return -1;
      }
    
      private int[] doubleArray(int[] array) {
        int[] results = new int[array.length + array.length];
        System.arraycopy(array, 0, results, 0, array.length);
        System.arraycopy(array, 0, results, array.length, array.length);
        return results;
      }

  • 0
    K

    I don't have proof but traveling backward shouldn't change the result IMO. But alas, all test cases only consider one direction.

    About [4],[5], I think it is a bit odd, I had the same length 1 check initially, but it could be interpreted that way I suppose.

    One thing to try to avoid the index wrap around is to keep track of how much gas should be left in the tank when you finish scanning the array once. When we fail at gas station k, we know from the current starting point, we are short of m1 gas. We take note of m1, and try then next starting point, if we fail again, we know from this new starting point we are short of m2 gas. Now suppose we CAN finish the circle, when we are at the last gas station, we must have still at least (m1+m2) in the tank. No need to wrap around.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.