134. Gas Station

MediumGreedyArray
Leetcode Link

Problem Description

In this problem, we are given n gas stations that are placed along a circular route. Each gas station has a certain amount of gas given in an array gas[] where gas[i] is the amount of gas available at the ith gas station. Additionally, we have an array cost[] where cost[i] represents the amount of gas needed to travel from the ith station to the next station (i + 1)th. The goal is to find out if it's possible to start at a gas station with an empty gas tank and travel around the entire route once without running out of gas. If it is possible, we need to return the index of the starting gas station, otherwise, we return -1. It is important to note that if an answer exists, it is unique.

Intuition

To solve this problem, we need to check if the total amount of gas is at least as much as the total cost. If it is not, we cannot complete the trip, and we return -1. Otherwise, a start point exists, and we need to find it.

The intuition behind the solution is to keep track of the total gas in the car (s) as we try to make the circuit. We start at the last gas station and work backwards to see if we can reach it from the second to last, third to last and so on. This is done because if we can't complete the circuit starting at station i, then we also can't complete it starting at any station before it, as we would have even less gas by the time we reached i.

  1. We initialize two pointers i and j to the last station (index n - 1).
  2. We then try to make the trip by simulating the journey, incrementing j and decrementing i as necessary as we simulate traveling around the circle. Every time we move to the next station, we update the total gas in the car s by adding the gas we get from the current station (gas[j]) and subtracting the cost to get to the next station (cost[j]).
  3. If at any point our total s becomes negative, it means we can't reach the next station from our current starting point. Therefore, we need to change our starting point to the previous station by decrementing i and adding the gas available at the new starting station minus the cost to get to the next station.
  4. We continue this process until we've checked all n stations.

If by the end of this process, s is still negative, it means we couldn't find a starting point that could complete the circuit; thus, we return -1. Otherwise, the i at which we finish is our starting point that can complete the circuit.

Learn more about Greedy patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Solution Approach

The solution approach for this problem is based on the greedy algorithm. The implementation may seem a bit counter-intuitive at first glance because it works backwards, starting from the end of the loop rather than the beginning.

Here's a step-by-step guide through the algorithm:

  • Initialize two pointers i and j to the last position in the arrays (n - 1). They will indicate the starting point of our journey (i) and the current station we are considering (j).

  • Initialize two variables: cnt to keep track of how many stations we have considered so far, and s to represent the total amount of gas available subtracting the cost needed to get to the next station.

  • Use a while loop to iterate until we have considered all n stations (cnt < n). For each iteration:

    • We add the net gas (gas at current station minus cost to next station) for station j to s (total gas available) and increment cnt.
    • We move to the next station j by using modular arithmetic (j + 1) % n, which wraps the index around to the start of the array when j reaches the end.
    • If ever our total available gas s drops below zero, it means we cannot reach the next station from our current start point, and thus we move our candidate starting point back one station (i -= 1).
    • We then incorporate this station's net gas into s and increment cnt.

  • After finishing the loop, if our total gas s is negative, it means that we were not able to find a path that completes the circuit, and as per problem statement, we return -1.

  • In case s is non-negative, it means that the car can traverse the entire circuit starting from gas station at index i. The position i is our answer, the index of the starting gas station.

Here are some insights into the data structures and patterns used:

  • Arrays: The gas stations' gas and cost are given as arrays, and we are traversing these arrays to calculate the net gas.
  • Modular Arithmetic: This is used to wrap the circular route, allowing us to move through the circular array repeatedly.
  • Greedy Algorithm: We are using a greedy approach because at each step we take the best local decision: to move forward or change our start point, hoping to find a global optimum (a start point that lets us complete the circuit).

The overall complexity of the algorithm is O(n), because we are doing a single pass through the stations.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's consider a small example to illustrate the solution approach.

Suppose we have 4 gas stations with the following gas and cost values:

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

We will walk through the steps of the algorithm described above using these values.

Step 1: Initialization

We set i and j to the last index which is 3 in this case.

  • i = 3
  • j = 3
  • cnt = 0 to count the stations considered.
  • s = 0 to keep track of the net gas.

Step 2: Start the Iteration

We start iterating while cnt < n, where n = 4 is the number of gas stations.

Iteration 1:

  • j = 3
  • Add net gas of the current station (j) to s: s += gas[j] - cost[j] => s += 4 - 1 => s = 3
  • Increment cnt: cnt = 1
  • Move to the next station (in this case, wrap around to the first) j = (j + 1) % 4 => j = 0

Iteration 2:

  • j = 0
  • Add net gas of the current station to s: s += gas[j] - cost[j] => s += 1 - 2 => s = 2
  • Increment cnt: cnt = 2
  • Move to the next station: j = (j + 1) % 4 => j = 1

Iteration 3:

  • j = 1
  • Add net gas of the current station to s: s += gas[j] - cost[j] => s += 2 - 3 => s = 1
  • Increment cnt: cnt = 3
  • Move to the next station: j = (j + 1) % 4 => j = 2

Iteration 4:

  • j = 2
  • Before adding the net gas, we note that cost[j] is greater than gas[j] and if we added it, s would drop below zero. So, we need to change our start point.
  • Decrement i: i -= 1 => i = 2
  • We won't add gas[j] - cost[j] to s just yet because we are potentially moving our start point.

Adjust Starting Point:

  • Update s with the new start point's net gas: s += gas[i] - cost[i] => s += 3 - 1 => s = 3
  • Increment cnt: cnt = 4
  • Since we have considered all stations (cnt = n), we break out of the loop.

Determining the Result:

At the end of the loop:

  • s = 3
  • i = 2

Since s is not negative, it means it's possible to complete the circuit, starting from station 2. So, our answer is i = 2.

It's important to note that the explanation above used explicit iterations for clarity, while in actual implementation, checking the total gas s against zero and updating the start point i would happen inside of the same iteration.

Solution Implementation

1from typing import List
2
3class Solution:
4    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
5        # Initialize the length of the gas and cost lists
6        num_stations = len(gas)
7      
8        # Initialize pointers for traversing the gas stations
9        start_index = end_index = num_stations - 1
10      
11        # Initialize counter for stations visited and total balance of gas
12        stations_visited = total_gas_balance = 0
13      
14        # Loop until all stations have been visited
15        while stations_visited < num_stations:
16            # Update the total balance by adding current gas and subtracting current cost
17            total_gas_balance += gas[end_index] - cost[end_index]
18          
19            # Increment the number of stations visited
20            stations_visited += 1
21          
22            # Move to the next station, wrapping around if necessary
23            end_index = (end_index + 1) % num_stations
24          
25            # While the total balance is negative and we haven't visited all stations
26            # move the start index backwards and adjust the balance.
27            while total_gas_balance < 0 and stations_visited < num_stations:
28                # Move the start index to the previous station
29                start_index = (start_index - 1 + num_stations) % num_stations
30              
31                # Update the total balance by adding gas and subtracting cost at the new start
32                total_gas_balance += gas[start_index] - cost[start_index]
33              
34                # Increment the number of stations visited
35                stations_visited += 1
36      
37        # If the total balance is negative, return -1 indicating the circuit cannot be completed,
38        # otherwise return the start index
39        return -1 if total_gas_balance < 0 else start_index
40
1class Solution {
2    public int canCompleteCircuit(int[] gas, int[] cost) {
3        // n represents the total number of gas stations
4        int n = gas.length;
5
6        // Initialize index pointers for the circular route
7        int start = n - 1; // Start from the last station
8        int end = n - 1;   // End at the last station initially
9
10        // Initialize a sum to keep track of the remaining gas and count of stations checked
11        int sum = 0;
12        int stationsChecked = 0;
13
14        // Iterate until we've checked all stations
15        while (stationsChecked < n) {
16            // Calculate the remaining gas after visiting a station
17            sum += gas[end] - cost[end];
18            stationsChecked++; // Increment the number of stations checked
19            end = (end + 1) % n; // Move to the next station circularly
20
21            // If we have a deficit (sum < 0), try starting from an earlier station
22            while (sum < 0 && stationsChecked < n) {
23                start--; // Decrement start index to check an earlier station
24                sum += gas[start] - cost[start]; // Update sum for the new start station
25                stationsChecked++; // Increment the number of stations checked
26            }
27        }
28
29        // If we have remaining gas (sum >= 0), return the starting station
30        // Else, return -1 indicating the trip cannot be completed
31        return sum >= 0 ? start : -1;
32    }
33}
34
1#include <vector>
2
3class Solution {
4public:
5    int canCompleteCircuit(std::vector<int>& gas, std::vector<int>& cost) {
6        // 'n' represents the number of gas stations.
7        int n = gas.size();
8      
9        // Start from the last gas station.
10        int start = n - 1;
11      
12        // 'j' will be used to traverse the gas stations.
13        int j = n - 1;
14      
15        // 'tours' will count how many gas stations we have considered.
16        int tours = 0;
17      
18        // 'totalFuel' will keep track of our current fuel balance.
19        int totalFuel = 0;
20
21        // Loop through the gas stations to see where we can start.
22        while (tours < n) {
23            // Add net fuel (after consuming cost) at the current station.
24            totalFuel += gas[j] - cost[j];
25          
26            // Move to the next gas station.
27            tours++;
28            j = (j + 1) % n;
29          
30            // If our total fuel goes negative, move start one station backward
31            // and add the net fuel at that station to 'totalFuel'.
32            while (totalFuel < 0 && tours < n) {
33                // Only able to move backward if the total number of steps
34                // considered is less than the number of gas stations.
35                start--;
36                totalFuel += gas[start] - cost[start];
37              
38                // Another station considered.
39                tours++;
40            }
41        }
42      
43        // If after considering all stations the 'totalFuel' is still negative,
44        // there is no way to complete the circuit. Otherwise, return the starting station.
45        return totalFuel < 0 ? -1 : start;
46    }
47};
48
1// Function to determine if a vehicle can complete a circuit given the gas and cost.
2function canCompleteCircuit(gas: number[], cost: number[]): number {
3    // Total number of gas stations.
4    const totalStations = gas.length;
5
6    // Initialize pointers for current and next station.
7    let currentStation = totalStations - 1;
8    let nextStation = totalStations - 1;
9
10    // Initialize surplus gas variable to store the surplus/deficit gas amount.
11    let surplusGas = 0;
12
13    // Counter for how many stations have been visited.
14    let stationsVisited = 0;
15
16    // Loop through all stations until all stations have been visited.
17    while (stationsVisited < totalStations) {
18        // Calculate current surplus by adding gas available and subtracting the cost.
19        surplusGas += gas[nextStation] - cost[nextStation];
20      
21        // Increment station visited counter.
22        stationsVisited++;
23      
24        // Move to next station, wrap around if necessary.
25        nextStation = (nextStation + 1) % totalStations;
26
27        // If surplus is negative and not all stations have been visited, 
28        // move current station counter backwards and add to surplusGas.
29        while (surplusGas < 0 && stationsVisited < totalStations) {
30            currentStation = (currentStation - 1 + totalStations) % totalStations; // Ensure currentStation stays within bounds.
31            surplusGas += gas[currentStation] - cost[currentStation];
32          
33            // Increment stations visited to account for new calculation.
34            stationsVisited++;
35        }
36    }
37
38    // Return the starting station index if a circuit is possible, else return -1.
39    return surplusGas >= 0 ? currentStation : -1;
40}
41
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the minimum element can be found in:

Time and Space Complexity

The given Python code is intended to solve the gas station problem, which involves finding a starting gas station from which a vehicle can travel around a circular route without running out of gas, assuming the vehicle starts with an empty gas tank.

The time complexity of the provided code is O(n), where n is the number of gas stations. This is because although there are nested while-loops, the outer loop and the inner loop combined ensure that each station is visited at most twice: once when moving forward (cnt and j increment) and possibly once when moving backward (i decrement). The condition cnt < n prevents the code from examining more than n elements.

The space complexity of the algorithm is O(1). This is because the solution uses only a fixed number of variables (n, i, j, cnt, s) and does not allocate any additional space that would grow with the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫