Linear time complexity


#1

int Solution::solve(vector &A) {
int n=A.size();
int j=0;
for(int i=0;i<n;i++)
{
if(A[i]<0)
{
swap(A[i],A[j]);
j++;
}
}
int arr[n-j+1];
memset(arr,0,sizeof(arr));
for(int i=j;i<n;i++)
{
if(A[i]>n-j-1)
arr[n-j]++;
else
arr[A[i]]++;
}
int count=0;
for(int i=n-j;i>0;i–)
{
if(count+arr[i]==i-1 && arr[i-1])
return 1;
count+=arr[i];
}
return -1;
}