algoadvance

Leetcode 134. Gas Station

Problem Statement

The problem is to determine if there is a starting gas station around a circular route where a car can travel, starting with an empty tank. The car can travel from the index i to the next index i+1, and the car’s tank can be refueled at each gas station. You are given two integer arrays: gas where gas[i] is the amount of gas at the i-th station, and cost where cost[i] is the amount of gas needed to travel from the i-th station to the (i+1)-th station.

Your goal is to return the starting gas station index if you can travel around the circuit once in the clockwise direction, otherwise, return -1.

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

Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1

Clarifying Questions

  1. Q: Can the arrays gas and cost have different lengths? A: No, both arrays will always have the same length.

  2. Q: What are the constraints on the values of gas[i] and cost[i]? A: We assume that 0 <= gas[i], cost[i] <= 10^4 and the lengths of the arrays are 1 <= n <= 10^4.

  3. Q: If there are multiple valid starting stations, can I return any of them? A: Yes, you can return any valid starting station index.

Strategy

  1. Initial Pass: Compute the total surplus or deficit of gas.
    • If total gas available is less than total cost, return -1 because it’s impossible to complete the circuit.
  2. Finding the Start Station: Traverse the arrays to find the start index.
    • Initialize the total deficit and current surplus.
    • Iterate over the stations:
      • Update current surplus as the difference between gas at current station and cost to next station.
      • If current surplus drops below zero, it means the portion up to this station is unsustainable as a starting point; hence, reset the start position to the next station and update the total deficit.
  3. Return the Start Index: If the total deficit is within the total surplus (considering both start and remaining journey), we have the valid start station, otherwise return -1.

Code

#include <vector>
using namespace std;

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int totalGas = 0, totalCost = 0, start = 0, tank = 0;

        for (int i = 0; i < n; ++i) {
            totalGas += gas[i];
            totalCost += cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }

        return totalGas >= totalCost ? start : -1;
    }
};

Time Complexity

This approach ensures an efficient solution through optimized traversal and logical condition checks, adhering to a linear time complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI