Gas Station

Medium

Python

def can_complete_circuit(gas,cost):
    if sum(gas)<sum(cost): return -1
    tank=start=0
    for i in range(len(gas)):
        tank+=gas[i]-cost[i]
        if tank<0: tank=0; start=i+1
    return start

Java

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

Key Insight

Python sum() checks upfront. Java combines into one loop.

Python → Java Differences

Python sum() vs Java manual total
Python checks feasibility first
Greedy start tracking

Python

def can_complete_circuit(gas,cost):
    if sum(gas)<sum(cost): return -1
    tank=start=0
    for i in range(len(gas)):
        tank+=gas[i]-cost[i]
        if tank<0: tank=0; start=i+1
    return start

Java

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

Algorithm Steps

1. Check feasibility
2. Reset start when tank negative

← Previous All Greedy Next →