> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/greedy/134.-gas-station.md).

# 134. Gas Station

![](/files/-MhwIFKhrNdR_8N5dyJv)

![](/files/-MhwIIo8M9eY0HStSrir)

![](/files/-MhwIMNbIxbGNmOrG6sx)

time: O(n)

space: O(1)

```java
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        for (int i = 0; i < gas.length; i++) { // check gas >= cost
            sum += gas[i] - cost[i];
        }
        if (sum < 0) return -1;
        
        sum = 0;
        int result = 0;
        for (int i = 0; i < gas.length; i++) {
            sum += gas[i] - cost[i];
            if (sum < 0) {
                sum = 0;
                result = i + 1;
            }
        }
        return result;
    }
}


/*
    g[1,2,3,4,5]
    c[3,4,5,1,2]
    
    g[i] - c[i] + g[i+1] >= 0
    
    0 + 3 - 4 < 0 => false,
    
    
    2,3,4
    3,4,3
    
    5-3 = 2
    2+4-4 = 2
    
    A <-> B fail => A 出發到 B fails
      A+1 A+2 < B => 從 A+1, A+2...< B 都會 fail
    
    so should use B+1 be a new start
    loop do this strategy, if following C point fails, use C+1 be a new start
    
    and until end, it finished 
    ( dont need to validate the follings in start of array, because 
    => If there exists a solution, it is guaranteed to be unique)
    
*/
```