This is rather a Math Problem, Explanation Here


  • 0
    B

    We are trying to find an i satisfies:

    sum(gas[(i + j)%N], j belongs to [0, L]) >= sum(cost[(i + j)%N], j belongs to [0, L]),
    for any L belongs to [0, N - 1].

    Yes, iterate i from 0 to N-1, but a O(N^2) solution is not sufficient. Fortunately we can discover that, when one i fails to suffice the condition, concretely with some L, then it would be impossible that any i between i+1 and i+L(inclusive) is an answer. This is easy to prove using a little math skill.

    class Solution {
    public:
        int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
            int accGas = 0, accCost = 0;
            int N = gas.size();
            int i = 0;
            while(i < N)
            {
                accGas = 0; accCost = 0;
                bool flag = true;
                for(int j = 0; j < N; j ++)
                {
                    accGas += gas[(i+j)%N];
                    accCost += cost[(i+j)%N];
                    if(accCost > accGas)
                    {
                        i = i+j+1;
                        flag = false;
                        break;
                    }
                }
                if(flag)
                {
                    return i;
                }
            }
            return -1;
        }
    };

  • 0
    C

    The solution above is correct, but there is still a linear solution, here my solution with O(n) and comments inline. The overall analysis has some base on what you express: we can calculate the difference between the gas and the cost. I calculate it on the first for loop. If the sum is negative, there's no way there's a route.

    Else, we look for a negative difference (a gas station where the gas provided is less than the cost to the next station). And from there we go backwards to find the first gas station that makes the accumulated sum positive before the negative number. If we find it, then we move the index that was pointing to the negative number one up and repeat until both indexes collide.

    There are three N loops so the overall complexity is O(n) (N is the number of gas stations).

    public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int[] diff = new int[gas.length];
    
    	// Find difference (O(n))
    	int totalSum = 0;
    	for (int i = 0; i < diff.length; i++) {
    		diff[i] = gas[i] - cost[i];
    		totalSum += diff[i];
    	}
    
    	// It's not possible to do the circuit.
    	if (totalSum < 0) {
    		return -1;
    	}
    
    	// Find negative (O(n))
    	int negPos = -1;
    	for (int i = 0; i < diff.length; i++) {
    		if (diff[i] < 0) {
    			negPos = i;
    			break;
    		}
    	}
    	
    	// No negatives, return first gas station (as good as any)
    	if (negPos == -1) {
    		return 0;
    	}
    
    	// Else, we keep two pointers: posPos and negPos
    	// posPos is going to keep track of the the index on which the sum starts to be positive. negPos keeps track of the index in which the sum became negative.
    	// When currSum is >= 0, we increase negPos index. When currSum < 0 we decrease posPos (looking for a previous positive number to make the sum >= 0).
    	int posPos = modulo((negPos - 1), diff.length);
    	int currSum = diff[negPos] + diff[posPos];
    	while (posPos != negPos) {
    		if (currSum >= 0) {
    			negPos = modulo((negPos + 1), diff.length);
    			currSum += diff[negPos];
    		} else {
    			posPos = modulo((posPos - 1), diff.length);
    			
    			currSum += diff[posPos];
    		}
    	}
    	return posPos;
        }
        
        public int modulo(int x, int y) {
            int result = x % y;
            if (result < 0) {
                result += y;
            }
            return result;
        }
    }

  • 0
    B

    Your advanced subtraction is always a practical method in maths. But my method is also a linear one. Maybe my text description is somewhat vague, but the codes are distinct. The key-point is that iterator i is added by j + 1 to skip unnecessary comparisons when the matching fails. The most times of comparing is no more than 2*N.


  • 0
    C

    Mmm. I haven't run your code step by step, but I think you are correct. I missed that part, thanks for the explanation :)


Log in to reply
 

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