{x}
blog image

Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

 

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

 

Constraints:

  • n == gas.length == cost.length
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

Solution Explanation:

This problem asks to find a gas station to start a circular route, given the amount of gas at each station (gas) and the cost to travel to the next station (cost). We need to determine if a complete circuit is possible, and if so, return the starting index; otherwise, return -1.

The solution employs a greedy approach with two pointers (i and j). The core idea is to keep track of the remaining fuel (s) while iterating through the stations. If at any point the remaining fuel becomes negative, it means the current starting point (i) is invalid, and we need to move the starting point (i) backwards and adjust the fuel accordingly.

Algorithm:

  1. Initialization:

    • i and j are initialized to n - 1 (the last station index), where n is the number of gas stations.
    • s (sum) keeps track of the remaining fuel, initialized to 0.
    • cnt counts the number of stations visited.

  2. Iteration:

    • The outer while loop continues until all stations have been considered (cnt < n).
    • In each iteration:
      • s is updated by adding the gas at station j and subtracting the cost to travel to the next station.
      • cnt is incremented.
      • j moves to the next station (circularly using the modulo operator %).
      • The inner while loop handles cases where s becomes negative. This indicates that the current starting point (i) is infeasible. The loop moves i backwards, adjusts s by adding the gas and subtracting the cost at the new starting point (i), and increments cnt.

  3. Result:

    • If after considering all stations (cnt >= n), s is still less than 0, it means no valid starting point exists, so -1 is returned.
    • Otherwise, i represents the index of a valid starting point, which is returned.

Time Complexity Analysis:

The outer while loop iterates at most n times (number of gas stations). The inner while loop also iterates at most n times in the worst case (when every starting point is invalid). Therefore, the total time complexity is O(n) in the worst-case scenario, but it could be much less if a solution is found early.

Space Complexity Analysis:

The solution uses a constant amount of extra space for variables (i, j, s, cnt). Therefore, the space complexity is O(1), which is constant.

Example Walkthrough (Example 1):

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

  1. i = j = 4, s = 0, cnt = 0
  2. Outer loop:
    • s = 5 - 2 = 3, cnt = 1, j = 0
    • s = 3 + 1 - 3 = 1, cnt = 2, j = 1
    • s = 1 + 2 - 4 = -1, cnt = 3, j = 2 (s becomes negative)
  3. Inner loop:
    • i = 3, s = -1 + 4 - 5 = -2, cnt = 4 (still negative)
    • i = 2, s = -2 + 3 - 5 = -4, cnt = 5 (still negative)
    • i = 1, s = -4 + 2 - 4 = -6, cnt = 6 (still negative)
    • i = 0, s = -6 + 1 - 3 = -8, cnt = 7 (still negative)
  4. Continues with outer loop until a valid start point is found which is index 3.