Gas Station

Try to solve the Gas Station problem.

Statement

There are nn gas stations along a circular route, where the amount of gas at the ithi^{th} station is gas[i].

We have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from the ithi^{th} station to the next (i+1)th(i+1)^{th} station. We begin the journey with an empty tank at one of the gas stations.

Find the index of the gas station in the integer array gas such that if we start from that index we may return to the same index by traversing through all the elements, collecting gas[i] and consuming cost[i].

  • If it is not possible, return -1.

  • If there exists such index, it is guaranteed to be unique.

Constraints:

  • gas.length ==== cost.length
  • 1 ≤\leq gas.length, cost.length ≤103\leq 10^3
  • 0 ≤\leq gas[i], cost[i] ≤103\leq 10^3

Create a free account to view this lesson.

Continue your learning journey with a 14-day free trial.

By signing up, you agree to Educative's Terms of Service and Privacy Policy