134. Gas Station

📝 Problem Details

• Title: 134. Gas Station
• Link: https://leetcode.com/problems/gas-station/
• Difficulty: Medium
• Tags/Categories: Greedy

input array gas input array cost return the starting gas station’s index if you can travel around the circuit once in a clockwise direction, otherwise return -1

💭What Were My Initial Thoughts?

- The problem involves a circular dependency
- suggests a greedy approach rather than brute force
- the naive approach would be to similar the journey from each gas station, but that would be O(n^2) and inefficient

- if the total gas is less than total cost, its impossible to complete the journey, so we can return -1
- if there's a solution, there must be one unique starting station that allow us to complete the loop

💡 Explanation of Solution

Greedy Approach:
1. Compute the net gain for each station:
	gain[i] = gas[i] - cost[i]

2. Track:
	- totalGain : total net gas after visiting all stations
	- currGain : running sum of the gas from a given starting station
	- answer : potential starting station

3. if currGain drops below 0, reset the starting index to the next station
	- this is because any station before this cannot be a valid starting point

4. if totalGain >= 0, return answer, otherwise return -1

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int currGain = 0, totalGain = 0, answer = 0;
 
        for (int i = 0; i < gas.size(); ++i) {
            // gain[i] = gas[i] - cost[i]
            totalGain += gas[i] - cost[i];
            currGain += gas[i] - cost[i];
 
            // If we meet a "valley", start over from the next station
            // with 0 initial gas.
            if (currGain < 0) {
                answer = i + 1;
                currGain = 0;
            }
        }
 
        return totalGain >= 0 ? answer : -1;
    }
};