Gas Station

                                            
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        int total_tank = 0;
        int curr_tank = 0;
        int starting_station = 0;
        
        for (int i = 0; i < n; ++i) {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];
            if (curr_tank < 0) {
                starting_station = i + 1;
                curr_tank = 0;
            }
        }
        
        return total_tank >= 0 ? starting_station : -1;
    }
};

                                            
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int curr = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            total += gas[i] - cost[i];
            curr += gas[i] - cost[i];
            if (curr < 0) {
                start = i + 1;
                curr = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
}

                                            
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        total_tank = 0
        curr_tank = 0
        starting_station = 0
        
        for i in range(len(gas)):
            total_tank += gas[i] - cost[i]
            curr_tank += gas[i] - cost[i]
            
            if curr_tank < 0:
                starting_station = i + 1
                curr_tank = 0
                
        return starting_station if total_tank >= 0 else -1

                                            
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) 
{
    int total_tank = 0;
    int curr_tank = 0;
    int starting_station = 0;

    for (int i = 0; i < gasSize; i++) {
        total_tank += gas[i] - cost[i];
        curr_tank += gas[i] - cost[i];
        
        if (curr_tank < 0) {
            curr_tank = 0;
            starting_station = i + 1;
        }
    }

    return total_tank >= 0 ? starting_station : -1;
}

                                            
public class Solution {
    public int CanCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int tank = 0;
        int start = 0;

        for (int i = 0; i < gas.Length; i++) {
            total += gas[i] - cost[i];
            tank += gas[i] - cost[i];

            if (tank < 0) {
                start = i + 1;
                tank = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
}

                                            
/**
 * @param {number[]} gas
 * @param {number[]} cost
 * @return {number}
 */
var canCompleteCircuit = function(gas, cost) {
    let totalGas = 0;
    let totalCost = 0;
    let tank = 0;
    let start = 0;
    
    for (let i = 0; i < gas.length; i++) {
        totalGas += gas[i];
        totalCost += cost[i];
        tank += gas[i] - cost[i];
        if (tank < 0) {
            start = i + 1;
            tank = 0;
        }
    }
    
    return totalGas < totalCost ? -1 : start;
};

                                            
function canCompleteCircuit(gas: number[], cost: number[]): number {
    const totalGas = gas.reduce((acc, val) => acc + val, 0);
    const totalCost = cost.reduce((acc, val) => acc + val, 0);

    if (totalGas < totalCost) {
        return -1;
    }

    let tank = 0;
    let start = 0;
    let remains = 0;

    for (let i = 0; i < gas.length; i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {
            start = i + 1;
            remains += tank;
            tank = 0;
        }
    }

    return tank + remains >= 0 ? start : -1;
};

                                            
class Solution {
    /**
     * @param Integer[] $gas
     * @param Integer[] $cost
     * @return Integer
     */
    function canCompleteCircuit($gas, $cost) {
        $totalTank = 0;
        $currentTank = 0;
        $startIndex = 0;
        
        for ($i = 0; $i < count($gas); $i++) {
            $totalTank += $gas[$i] - $cost[$i];
            $currentTank += $gas[$i] - $cost[$i];
            
            if ($currentTank < 0) {
                $startIndex = $i + 1;
                $currentTank = 0;
            }
        }
        
        return $totalTank >= 0 ? $startIndex : -1;
    }
}

                                            
class Solution {
    func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
        var totalTank = 0
        var currTank = 0
        var startingStation = 0
        
        for i in 0..<gas.count {
            totalTank += gas[i] - cost[i]
            currTank += gas[i] - cost[i]
            
            if currTank < 0 {
                startingStation = i + 1
                currTank = 0
            }
        }
        
        return totalTank >= 0 ? startingStation : -1
    }
}

                                            
class Solution {
    fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
        var total = 0
        var current = 0
        var start = 0
        
        for (i in gas.indices) {
            total += gas[i] - cost[i]
            current += gas[i] - cost[i]
            
            if (current < 0) {
                start = i + 1
                current = 0
            }
        }
        
        return if (total >= 0) start else -1
    }
}

                                            
class Solution {
  int canCompleteCircuit(List<int> gas, List<int> cost) {
      int total = 0;
      int sum = 0;
      int start = 0;
      
      for (int i = 0; i < gas.length; i++) {
          total += gas[i] - cost[i];
          sum += gas[i] - cost[i];
          
          if (sum < 0) {
              start = i + 1;
              sum = 0;
          }
      }
      
      return total >= 0 ? start : -1;
  }
}

                                            
func canCompleteCircuit(gas []int, cost []int) int {
    totalTank := 0
    currentTank := 0
    start := 0
    
    for i := 0; i < len(gas); i++ {
        totalTank += gas[i] - cost[i]
        currentTank += gas[i] - cost[i]
        
        if currentTank < 0 {
            start = i + 1
            currentTank = 0
        }
    }
    
    if totalTank < 0 {
        return -1
    }
    
    return start
}

                                            
# @param {Integer[]} gas
# @param {Integer[]} cost
# @return {Integer}
def can_complete_circuit(gas, cost)
    total_tank = 0
    tank = 0
    start = 0
    gas.each_with_index do |g, i|
        tank += g - cost[i]
        total_tank += g - cost[i]
        if tank < 0
            start = i + 1
            tank = 0
        end
    end
    total_tank >= 0 ? start : -1
end

                                            
object Solution {
    def canCompleteCircuit(gas: Array[Int], cost: Array[Int]): Int = {
        var totalGas = 0
        var totalCost = 0
        var currGas = 0
        var start = 0

        for (i <- gas.indices) {
            totalGas += gas(i)
            totalCost += cost(i)
            currGas += gas(i) - cost(i)
            if (currGas < 0) {
                start = i + 1
                currGas = 0
            }
        }

        if (totalGas < totalCost) {
            -1
        } else {
            start
        }
    }
}

                                            
impl Solution {
    pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
        let mut total_tank = 0;
        let mut curr_tank = 0;
        let mut starting_station = 0;

        for i in 0..gas.len() {
            total_tank += gas[i] - cost[i];
            curr_tank += gas[i] - cost[i];

            if curr_tank < 0 {
                starting_station = i + 1;
                curr_tank = 0;
            }
        }

        if total_tank >= 0 {
            return starting_station as i32;
        } else {
            return -1;
        }
    }
}

To solve this coding challenge, we need to determine if we can traverse all gas stations in a circular route starting from a specific station, given the amount of gas at each station and the gas cost needed to travel to the next station. The goal is to find the starting station index that allows us to complete the circular route, or return

-1

if it's not possible.

# Explanation

The problem essentially boils down to understanding whether there is a feasible starting point from which we can complete the entire route without running out of gas. We can leverage a greedy approach given that there is a guarantee of a unique solution or no solution.

Approach:

Total Balance Check : If the total amount of gas is greater than or equal to the total cost, it implies that there is enough gas to complete the journey, but we need to identify the correct starting point.
Current Balance Check : Track the current balance of gas while iterating through the stations. Whenever the gas balance falls below zero, that means the current starting point is not viable; thus, the next station should be considered as a new starting point.
Iterate Through Stations : Maintain two variables: one for accumulating the total gas surplus (to confirm the feasibility of traveling the entire route), and another for tracking the surplus at any given point to identify the viable starting station.

Detailed Steps in Pseudocode:

Initialization :

Initialize variables for total gas surplus, current gas surplus, and the starting station index.

Iterate Over Stations :

For each station, update the total and current gas surplus by subtracting the cost from the available gas.
If at any point the current gas surplus is negative, reset it to zero and set the starting station to the next station (current index + 1).

Check Feasibility and Return Result :

After the loop, if the total gas surplus is non-negative, the journey is feasible starting from the identified starting station. Otherwise, return
-1

indicating no possible route.

Pseudocode

Here is the final pseudocode with comments:

                                            
# Function to determine the starting gas station index
# or -1 if the route is not possible
function canCompleteCircuit(gas, cost):
    # Initialize the total tank and current tank to 0
    total_gas_surplus = 0
    current_gas_surplus = 0
    starting_station = 0

    # Iterate through each station
    for station_index from 0 to len(gas) - 1:
        gas_balance = gas[station_index] - cost[station_index]
        # Update total gas surplus
        total_gas_surplus += gas_balance
        # Update current gas surplus and check if it becomes negative
        current_gas_surplus += gas_balance

        # If current gas surplus is negative
        if current_gas_surplus < 0:
            # Reset current gas surplus
            current_gas_surplus = 0
            # Update the starting station to the next station
            starting_station = station_index + 1

    # After the loop, check if the total gas surplus is non-negative
    if total_gas_surplus >= 0:
        return starting_station
    else:
        return -1

Detailed Breakdown:

Initialization :

total_gas_surplus

: Keeps track of the overall surplus gas across all stations.
current_gas_surplus

: Tracks the running total of surplus gas to identify if a reset is needed when it drops below zero.
starting_station

: Marks the index of the station from which the circular journey should start.

Iteration Over Stations :

For each station, calculate the gas balance (
gas_balance

).
Update the
total_gas_surplus

to ensure at the end if it's non-negative.
Update the
current_gas_surplus

and check if it becomes negative. If it does, reset it and move the starting point to the next station.

Feasibility Check :

After completing the loop, determine if the journey is possible by checking if
total_gas_surplus

is non-negative.

This approach ensures that each station is considered as a potential starting point if needed, and thus guarantees finding the correct starting index or confirms it's impossible to complete the journey.