My O(n) C solution.


  • 0
    P

    my C code. It costs 3ms.

    int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize) 
    {
        int i;
        int s, ret;//s: the start index of current sub-sequence; ret: the return value
        int diff[gasSize];//store (gas[i] - cost[i])
        int max = 0;//the largest and of the sub-sequence of diff[i]
        int sum = 0;//the and of current sub-sequence
        
        for(i=0; i<gasSize; i++)//get the difference between gas[i] and cost[i]
            diff[i] = gas[i] - cost[i];
            
        s = 0;
    
        for(i=0; s<gasSize; i++)//get the max and of diff
        {
            if(i>=s+gasSize)
                break;
                
            if(diff[i%gasSize]>=0)
            {
                sum += diff[i%gasSize];
                if(sum>max)
                {
                    max = sum;
                    ret = s;
                }
            }
            else
            {
                if(sum+diff[i%gasSize]<0)
                {
                    s = i+1;
                    sum = 0;
                }
                else
                {
                    sum += diff[i%gasSize];
                }
            }
            
        }
        
        //if the sum which begin with index ret is not always >= 0, return -1
        sum = 0;
        for(i=ret; i!=ret+gasSize; i++)
        {
            sum += diff[i%gasSize];
            if(sum<0)
                return -1;
        }
        
        return ret;
    }

Log in to reply
 

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