DEV Community

Cover image for LeetCode Challenge: 134. Gas Station - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

1 1 1 1 1

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.
Enter fullscreen mode Exit fullscreen mode

Example 2

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

πŸ† 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;
};
Enter fullscreen mode Exit fullscreen mode

πŸ” 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]

Gas Station
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

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

A Workflow Copilot. Tailored to You.

Pieces.app image

Our desktop app, with its intelligent copilot, streamlines coding by generating snippets, extracting code from screenshots, and accelerating problem-solving.

Read the docs