Note:

- A loop exists if there is enough gas starting from any gas station. i.e. loop exists if total gas >= total distance (assume 1 mpg).

- If a loop exists clockwise for gas stations, it also does anti-clockwise. So direction does not matter.

We get this array with a surplus or deficit at each gas station.

- If sum >= 0 at the end, a loop exists. The loop gas station is the first one after which sum stays >= 0 till end. This logic does not work for all valid loop gas stations but works for at least one gas station if loop exists (see examples with -).

d: -1 4 -3 -1 1 s: -1 3 0 -1 0 - | d: -1 3 -4 0 1 s: -1 2 -2 -2 -1 // no loop d: -1 6 -3 -1 1 s: -1 5 2 1 2 | - d: -1 5 -7 4 2 -6 5 s: -1 4 -3 1 3 -3 2 - | point: gas distance

// time O(n), O(1) space (points): looppoint = null sum = 0 for point in points: delta = point.gas - (point.distance / mpg) sum += delta if sum >= 0: if looppoint == null: looppoint = point else: looppoint = null return looppoint[Hat tip to B]

Another logic that works is this. The loop point is the next point when the sum is least if sum >= 0 in end.

(points): loopi = 0 sum = 0 minsum = 0 for i, point in points: delta = point.gas - (point.distance / mpg) sum += delta if sum < minsum: minsum = sum loopi = i+1 if sum < 0: loopi = -1 looppoint = 0 <= loopi < points.length() ? points[loopi] : null return looppoint

## No comments:

## Post a Comment