If the total fuel available is at least the total cost, a valid start must exist. Track the running surplus and reset the candidate start whenever it dips below zero.

Gas Station

medium

Acceptance: 43%

GreedyArrays

There are n fuel stations arranged in a circle. Station i offers gas[i] units of fuel, and traveling from station i to the next costs cost[i] units. Starting with an empty tank, determine the station index from which you can depart and complete a full loop, or return -1 if no such starting point exists.

Examples

Example 1:

Input:gas = [2,3,1,5,4], cost = [3,2,4,2,3]

Output:3

Example 2:

Input:gas = [1,2,3], cost = [2,3,4]

Output:-1

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Gas Station

Examples

Hints

Related Problems