# 134. Gas Station

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhvM3JAs--rZYkr6ke6%2F-MhwIFKhrNdR_8N5dyJv%2Fimage.png?alt=media\&token=f6fd5cfe-6e37-4e1d-b4f4-0830b96078a1)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhvM3JAs--rZYkr6ke6%2F-MhwIIo8M9eY0HStSrir%2Fimage.png?alt=media\&token=9f99c4ec-89e6-43ee-b636-ca229dbcb77d)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MhvM3JAs--rZYkr6ke6%2F-MhwIMNbIxbGNmOrG6sx%2Fimage.png?alt=media\&token=ed1caa9a-f76d-43da-97ca-9acf3bcdcc90)

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)
    
*/
```