Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

187. Gas Station

MediumDay 55 of 60Greedy & Intervals

There are n gas stations on a circular road. Station i gives gas[i] units of fuel, and driving from station i to station i + 1 uses cost[i] units. You start with an empty tank at some station. Return the index of the station from which you can drive around the whole circle once, or -1 if no such station exists. If an answer exists, it is unique.

Example 1
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Starting at index 3 the tank goes 4, 8, 7, 6, 3 units and never drops below zero.
Example 2
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Total gas 9 is less than total cost 10.
Constraints
  • 1 <= n <= 10^5
  • 0 <= gas[i], cost[i] <= 10^4
Hints
Frequently asked at: Amazon, Google, Microsoft
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min