#134

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Gas Station

The Gas Station problem requires finding the starting station index for a full circular trip with gas stations and costs.

array greedy

Problem Statement

You are given a circular route of gas stations where the amount of gas at the ith station is gas[i]. To travel between two stations, it costs cost[i] units of gas. You start with an empty tank at any station and must determine the best station to begin a circular trip, where you can complete a round trip using the available gas.

The goal is to find the index of the station from which you can complete a full loop, or return -1 if no such starting point exists. If a solution exists, it is guaranteed to be unique.

Examples

Example 1

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

Output: 3

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

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
The input is generated such that the answer is unique.

Solution Approach

Greedy Choice and Invariant Validation

The key to solving this problem is a greedy approach, where you try to pick a starting station and validate whether it's feasible to complete the loop. By tracking the remaining gas at each station, you maintain an invariant that helps you check whether the next station can be reached. If the total gas is less than the total cost, no solution exists.

Total Gas and Total Cost Comparison

Before starting the loop validation, compare the total gas and total cost. If the total gas available is less than the total cost required, then it is impossible to complete the loop, and you should return -1. This comparison ensures you don't waste time on infeasible paths.

Single Pass Optimization

Iterate through the stations once to check if starting from a particular station allows completing the journey. As you travel, update the current gas level and check if you ever run out of gas. If you do, move your starting point to the next station. This allows you to solve the problem in linear time.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) since we only iterate through the gas stations once to check all possible starting points, and the space complexity is O(1) as we only store a few variables to track gas levels and indices.

What Interviewers Usually Probe

The candidate demonstrates a good understanding of greedy algorithms by proposing a solution based on the greedy choice paradigm.
The candidate explains invariant validation correctly, ensuring that they track gas levels and station indices effectively throughout the solution.
The candidate shows familiarity with optimization techniques, aiming to solve the problem in linear time with minimal extra space.

Common Pitfalls or Variants

Common pitfalls

Failing to consider the case where the total gas is less than the total cost, which leads to an incorrect answer.
Not correctly handling the circular nature of the route, which might cause the candidate to miss a valid starting point.
Incorrectly assuming that it's always possible to start from any station and reach the end without first validating the total gas and cost.

Follow-up variants

What if the gas and cost arrays contain very large values, or the number of stations is extremely high?
How would you modify the approach to accommodate variable costs that change dynamically while traveling?
Can the problem be solved using a dynamic programming approach, and how would it compare to the greedy solution?

FAQ

What is the primary pattern for solving the Gas Station problem?

The Gas Station problem is typically solved using a greedy approach with invariant validation, ensuring that the remaining gas is enough to reach the next station.

Can the Gas Station problem be solved in less than linear time?

No, since we must examine every station to validate whether the journey can be completed, it requires a linear time complexity of O(n).

What happens if the total gas is less than the total cost in the Gas Station problem?

If the total gas is less than the total cost, it is impossible to complete the circuit, and the correct output would be -1.

How does the greedy approach work for the Gas Station problem?

The greedy approach works by attempting to start at a station and verifying if it is feasible to travel around the circle, adjusting the starting point if the gas runs out before reaching the next station.

How can GhostInterview help with solving the Gas Station problem?

GhostInterview helps by guiding you to apply a greedy strategy efficiently, optimize for linear time complexity, and track invariant validation during your solution process.

terminal

Solution

Solution 1

#### Python3

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        n = len(gas)
        i = j = n - 1
        cnt = s = 0
        while cnt < n:
            s += gas[j] - cost[j]
            cnt += 1
            j = (j + 1) % n
            while s < 0 and cnt < n:
                i -= 1
                s += gas[i] - cost[i]
                cnt += 1
        return -1 if s < 0 else i

Continue Practicing

#135 candy #122 best time to buy and sell stock ii #179 largest number