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

• 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;
}
};``````

• ``````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;
``````

}

• used your method @dbcooper. It got accepted.

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