## Global Scholar Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

You can keep only 3 nodes in the max heap, and only two nodes in min heap, thus reaching the O(n) complexity.

```
int prod3(int arr[], int size)
{
int i,max1,max2,max3,min1,min2;
max1=max2=max3=min1=min2=arr[0];
for(i=0;i<size;i++)
{
if(arr[i]>max1)
{
max3=max2;
max2=max1;
max1=arr[i]; //Max Value
}
else if(arr[i]>max2)
{
max3=max2;
max2=arr[i] //2nd Max value
}
else if(arr[i]>max3)
{
max3=arr[i]; //3rd max value
}
if(min1<arr[i])
{
min2=min1;
min1=arr[i]; //Min value
}
else if(min2<arr[i])
{
min2=arr[i]; //2nd Min value
}
}
int prod1,prod2;
prod1=min1*min2*max1;
prod2=max1*max2*max3;
if(prod1<prod2)
return prod2;
else
return prod1;
}
```

take three variables a,b,c

for(i=0;i<=1;i++)

{

a=a+b;b=a-b;a=a-b;

b=b+c;c=b-c;b=b-c;

}

for(i=3;i<n;i++)

{

if(a[i]>a)

{

t=a;t1=b;

a=a[i];b=t;c=t1;

}

else if(a[i]>b)

{

b=c;c=a[i];

}

else

{

if(a[i]>c)

{

c=a[i];

}

}

}

step-1 create a max heap out of the array

- raja roy January 22, 2012step-2 create a min heap out of the array(only if the array contains -ve nos)

step-3 delete three elements(say maxa, maxb, maxc) from the max heap these elements would the 3 largest elements in the array

step-4 if the array contains -ve elements then delete TWO elements(say mina, minb) from the min heap.

step-5 If the array contains -ve elements then check

if((mina *minb) > (maxa*maxb))

then MaxProduct = mina *minb * maxc

else

MaxProduct = maxa*maxb*maxc

Total time would be = O(nlogn) which could be reduce to O(n) if you create using fast heap