Recursive C++ solution exceeds Time Limit, but runs fine for sample test data


  • 0
    N
    class Solution {
    public:
        
        int tryNext(int current_gas, int start_pos, int curr_pos, vector<int> gas, vector<int> cost)
        {
            // if last position has been reached return true
            if(start_pos == 0 && (curr_pos == gas.size() - 1))
            {
                current_gas += gas[curr_pos];
                
                if((current_gas - cost[curr_pos])<0)
                    return curr_pos;
                else
                    return 0;
            }
            if(curr_pos == (start_pos - 1))
            {
                current_gas += gas[curr_pos];
                
                if((current_gas - cost[curr_pos])<0)
                    return curr_pos;
                else
                    return 0;
            }
            current_gas += gas[curr_pos];
            
            if((current_gas - cost[curr_pos]) >= 0)
            {
                current_gas -= cost[curr_pos];
                // proceed
                return tryNext(current_gas, start_pos, ((curr_pos+1) % gas.size()), gas, cost);
            }
            else
            {
                return curr_pos;
            }
        }
        
        
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost)
        {
            int size = gas.size();
            
            if(size == 0)
                return -1;
            
            if(size == 1)
                return cost[0]<=gas[0] ? 1 :-1 ;
            
            int current_gas;
            
            // try each gas station as potential starting points if you can reach to the next station
            // at some point if you run out of gas, abandon all the points from that starting point till this point
            // choose the current as new starting point and re-try the search
            
            for(int i=0; i<size; i++)
            {
                current_gas = 0;
                
                int returnVal = tryNext(current_gas, i, i, gas, cost);
                
                if(returnVal == 0)
                    return 1;
                else
                    i = returnVal;
            }
            return -1;
        }
    };

Log in to reply
 

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