Why is my O(n) solution failing ? Custom Test case expected answer is also right.


  • 0
    D

    The OJ says a runtime error on [2,2] test case, but the expected answer when tried using the custom test case matches my answer. I first shift all non positive numbers to right , and then use the array indices as indicators, to find a missing positive. Whenever i come across a positive number, I turn the number at that index to negative. The index that is left positive is the answer. Can anyone help ?

    class Solution {
    public:
    int firstMissingPositive(vector<int>& nums) {
        if(nums.size()==0)
            return 1;
        int high=nums.size()-1;
        int i=0;
        while(i<=high){
            if(nums[i]<=0){
                int t=nums[high];
                nums[high]=nums[i];
                nums[i]=t;
                high--;
            }
            else
                i++;
        }
        for(int j=0;j<i;j++){
            if(nums[j]<0){
                int t=-nums[j];
                if(t>i)
                    continue;
                if(nums[t-1]<0)
                    continue;
                else 
                    nums[t-1]=-nums[t-1];
            }
            if(nums[j]<=i){
                if(nums[nums[j]-1]<0)
                    continue;
                nums[nums[j]-1]=-nums[nums[j]-1];
            }
        }
        for(int j=0;j<i;j++){
            if(nums[j]>0)
                return j+1;
        }
        return i+1;
    }
    };

  • 0
    M
    int firstMissingPositive(int* nums, int numsSize) {
    if(nums == NULL)
        return 1;
    
    int negativeStart = numsSize;
    int i=0;
    while(i<negativeStart)
    {
        if(nums[i]<=0)
        {
            int temp = nums[i];
            nums[i] = nums[negativeStart-1];
            nums[negativeStart -1] =nums[i];
            negativeStart--;
        }
        else
            i++;
    }
    printf("%d",negativeStart);
    i=0;
    while(i<negativeStart)
    {
        if(nums[i]>0)
        {
            nums[nums[i]-1] = (nums[nums[i]-1]>0)?-nums[nums[i]-1]:nums[nums[i]-1];
        }
        else
        {
            nums[-nums[i]-1] = (nums[-nums[i]-1]>0)?-nums[-nums[i]-1]:nums[-nums[i]-1];
        }
        i++;
    }
    
    i=0;
    while(i<negativeStart)
    {
        if(nums[i]>=0)
            return i+1;
        i++;
    }
    //if(i==negativeStart)
            return negativeStart+1;
    

    }


  • 0
    M

    used your method @dbcooper. It got accepted.


Log in to reply
 

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