algoadvance

Leetcode 134. Gas Station

Problem Statement

There are n gas stations along a circular route, where the amount of gas at the i-th station is represented by gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i-th station to its next (i + 1)-th station. You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Example:

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

Output: 3

Input:
gas  = [2,3,4]
cost = [3,4,3]

Output: -1

Clarifying Questions

1. Is the input guaranteed to always have at least one station?
   • Yes, as per the problem description, n >= 1.
2. Can gas[i] and cost[i] be negative or zero?
   • Both gas[i] and cost[i] are non-negative integers.
3. Can we assume that gas stations are on a circular route, meaning after the last station, the next station is the first one?
   • Yes, the route is circular.

Strategy

To solve this problem, we can use a greedy approach for simplicity and efficiency:

1. Check Total Feasibility:
   • First, if the total amount of gas available is less than the total amount of gas required (sum(gas) < sum(cost)), the trip is impossible, and we should return -1.
2. Finding the Starting Point:
   • If sum(gas) >= sum(cost):
     • Initialize two variables: total_tank and current_tank to 0, and a variable starting_station to 0.
     • Traverse through each station:
       • Update total_tank by adding the net gas at the current station (gas[i] - cost[i]).
       • Update current_tank similarly.
       • If current_tank drops below 0, it means you cannot reach the next station from the current starting station. Therefore, set the next station as the new starting station and reset current_tank to 0.
     • After the loop, if total_tank is non-negative, return the starting_station, otherwise return -1.

Code

public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalTank = 0;
        int currentTank = 0;
        int startingStation = 0;
        
        for (int i = 0; i < gas.length; i++) {
            int netGas = gas[i] - cost[i];
            totalTank += netGas;
            currentTank += netGas;
            
            if (currentTank < 0) {
                startingStation = i + 1;
                currentTank = 0;
            }
        }
        
        return totalTank >= 0 ? startingStation : -1;
    }
}

Time Complexity

• Time Complexity: O(n)
  • We traverse the array only once, making the algorithm linear in terms of the input size.
• Space Complexity: O(1)
  • We use a constant amount of extra space regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?