Test cases not good enough..wrong solution accepted..


  • 1
    Z

    My C++ code which is not correct is getting accepted by OJ. But on test gas[]={5,8,2,8}; and cost[]={6,5,6,6}; it should return 3 but it returns 1 which is wrong. I hope LeetCode will add the testcase.

    class Solution {
    public:
        int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
            int initial_idx=-1,current_idx=-1,max_diff=-1,diff=0,possible=0;
            int n=gas.size();
            for(int i=0;i<n;i++){
                diff+=gas[i]-cost[i];
                possible+=gas[i]-cost[i];
                if(diff>=0){
                    if(current_idx==-1)
                            current_idx=i;
                    if(diff>max_diff){
                        max_diff=diff;
                        initial_idx=current_idx;
                    }
                } else{
                    current_idx=-1;
                    diff=0;
                }
            }
           
            if(diff>0){
                int sum=0,pre=0;
                for(int i=0;(i<n)&&(sum>=0);i++){
                    pre=sum>pre?sum:pre;
                    sum+=gas[i]-cost[i];
                }
                if(pre+diff>max_diff)
                    initial_idx=current_idx;
            }
            if(possible<0)
                return -1;
            else
                return initial_idx;
        }
    };

Log in to reply
 

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