How do you solve Gas Station on LeetCode?

Gas Station (LeetCode #134) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: The total gas must be greater than or equal to the total cost to complete the circuit.

What is the brute force solution for Gas Station?

The brute force approach for Gas Station is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every gas station as a potential starting point. For each station, we simulate the journey around the circuit to see if we can complete it with the available gas. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Gas Station?

Gas Station uses the following concepts: Array, Greedy. The recommended patterns to study are: Greedy, Array.

What are the interview tips for Gas Station?

Explain your thought process clearly while coding. Consider edge cases, such as when all gas values are less than costs. Practice simulating the journey to understand the problem better.

What are common mistakes when solving Gas Station?

Not considering the circular nature of the problem. Failing to reset the starting index when the tank goes negative.

#134

Gas Station

Medium

ArrayGreedyGreedyArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal approach uses a greedy method to determine if a complete circuit can be made. By tracking the total gas and cost, we can identify the starting point in a single pass.

⚙️

Algorithm

4 steps

1Step 1: Initialize total gas and total cost, and a temporary tank variable.
2Step 2: Loop through each gas station, updating the total gas and cost, and the temporary tank.
3Step 3: If the temporary tank drops below zero, reset the starting point to the next station and reset the temporary tank.
4Step 4: After the loop, if total gas is greater than or equal to total cost, return the starting index; otherwise return -1.

solution.py13 lines

1# Full working Python code
2
3def canCompleteCircuit(gas, cost):
4    total_gas = total_cost = tank = start = 0
5    n = len(gas)
6    for i in range(n):
7        total_gas += gas[i]
8        total_cost += cost[i]
9        tank += gas[i] - cost[i]
10        if tank < 0:
11            start = i + 1
12            tank = 0
13    return start if total_gas >= total_cost else -1

ℹ

Complexity note: This approach only requires a single pass through the gas stations, leading to O(n) time complexity and O(1) space complexity as we only use a few variables.

1The total gas must be greater than or equal to the total cost to complete the circuit.
2If the tank goes negative, the next station must be the new starting point.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.