Two pointers easy and fast Java solution, with comments


  • 1
    J

    The main idea of the algorithm is to have 2 pointers representing where the trip starts and where the trip ends. We move the "front pointer" if we have "capacity" to do so (i.e. if we have extra gas), and we move the "back pointer" if we lack gas to complete our trip, therefore trying to find a start position that will give us the extra gas we need.

    When the 2 pointers meet, we just check whether we ended up with enough gas or not to complete the trip.

    We treat the array as circular and start at a random position (for simplicity, say index 0). Not sure how to movie backwards on a circular array in an elegant fashion, therefore just came up with

    startIndex = startIndex-1 >= 0 ? startIndex-1 : n-1

    Please let me know if there is a nice way :)

     public int canCompleteCircuit(int[] gas, int[] cost) {
        
        if(gas == null || gas.length == 0 || 
            cost == null ||cost.length == 0) {
            return -1;        
        }
        
        int n = gas.length;
        
        int startIndex = 0;
        int endIndex = 0;
        int totalProfit = gas[startIndex] - cost[startIndex];
        
        do {
            if(totalProfit >= 0) {
                endIndex = (endIndex+1)%n;
                totalProfit += gas[endIndex] - cost[endIndex];
            } else {
                startIndex = startIndex-1 >= 0 ? startIndex-1 : n-1;
                totalProfit += gas[startIndex] - cost[startIndex];
            }
        } while(startIndex != endIndex);
        
        return totalProfit >= 0 ? startIndex : -1;
    }

  • 0
    T

    You can move the same way backwards as forwards: (startIndex - 1 + n) % n.
    The +n makes sure you'll get the result in 0..n-1 and not in -1..n-2 range.


  • 0
    T

    An idea for "elegant": no need to wrap around, that is you can lose the %n from everywhere:

    • int startIndex = n; (0 ≡ n (% n)) this gets rid of the startIndex-1 >= 0 condition because it will simply end up with n-1 the first time the else branch is reached and then just keeps decreasing.
    • ++endIndex;, --startIndex; notice that each index is inc/decremented once every iteration, and the loop stops when they meet, so starting at 0 (≡ n) will likely end up being the middle of the tour. Even if the input is such that always only one of the indices are inc/decremented they'll still end up being equal: either 0->n or n->0.

    Didn't test it, but I feel my reasoning strong enough; one tricky part is that you're returning startIndex which may need another check, like: if (startIndex == n) startIndex = 0; right after the loop.

    Edit: init becomes: int totalProfit = gas[endIndex] - cost[endIndex]; to prevent IOOBE.

    Here's the full code for simplicity:

    public int canCompleteCircuit(int[] gas, int[] cost) {
    	if (gas == null || gas.length == 0 || cost == null || cost.length == 0) return -1;
    
    	int startIndex = gas.length;
    	int endIndex = 0;
    	int totalProfit = gas[endIndex] - cost[endIndex];
    
    	do {
    		if (totalProfit >= 0) {
    			++endIndex;
    			totalProfit += gas[endIndex] - cost[endIndex];
    		} else {
    			--startIndex;
    			totalProfit += gas[startIndex] - cost[startIndex];
    		}
    	} while (startIndex != endIndex);
    	if (startIndex == gas.length) startIndex = 0;
    
    	return totalProfit >= 0? startIndex : -1;
    }

Log in to reply
 

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