Leetcode 134 : Gas Station

#programming #tutorial #beginners

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 <= 10^5
0 <= gas[i], cost[i] <= 10^ 4

Intuition

We have to find a particular position such that if we started from that position, we can cover all the gas stations with enough amount of fuel.
Suppose there are two gas stations A and B, if A can reach B, then all the stations in between can also reach B. Also if we consider that A cannot reach B, and B is the first station where A cannot reach, then there are chances that any stations in between A and B can also never reach B as there will not be enough gas available. So we need to consider starting from the gas station after B.
Also if the gas we used to cover all the stations is greater than the cost of gas we paid, then we are surely having a station that will satisfy our condition.

Approach

Store the gasAvailable, amountPaid, gasUsed, and startPoint to some variable.
Start iterating through the array.
Increment our gasUsed and amountPaid.
Update the gasAvailable after traveling from gas1 to gas2.
If the gasAvailable is negative, then there is no good starting position till now, reset the starting position to index + 1.
Once the iteration is over, check how much we paid. If it's greater than the amount of gas we used, then there is no starting point. Return -1, else we return the starting point.

Complexity

Time complexity:
We are iterating through the array once and thus it's a one-pass solution.
Time complexity will be O(n) where n = length of the array.
Space complexity:
No extra space is used. Thus space complexity will be O(1).

Code

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int gasAvailable = 0;
        int gasUsed = 0;
        int paid = 0;
        int startingPoint = 0;
        for (int i=0; i<length; i++) {
            gasUsed += gas[i];
            paid += cost[i];
            gasAvailable += gas[i] - cost[i];
            if (gasAvailable < 0) {
                gasAvailable = 0;
                startingPoint = i + 1;
            }
        }
        return paid > gasUsed ? -1 : startingPoint;
    }
}