LeetCode Challenge: 134. Gas Station - JavaScript Solution 🚀

Top Interview 150

The Gas Station problem is a classic interview question that tests your understanding of greedy algorithms. Let's explore LeetCode 134: Gas Station, break it down, and implement an efficient solution.

---

🚀 Problem Description

You are given two integer arrays:

• gas: The amount of gas available at each station.
• cost: The gas required to travel to the next station.

You need to determine:

• If you can travel around the circuit starting at one of the gas stations.
• Return the index of the starting gas station if possible; otherwise, return -1.
• The solution is guaranteed to be unique if one exists.

---

💡 Examples

Example 1

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]  
Output: 3  
Explanation: Starting at index 3 allows a successful circuit.

Example 2

Input: gas = [2,3,4], cost = [3,4,3]  
Output: -1  
Explanation: It is not possible to complete the circuit.

---

🏆 JavaScript Solution

The key observation is:

• If the total gas available is less than the total cost required, completing the circuit is impossible.
• If the total gas is greater or equal to the total cost, then a greedy approach can determine the starting station.

---

Step-by-Step Implementation

var canCompleteCircuit = function(gas, cost) {
    let totalTank = 0;
    let currentTank = 0;
    let startStation = 0;

    for (let i = 0; i < gas.length; i++) {
        let netGain = gas[i] - cost[i];

        totalTank += netGain;
        currentTank += netGain;

        if (currentTank < 0) {
            startStation = i + 1;
            currentTank = 0;
        }
    }

    return totalTank >= 0 ? startStation : -1;
};

---

🔍 How It Works

1. Track net gas: At each station, calculate the net gain (gas[i] - cost[i]) and add it to both totalTank (total balance) and currentTank (current balance).

2. Reset starting point:

   • If currentTank becomes negative, it means you can’t travel from the current starting station.
   • Reset the starting station to i + 1 (next station).

3. Final check:

   • If totalTank is negative, return -1 (impossible to complete the circuit). Otherwise, return the index of the startStation.

---

🔑 Complexity Analysis

Time Complexity: O(n), where n is the number of gas stations. The array is traversed once.
Space Complexity: O(1), as no additional data structures are used.

---

📋 Dry Run

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

Output: 3

---

✨ Pro Tips for Interviews

1. Understand the conditions: If the total net gas (sum(gas) - sum(cost)) is negative, completing the circuit is impossible.
2. Optimize for one pass: Instead of repeatedly checking starting points, reset the start when the current gas balance drops below zero.
3. Edge cases:
   • Single gas station (gas = [3], cost = [2] → 0).
   • All stations have equal gas and cost (gas = [1,1,1], cost = [1,1,1] → 0).

---

📚 Learn More

Check out the full explanation and code walkthrough on my Dev.to post:
👉 238. Product of Array Except Self - JavaScript Solution

How would you optimize this further? Let’s discuss below! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!