Simple JAVA Solution using Linked List and Hash


  • 0
    C

    ...
    public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
    Helper head=new Helper(gas[0],cost[0],0);
    Helper current=head;

        for(int i=1;i<gas.length;i++){
            current.next=new Helper(gas[i],cost[i],i);
            current=current.next;
        }
        
        current.next=head; 
        HashSet<Helper> hs=new HashSet<>();     
        Helper startGas=head;
       
        
        while(!hs.contains(startGas)){
             int leftGas=0;
             Helper currentGas=startGas;
             while(leftGas>=0){
                 hs.add(currentGas);
                 leftGas=leftGas+currentGas.gas-currentGas.costToNextGas;
                 currentGas=currentGas.next;
                 if(leftGas>=0 && currentGas==startGas) return currentGas.index;
             }
             startGas=currentGas;
             
        }
        
        return -1;
        
    }
    
    
    class Helper{
        int gas;
        int costToNextGas;
        int index;
        Helper next;
        Helper(int gas,int costToNextGas,int i){
            this.gas=gas;
            this.costToNextGas=costToNextGas;
            index =i;
        }  
    }
    

    }
    ...


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.