CareerCup

A min_heap of size 6 suffices.

takes 6 extra space then.

look up quick-select or selection algo..linear time.. O(1) space

int sixthLargest(const int a[]) {
    int max[6] = {INT_MIN};
    for (int i = 0; i < N; ++i)
        if (a[i] > max[0]) max[0] = a[i];
    for (int x = 1; x < 6; ++x)
        for (int i = 0; i < N; ++i)
            if (a[i] > max[x] && a[i] < max[x - 1]) max[x] = a[i];
    return max[5];
}

T: O(6n) = O(n)
S: O(6) = O(1)

this is simple selection problem

ghouse if u cn explain how it can be solved by selection

I think this works..

int sixthLargest(int[] a){
	int[] max = {Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE,
			Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE};
	for(int i=0; i<a.length; i++){
		int index=-1;
		for(int j=0;j<max.length;j++){
			if(a[i]>max[j]){
				index = j;
				break;
			}
		}
		if(index!=-1){
			//move all max[index] -> max[index+1]
			for(int j=max.length-1; j>index; j--)
				max[j]=max[j-1];
				max[index]=a[i];
			}
		}
	return max[5];
}

The space complexity is O(1) - constant
The time complexity is O(n)

i don't think show ashok

can u explain ur code

good sol given by mg but same as bubble sort o(k*n)

good sol given by mg but same as bubble sort o(k*n)

Use Median of Medians algorithm for selection.

That can give you a linear time algorithm.

1. Mark virtual boundary in a single dimensional with distance of 5 elements.
2. Sort these boundaries
3. Pick 5 elements using (i+2)th where i = 0 to 4
4. Sort these elements and find the pivot.
5. Apply partition using the above pivot.
6. Divide the problem and start again if necessary.
If k=r, then return m
If k<r, then return k thsmallest of the set L .(Bound time T7n/10)
If k>r, then return k-r thsmallest of the set R

Use selection sort to sort in decending order & terminate @ the 6th instance !

Use Counting Sort.

It requires O(n) extra space with Linear time O(n). this sort also known as stable sort. Algorithm is in below.

for i =1 to K
do C[i] = 0;
for j = 1 to length[A]
do C[A[j]] = C[A[j]]+1

C[i] is now contains the number of elements equal to i

for i = 2 to k
do C[i] = C[i] + C[i-1];

C[i] now contains the number of elements less than or equal to i

for j = length[A] to 1
do B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]]-1

here A is input array , B is output array and C is counter array

1)read first six numbers and create a min-heap of six elements....so that the root has minimum of the six.
2)now when you get a new number >root then pop the root and make root =new number
3) heapify the 6 element heap; takes O(log6) constant time
4)scan like this for whole array
5) the root gives the 6th greatest number

Overall complexity= O(nlog(6))==O(n)

code

#include<iostream>
#include<queue>

int main()
{
int a[]={10,23,44,2,1,4,56,23,56,75,35,73,354,1223,9};
priority_queue< int, greater<int> > min_h(a,a+5);
for(i=6;i<15;i++)
{
if(a[i]>min_h.top()) {min_h.pop(); min_h.push(a[i]);}
}
cout<<"6th greatest is "<<min_h.top();

return 0;
}

my approach
Read first 6 elements and keep them sorted in an array of size 6.
Now start reading from 7th element and see via binary search if the element is larger than greatest then ignore else place it in the array.
Iterate till end.
The loop invariant at any time maintains 6 s,mallest numbers in that array and return the last element of the temp array in the end
Space O(6) --- ie Constant space
time O(n)