Why 36 / 41 test cases passed?


  • 0
    C

    Does anyone know why my following code is wrong? I think the logic is right. Thanks

    public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
    unordered_map<int, pair<int,int>> idxToLeftRightLen;
    int n = nums.size(), cnt=0, pre=-1;

        for(int i=0; i<n; i++){
            if (nums[i]==1)
                cnt++;
            else{
                if (i==0)
                   idxToLeftRightLen[0]=make_pair(0,0);
                
                if (i==n-1)   
                   idxToLeftRightLen[n-1]=make_pair(cnt,0);
                
                if (idxToLeftRightLen.find(i)==idxToLeftRightLen.end())
                    idxToLeftRightLen[i]=make_pair(cnt, 0);
                if (pre!=-1)
                    idxToLeftRightLen[pre-1].second = cnt;
                cnt=0;
                if (i+1<n&&nums[i+1]==1)
                    pre=i+1;
                    
                //cout<<pre<<endl;
            }
        }
        int res = 0;
        if (pre!=-1)
            idxToLeftRightLen[pre-1].second = cnt;
        if (idxToLeftRightLen.empty())
            return n;
        for (auto zeros: idxToLeftRightLen){
            //cout<< zeros.second.first ;
            //cout<< " ";
            //cout<< zeros.second.second<<endl;
            res = max(res, zeros.second.first + zeros.second.second + 1);
        }
        
        return res;
    }

  • 0

    @coder2 said in Why 36 / 41 test cases passed?:

    I see you define map idxToLeftRightLen[i] = make_pair(L, R) if nums[i] == 0 and there are L consecutive 1's to its left and R consecutive '1''s to its right. And pre denotes the last index where nums[pre-1] == 0.

    The problem is this condition check:

    if (i+1<n&&nums[i+1]==1)

    You should remove this condition before update pre = i+1. If you define pre-1 as the previous index where nums[pre-1] == 0, then you should allow prev to be n+1. For example, you code will fail test case [1,0,1,0] where pre didn't update when the last '0' is scanned in the array.

    Actually, you can remove some redundant settings of map idxToLeftRightLen to clean up the code.

    Note: you can set a boundary case at idxToLeftRightLen[-1] = make_pair(0,cnt) so you don't have to check whether idxToLeftRightLen.empty().

        int findMaxConsecutiveOnes(vector<int>& nums) {
            unordered_map<int, pair<int,int>> idxToLeftRightLen;
            int n = nums.size(), cnt=0, pre=-1, res = 0;
            for(int i=0; i<=n; i++)
                if (i < n && nums[i] == 1) cnt++;
                else{
                    if (i<n) idxToLeftRightLen[i] = make_pair(cnt, 0);
                    idxToLeftRightLen[pre].second = cnt;
                    cnt=0; pre=i;
                }
                
            for (auto zeros: idxToLeftRightLen)
                res = max(res, zeros.second.first + zeros.second.second + (zeros.first>=0));
            
            return res;
        }
    

Log in to reply
 

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