Gas station

Array Greedy

47.5% acceptance

Jan 12, 2026

13415

1375

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn can_complete_circuit(gas: Vec<i32>, cost: Vec<i32>) -> i32 {
    let n = gas.len();
    let mut total_gas = 0;
    let mut current_gas = 0;
    let mut start = 0;
    
    for i in 0..n {
      let diff = gas[i] - cost[i];
      total_gas += diff;
      current_gas += diff;
      
      // If current gas becomes negative, we can't start from current start position
      if current_gas < 0 {
        start = i + 1;
        current_gas = 0;
      }
    }
    
    // If total gas is negative, no solution exists
    if total_gas < 0 {
      -1
    } else {
      start as i32
    }
  }
}