Gas Station
Understand how to apply greedy algorithms to identify the unique gas station index for completing a circular route with given gas and cost arrays. This lesson helps you analyze problem constraints and implement a solution that ensures you return to the starting point after traversing all stations.
We'll cover the following...
Statement
There are gas stations along a circular route, where the amount of gas at the station is gas[i].
We have a car with an unlimited gas tank, and it costs cost[i] of gas to travel from the station to the next 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.lengthcost.length- 1
gas.length,cost.length - 0
gas[i],cost[i]
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Gas Stations
What will the output be if the following gas and cost arrays are provided as input?
gas = [3, 1, 1]
cost = [1, 2, 2]
0
1
2
-1
Figure it out!
We have a game for you to play: re-arrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
export function gasStationJourney(gas, cost){// Replace this placeholder return statement with your codereturn -1}